Aurelia Butler

While Santa Claus may have a magical sleigh and nine plucky reindeer to help him deliver presents, for companies like FedEx, the optimization problem of efficiently routing holiday packages is so complicated that they often employ specialized software to find a solution.
This software, called a mixed-integer linear programming (MILP) solver, splits a massive optimization problem into smaller pieces and uses generic algorithms to try and find the best solution. However, the solver could take hours — or even days — to arrive at a solution.
The process is so onerous that a company often must stop the software partway through, accepting a solution that is not ideal but the best that could be generated in a set amount of time.
Researchers from MIT and ETH Zurich used machine learning to speed things up.
They identified a key intermediate step in MILP solvers that has so many potential solutions it takes an enormous amount of time to unravel, which slows the entire process. The researchers employed a filtering technique to simplify this step, then used machine learning to find the optimal solution for a specific type of problem.
Their data-driven approach enables a company to use its own data to tailor a general-purpose MILP solver to the problem at hand.
This new technique sped up MILP solvers between 30 and 70 percent, without any drop in accuracy. One could use this method to obtain an optimal solution more quickly or, for especially complex problems, a better solution in a tractable amount of time.

This approach could be used wherever MILP solvers are employed, such as by ride-hailing services, electric grid operators, vaccination distributors, or any entity faced with a thorny resource-allocation problem.
“Sometimes, in a field like optimization, it is very common for folks to think of solutions as either purely machine learning or purely classical. I am a firm believer that we want to get the best of both worlds, and this is a really strong instantiation of that hybrid approach,” says senior author Cathy Wu, the Gilbert W. Winslow Career Development Assistant Professor in Civil and Environmental Engineering (CEE), and a member of a member of the Laboratory for Information and Decision Systems (LIDS) and the Institute for Data, Systems, and Society (IDSS).
Wu wrote the paper with co-lead authors Siriu Li, an IDSS graduate student, and Wenbin Ouyang, a CEE graduate student; as well as Max Paulus, a graduate student at ETH Zurich. The research will be presented at the Conference on Neural Information Processing Systems.
Tough to solve
MILP problems have an exponential number of potential solutions. For instance, say a traveling salesperson wants to find the shortest path to visit several cities and then return to their city of origin. If there are many cities which could be visited in any order, the number of potential solutions might be greater than the number of atoms in the universe.
“These problems are called NP-hard, which means it is very unlikely there is an efficient algorithm to solve them. When the problem is big enough, we can only hope to achieve some suboptimal performance,” Wu explains.

An MILP solver employs an array of techniques and practical tricks that can achieve reasonable solutions in a tractable amount of time.
A typical solver uses a divide-and-conquer approach, first splitting the space of potential solutions into smaller pieces with a technique called branching. Then, the solver employs a technique called cutting to tighten up these smaller pieces so they can be searched faster.
Cutting uses a set of rules that tighten the search space without removing any feasible solutions. These rules are generated by a few dozen algorithms, known as separators, that have been created for different kinds of MILP problems.
Wu and her team found that the process of identifying the ideal combination of separator algorithms to use is, in itself, a problem with an exponential number of solutions.
“Separator management is a core part of every solver, but this is an underappreciated aspect of the problem space. One of the contributions of this work is identifying the problem of separator management as a machine learning task to begin with,” she says.
Shrinking the solution space
She and her collaborators devised a filtering mechanism that reduces this separator search space from more than 130,000 potential combinations to around 20 options. This filtering mechanism draws on the principle of diminishing marginal returns, which says that the most benefit would come from a small set of algorithms, and adding additional algorithms won’t bring much extra improvement.
Then they use a machine-learning model to pick the best combination of algorithms from among the 20 remaining options.
This model is trained with a dataset specific to the user’s optimization problem, so it learns to choose algorithms that best suit the user’s particular task. Since a company like FedEx has solved routing problems many times before, using real data gleaned from past experience should lead to better solutions than starting from scratch each time.
The model’s iterative learning process, known as contextual bandits, a form of reinforcement learning, involves picking a potential solution, getting feedback on how good it was, and then trying again to find a better solution.
This data-driven approach accelerated MILP solvers between 30 and 70 percent without any drop in accuracy. Moreover, the speedup was similar when they applied it to a simpler, open-source solver and a more powerful, commercial solver.
In the future, Wu and her collaborators want to apply this approach to even more complex MILP problems, where gathering labeled data to train the model could be especially challenging. Perhaps they can train the model on a smaller dataset and then tweak it to tackle a much larger optimization problem, she says. The researchers are also interested in interpreting the learned model to better understand the effectiveness of different separator algorithms.
This research is supported, in part, by Mathworks, the National Science Foundation (NSF), the MIT Amazon Science Hub, and MIT’s Research Support Committee. More

An interdisciplinary research team from the University of Waterloo is using artificial intelligence (AI) to identify microplastics faster and more accurately than ever before.
Microplastics are commonly found in food and are dangerous pollutants that cause severe environmental damage — finding them is the key to getting rid of them.
The research team’s advanced imaging identification system could help wastewater treatment plants and food production industries make informed decisions to mitigate the potential impact of microplastics on the environment and human health.
A comprehensive risk analysis and action plan requires quality information based on accurate identification. In search of a robust analytical tool that could enumerate, identify and describe the many microplastics that exist, project lead Dr. Wayne Parker and his team, employed an advanced spectroscopy method which exposes particles to a range of wavelengths of light. Different types of plastics produce different signals in response to the light exposure. These signals are like fingerprints that can also be employed to mark particles as microplastic or not.
The challenge researchers often find is that microplastics come in wide varieties due to the presence of manufacturing additives and fillers that can blur the “fingerprints” in a lab setting. This makes identifying microplastics from organic material, as well as the different types of microplastics, often difficult. Human intervention is usually required to dig out subtle patterns and cues, which is slow and prone to error.
“Microplastics are hydrophobic materials that can soak up other chemicals,” said Parker, a professor in Waterloo’s Department of Civil and Environmental Engineering. “Science is still evolving in terms of how bad the problem is, but it’s theoretically possible that microplastics are enhancing the accumulation of toxic substances in the food chain.”
Parker approached Dr. Alexander Wong, a professor in Waterloo’s Department of Systems Design Engineeringand the Canada Research Chair in Artificial Intelligence and Medical Imaging for assistance. With his help, the team developed an AI tool called PlasticNet that enables researchers to rapidly analyze large numbers of particles approximately 50 per cent faster than prior methods and with 20 per cent more accuracy.

The tool is the latest sustainable technology designed by Waterloo researchers to protect our environment and engage in research that will contribute to a sustainable future.
“We built a deep learning neural network to enhance microplastic identification from the spectroscopic signals,” said Wong. “We trained it on data from existing literature sources and our own generated images to understand the varied make-up of microplastics and spot the differences quickly and correctly — regardless of the fingerprint quality.”
Parker’s former PhD student, Frank Zhu, tested the system on microplastics isolated from a local wastewater treatment plant. Results show that it can identify microplastics with unprecedented speed and accuracy. This information can empower treatment plants to implement effective measures to control and eliminate these substances.
The next steps involve continued learning and testing, as well as feeding the PlasticNet system more data to increase the quality of its microplastics identification capabilities for application across a broad range of needs. More

Researchers have discovered magnetic monopoles — isolated magnetic charges — in a material closely related to rust, a result that could be used to power greener and faster computing technologies.
Researchers led by the University of Cambridge used a technique known as diamond quantum sensing to observe swirling textures and faint magnetic signals on the surface of hematite, a type of iron oxide.
The researchers observed that magnetic monopoles in hematite emerge through the collective behaviour of many spins (the angular momentum of a particle). These monopoles glide across the swirling textures on the surface of the hematite, like tiny hockey pucks of magnetic charge. This is the first time that naturally occurring emergent monopoles have been observed experimentally.
The research has also shown the direct connection between the previously hidden swirling textures and the magnetic charges of materials like hematite, as if there is a secret code linking them together. The results, which could be useful in enabling next-generation logic and memory applications, are reported in the journal Nature Materials.
According to the equations of James Clerk Maxwell, a giant of Cambridge physics, magnetic objects, whether a fridge magnet or the Earth itself, must always exist as a pair of magnetic poles that cannot be isolated.
“The magnets we use every day have two poles: north and south,” said Professor Mete Atatüre, who led the research. “In the 19th century, it was hypothesised that monopoles could exist. But in one of his foundational equations for the study of electromagnetism, James Clerk Maxwell disagreed.”
Atatüre is Head of Cambridge’s Cavendish Laboratory, a position once held by Maxwell himself. “If monopoles did exist, and we were able to isolate them, it would be like finding a missing puzzle piece that was assumed to be lost,” he said.

About 15 years ago, scientists suggested how monopoles could exist in a magnetic material. This theoretical result relied on the extreme separation of north and south poles so that locally each pole appeared isolated in an exotic material called spin ice.
However, there is an alternative strategy to find monopoles, involving the concept of emergence. The idea of emergence is the combination of many physical entities can give rise to properties that are either more than or different to the sum of their parts.
Working with colleagues from the University of Oxford and the National University of Singapore, the Cambridge researchers used emergence to uncover monopoles spread over two-dimensional space, gliding across the swirling textures on the surface of a magnetic material.
The swirling topological textures are found in two main types of materials: ferromagnets and antiferromagnets. Of the two, antiferromagnets are more stable than ferromagnets, but they are more difficult to study, as they don’t have a strong magnetic signature.
To study the behaviour of antiferromagnets, Atatüre and his colleagues use an imaging technique known as diamond quantum magnetometry. This technique uses a single spin — the inherent angular momentum of an electron — in a diamond needle to precisely measure the magnetic field on the surface of a material, without affecting its behaviour.
For the current study, the researchers used the technique to look at hematite, an antiferromagnetic iron oxide material. To their surprise, they found hidden patterns of magnetic charges within hematite, including monopoles, dipoles and quadrupoles.

“Monopoles had been predicted theoretically, but this is the first time we’ve actually seen a two-dimensional monopole in a naturally occurring magnet,” said co-author Professor Paolo Radaelli, from the University of Oxford.
“These monopoles are a collective state of many spins that twirl around a singularity rather than a single fixed particle, so they emerge through many-body interactions. The result is a tiny, localised stable particle with diverging magnetic field coming out of it,” said co-first author Dr Hariom Jani, from the University of Oxford.
“We’ve shown how diamond quantum magnetometry could be used to unravel the mysterious behaviour of magnetism in two-dimensional quantum materials, which could open up new fields of study in this area,” said co-first author Dr Anthony Tan, from the Cavendish Laboratory. “The challenge has always been direct imaging of these textures in antiferromagnets due to their weaker magnetic pull, but now we’re able to do so, with a nice combination of diamonds and rust.”
The study not only highlights the potential of diamond quantum magnetometry but also underscores its capacity to uncover and investigate hidden magnetic phenomena in quantum materials. If controlled, these swirling textures dressed in magnetic charges could power super-fast and energy-efficient computer memory logic.
The research was supported in part by the Royal Society, the Sir Henry Royce Institute, the European Union, and the Engineering and Physical Sciences Research Council (EPSRC), part of UK Research and Innovation (UKRI). More

Seeing robots made with soft, flexible parts in action appears to lower people’s anxiety about working with them or even being replaced by them.
A Washington State University study found that watching videos of a soft robot working with a person at picking and placing tasks lowered the viewers’ safety concerns and feelings of job insecurity. This was true even when the soft robot was shown working in close proximity to the person. This finding shows soft robots hold a potential psychological advantage over rigid robots made of metal or other hard materials.
“Prior research has generally found that the closer you are to a rigid robot, the more negative your reactions are, but we didn’t find those outcomes in this study of soft robots,” said lead author Tahira Probst, a WSU psychology professor.
Currently, human and rigid robotic workers have to maintain a set distance for safety reasons, but as this study indicates, proximity to soft robots could be not only physically safer but also more psychologically accepted.
“This finding needs to be replicated, but if it holds up, that means humans could work together more closely with the soft robots,” Probst said.
The study, published in the journal IISE Transactions on Occupational Ergonomics and Human Factors, did find that faster interactions with a soft robot tended to cause more negative responses, but when the study participants had previous experience with robots, faster speed did not bother them. In fact, they preferred the faster interactions. This reinforces the finding that greater familiarity increased overall comfort with soft robots.
About half of all occupations are highly likely to involve some type of automation within the next couple decades, said Probst, particularly those related to production, transportation, extraction and agriculture.

Soft robots, which are made with flexible materials like fabric and rubber, are still relatively new technology compared to rigid robots which are already widely in use in manufacturing.
Rigid robots have many limitations including their high cost and high safety concerns — two problems soft robots can potentially solve, said study co-author Ming Luo, an assistant professor in WSU’s School of Mechanical and Materials Engineering.
“We make soft robots that are naturally safe, so we don’t have to focus a lot on expensive hardware and sensors to guarantee safety like has to be done with rigid robots,” said Luo.
As an example, Luo noted that one rigid robot used for apple picking could cost around $30,000 whereas the current research and development cost for one soft robot, encompassing all components and manufacturing, is under $5,000. Also, that cost could be substantially decreased if production were scaled up.
Luo’s team is in the process of developing soft robots for a range of functions, including fruit picking, pruning and pollinating. Soft robots also have the potential help elderly or disabled people in home or health care settings. Much more development has to be done before this can be a reality, Luo said, but his engineering lab has partnered with Probst’s psychology team to better understand human-robot interactions early in the process.
“It’s good to know how humans will react to the soft robots in advance and then incorporate that information into the design,” said Probst. “That’s why we’re working in tandem, where the psychology side is informing the technical development of these robots in their infancy.”
To further test this study’s findings, the researchers are planning to bring participants into the lab to interact directly with soft robots. In addition to collecting participants self-reported surveys, they will also measure participants’ physical stress reactions, such as heart rate and galvanic skin responses, which are changes in the skin’s electrical resistance in reaction to emotional stress. More

Recent advances allow imaging of neurons inside freely moving animals. However, to decode circuit activity, these imaged neurons must be computationally identified and tracked. This becomes particularly challenging when the brain itself moves and deforms inside an organism’s flexible body, e.g. in a worm. Until now, the scientific community has lacked the tools to address the problem.
Now, a team of scientists from EPFL and Harvard have developed a pioneering AI method to track neurons inside moving and deforming animals. The study, now published in Nature Methods, was led by Sahand Jamal Rahi at EPFL’s School of Basic Sciences.
The new method is based on a convolutional neural network (CNN), which is a type of AI that has been trained to recognize and understand patterns in images. This involves a process called “convolution,” which looks at small parts of the picture — like edges, colors, or shapes — at a time and then combines all that information together to make sense of it and to identify objects or patterns.
The problem is that to identify and track neurons during a movie of an animal’s brain, many images have to be labeled by hand because the animal appears very differently across time due to the many different body deformations. Given the diversity of the animal’s postures, generating a sufficient number of annotations manually to train a CNN can be daunting.
To address this, the researchers developed an enhanced CNN featuring ‘targeted augmentation’. The innovative technique automatically synthesizes reliable annotations for reference out of only a limited set of manual annotations. The result is that the CNN effectively learns the internal deformations of the brain and then uses them to create annotations for new postures, drastically reducing the need for manual annotation and double-checking.
The new method is versatile, being able to identify neurons whether they are represented in images as individual points or as 3D volumes. The researchers tested it on the roundworm Caenorhabditis elegans, whose 302 neurons have made it a popular model organism in neuroscience.
Using the enhanced CNN, the scientists measured activity in some of the worm’s interneurons (neurons that bridge signals between neurons). They found that they exhibit complex behaviors, for example changing their response patterns when exposed to different stimuli, such as periodic bursts of odors.
The team have made their CNN accessible, providing a user-friendly graphical user interface that integrates targeted augmentation, streamlining the process into a comprehensive pipeline, from manual annotation to final proofreading.
“By significantly reducing the manual effort required for neuron segmentation and tracking, the new method increases analysis throughput three times compared to full manual annotation,” says Sahand Jamal Rahi. “The breakthrough has the potential to accelerate research in brain imaging and deepen our understanding of neural circuits and behaviors.” More

Unmanned Underwater Vehicles (UUVs) are used around the world to conduct difficult environmental, remote, oceanic, defence and rescue missions in often unpredictable and harsh conditions.
A new study led by Flinders University and French researchers has now used a novel bio-inspired computing artificial intelligence solution to improve the potential of UUVs and other adaptive control systems to operate more reliability in rough seas and other unpredictable conditions.
This innovative approach, using the Biologically-Inspired Experience Replay (BIER) method, has been published by the Institute of Electrical and Electronics Engineers journal IEEE Access.
Unlike conventional methods, BIER aims to overcome data inefficiency and performance degradation by leveraging incomplete but valuable recent experiences, explains first author Dr Thomas Chaffre.
“The outcomes of the study demonstrated that BIER surpassed standard Experience Replay methods, achieving optimal performance twice as fast as the latter in the assumed UUV domain.
“The method showed exceptional adaptability and efficiency, exhibiting its capability to stabilize the UUV in varied and challenging conditions.”
The method incorporates two memory buffers, one focusing on recent state-action pairs and the other emphasising positive rewards.

To test the effectiveness of the proposed method, researchers conducted simulated scenarios using a robot operating system (ROS)-based UUV simulator and gradually increasing scenarios’ complexity.
These scenarios varied in target velocity values and the intensity of current disturbances.
Senior author Flinders University Associate Professor in AI and Robotics Paulo Santos says the BIER method’s success holds promise for enhancing adaptability and performance in various fields requiring dynamic, adaptive control systems.
UUVs’ capabilities in mapping, imaging and sensor controls are rapidly improving, including with Deep Reinforcement Learning (DRL), which is rapidly advancing the adaptive control responses to underwater disturbances UUVs can encounter.
However, the efficiency of these methods gets challenged when faced with unforeseen variations in real-world applications.
The complex dynamics of the underwater environment limit the observability of UUV manoeuvring tasks, making it difficult for existing DRL methods to perform optimally.
The introduction of BIER marks a significant step forward in enhancing the effectiveness of deep reinforcement learning method in general.
Its ability to efficiently navigate uncertain and dynamic environments signifies a promising advancement in the area of adaptive control systems, researchers conclude.
Acknowledgements: This work was funded by Flinders University and ENSTA Bretagne with support from the Government of South Australia (Australia), the Région Bretagne (France) and Naval Group. More

Physicists at The City College of New York have developed a technique with the potential to enhance optical data storage capacity in diamonds. This is possible by multiplexing the storage in the spectral domain. The research by Richard G. Monge and Tom Delord members of the Meriles Group in CCNY’s Division of Science, is entitled “Reversible optical data storage below the diffraction limit” and appears in the journal Nature Nanotechnology.
“It means that we can store many different images at the same place in the diamond by using a laser of a slightly different color to store different information into different atoms in the same microscopic spots,” said Delord, postdoctoral research associate at CCNY. “If this method can be applied to other materials or at room temperature, it could find its way to computing applications requiring high-capacity storage.”
The CCNY research focused on a tiny element in diamonds and similar materials, known as “color centers.” These, basically, are atomic defects that can absorb light and serve as a platform for what are termed quantum technologies.
“What we did was control the electrical charge of these color centers very precisely using a narrow-band laser and cryogenic conditions” explained Delord. “This new approach allowed us to essentially write and read tiny bits of data at a much finer level than previously possible, down to a single atom.”
Optical memory technologies have a resolution defined by what’s called the “diffraction limit,” that is, the minimum diameter that a beam can be focused to, which approximately scales as half the light beam wavelength (for example, green light would have a diffraction limit of 270 nm). “So, you cannot use a beam like this to write with resolution smaller than the diffraction limit because if you displace the beam less than that, you would impact what you already wrote. So normally, optical memories increase storage capacity by making the wavelength shorter (shifting to the blue), which is why we have “Blu-ray” technology,” said Delord.
What differentiates the CCNY optical storage approach from others is that it circumvents the diffraction limit by exploiting the slight color (wavelength) changes existing between color centers separated by less than the diffraction limit. “By tuning the beam to slightly shifted wavelengths, it can be kept at the same physical location but interact with different color centers to selectively change their charges — that is to write data with sub-diffraction resolution,” said Monge, a postdoctoral fellow at CCNY who was involved in study as a PhD student at the Graduate Center, CUNY.
Another unique aspect of this approach is that it’s reversible. “One can write, erase, and rewrite an infinite number of times,” Monge noted. “While there are some other optical storage technologies also able to do this, this is not the typical case, especially when it comes to high spatial resolution. A Blu-ray disc is again a good reference example — you can write a movie in it but you cannot erase it and write another one.” More

Wearable devices that use sensors to monitor biological signals can play an important role in health care. These devices provide valuable information that allows providers to predict, diagnose and treat a variety of conditions while improving access to care and reducing costs.
However, wearables currently require significant infrastructure — such as satellites or arrays of antennas that use cell signals — to transmit data, making many of those devices inaccessible to rural and under-resourced communities.
A group of University of Arizona researchers has set out to change that with a wearable monitoring device system that can send health data up to 15 miles — much farther than Wi-Fi or Bluetooth systems can — without any significant infrastructure. Their device, they hope, will help make digital health access more equitable.
The researchers introduced novel engineering concepts that make their system possible in an upcoming paper in the journal Proceedings of the National Academy of Sciences.
Philipp Gutruf, an assistant professor of biomedical engineering and Craig M. Berge Faculty Fellow in the College of Engineering, directed the study in the Gutruf Lab. Co-lead authors are Tucker Stuart, a UArizona biomedical engineering doctoral alumnus, and Max Farley, an undergraduate student studying biomedical engineering.
Designed for ease, function and future
The COVID-19 pandemic, and the strain it placed on the global health care system, brought attention to the need for accurate, fast and robust remote patient monitoring, Gutruf said. Non-invasive wearable devices currently use the internet to connect clinicians to patient data for aggregation and investigation.

“These internet-based communication protocols are effective and well-developed, but they require cell coverage or internet connectivity and main-line power sources,” said Gutruf, who is also a member of the UArizona BIO5 Institute. “These requirements often leave individuals in remote or resource-constrained environments underserved.”
In contrast, the system the Gutruf Lab developed uses a low power wide area network, or LPWAN, that offers 2,400 times the distance of Wi-Fi and 533 times that of Bluetooth. The new system uses LoRa, a patented type of LPWAN technology.
“The choice of LoRa helped address previous limitations associated with power and electromagnetic constraints,” Stuart said.
Alongside the implementation of this protocol, the lab developed circuitry and an antenna, which, in usual LoRa-enabled devices, is a large box that seamlessly integrates into the soft wearable. These electromagnetic, electronic and mechanical features enable it to send data to the receiver over a long distance. To make the device almost imperceptible to the wearer, the lab also enables recharge of its batteries over 2 meters of distance. The soft electronics, and the device’s ability to harvest power, are the keys to the performance of this first-of-its-kind monitoring system, Gutruf said.
The Gutruf Lab calls the soft mesh wearable biosymbiotic, meaning it is custom 3D-printed to fit the user and is so unobtrusive it almost begins to feel like part of their body. The device, worn on the low forearm, stays in place even during exercise, ensuring high-quality data collection, Gutruf said. The user wears the device at all times, and it charges without removal or effort.
“Our device allows for continuous operation over weeks due to its wireless power transfer feature for interaction-free recharging — all realized within a small package that even includes onboard computation of health metrics,” Farley said.
Gutruf, Farley and Stuart plan to further improve and extend communication distances with the implementation of LoRa wireless area network gateways that could serve hundreds of square miles and hundreds of device users, using only a small number of connection points.
The wearable device and its communication system have the potential to aid remote monitoring in underserved rural communities, ensure high-fidelity recording in war zones, and monitor health in bustling cities, said Gutruf, whose long-term goal is to make the technology available to the communities with the most need.
“This effort is not just a scientific endeavor,” he said. “It’s a step toward making digital medicine more accessible, irrespective of geographical and resource constraints.” More