MAO group - Models and Algorithms for Optimization

We develop mathematical models and algorithms for optimizing complex problems and supporting decisions in many application settings (logistics and transportation, production, health-care, energy, and finance). Our applied methodologies range from classical Operational Research techniques (exact and heuristic) to modern integrations with Machine Learning and parallel computing.

Kernel Search

#matheuristic #generalpurpose

Kernel Search is a general-purpose matheuristic, initially proposed in Angelelli et al. (2010) and Angelelli et al. (2012), that focuses on solving complex mixed integer programming problems using limited resources and time. The starting point is usually the solution of the continuous relaxation of the original problem. This solution is used to identify an initial kernel set of variables and to partition the remaining ones into a predefined number of groups called buckets. Kernel set represents the set of variables that, with higher probability, will take a value larger than zero in the integer optimal solution. They include all variables taking a positive value in the continuous relaxation optimal solution plus some additional variables selected among those with lower reduced costs (in absolute value).
An initial solution is then obtained by tackling a restricted integer problem formulated on the initial kernel set of variables and by setting to zero all the remaining ones. Afterwards, a sequence of MILP subproblems is solved by means of a MILP solver, each one restricted to a subset of variables including the ones in the kernel set plus the ones belonging to the current bucket. To improve efficiency, an additional constraint imposing the selection of at least one variable from the current bucket is added. The best solution value found while solving each subproblem is used as cut-off value for the subsequent ones. Variables belonging to a bucket and selected in the solution of the corresponding subproblem enter the kernel set. The size of the kernel set increases monotonically.
The goal of solving each restricted subproblem is two-fold: possibly finding a better feasible solution, and identifying further variables to insert into the kernel set. The idea is that the final kernel set should contain most of (hopefully all) the variables that will be selected in an optimal solution. Although restricted, it might be the case that solving the subproblems comes out to be computationally cumbersome. A solution time limit can be set to tackle subproblems. The best feasible solution, possibly the optimal one (if any is found), is provided as output. If one subproblem is proven to be infeasible, the next one is considered. The algorithm stops as soon as the subproblem constructed on the last bucket is tackled.
The iterative variant of the method, called Iterative Kernel Search, allows to scroll the buckets more than once. As soon as the last bucket has been considered, provided that a new solution has been found and the kernel set has been updated, the method restarts from the first bucket until no new variables enter the kernel set.

References

• Angelelli, E., Mansini, R., Speranza, M.G., 2010. Kernel search: A general heuristic for the multi-dimensional knapsack problem. Computers & Operations Research 37, 2017-2026. link
• Angelelli, E., Mansini, R., Speranza, M.G., 2012. Kernel search: A new heuristic framework for portfolio selection. Computational Optimization and Applications 51, 345-361.link
• Gobbi A., Manerba D., Mansini R., Zanotti R., 2019. A Kernel Search for a Patient Satisfaction-oriented Nurse Routing Problem with Time-Windows, IFAC-PapersOnLine. link
• Hanafi S., Mansini R., Zanotti R., 2020. The multi-visit team orienteering problem with precedence constraints. European Journal of Operational Research 282 (2), 515-529. link
• Lamanna L., Mansini R., Zanotti R., 2021. A two-phase kernel search variant for the multidimensional multiple-choice knapsack problem, European Journal of Operational Research. link

Resources

• Hanafi S., Mansini R., Zanotti R. Multi-visit Clustered Team Orienteering Problem. Odysseus 2018. Presentation
• Mansini R., Zanotti R. Hybridizing Kernel Search. ODS 2018. Presentation
• Mansini R., Zanotti R. Enhanced Kernel Search applied to the Multidimensional Multiple-Choice Knapsack Problem. EURO-ALIO 2018. Presentation
• Mansini R. Kernel Search: a simple heuristic framework for MILP problems. Trento, 2018. Presentation
• Mansini R., Ghiani G., Guerriero E., Zanotti R. A Kernel Search Approach for the Time-Dependent Rural Postman Problem. ODS 2019. Presentation

Logistics, Transportation, Vehicle / Arc Routing Problems (VRPs/ARPs)

#logistics #vrp #arp #sustainability

Optimization of distribution/procurement logistics and transportation processes, with a particular focus on sustainability and emerging technologies/paradigms as well as on the health-care sector. Profits maximization, costs control, and improvement operational efficiencies in static or dynamic, deterministic or stochastic routing problems subject to real-life constraints such as time-windows, heterogeneous vehicle fleet, orders with multiple pick-up and delivery locations, split deliveries.

Some studied problems are the Traveling Purchaser Problem (TPP) and its variants (multi-vehicle, dynamic, stochastic), supplier selection and procurement problems (Total Quantity Discount problem, shipper's lane selection), location-allocation problems, Nurse Routing Problems, and other VRPs (time-dependent, pickup and delivery, Team Orienteering). Finally, classical or new ARPs (directed profitable Rural Postman Problem, undirected capacitated ARP with profits) are studied and applied in various contexts such as street sweeping, snow plowing, garbage collection, mail delivery, school bus routing.

Scheduling problems

#scheduling #production #online

Optimization of single or multi-machine job scheduling, task allocation, and timetabling problems, subject to operative constraints such as availabilities, incompatibilities, and precedencies.

Some studied problems are the scheduling of surgeries and personnel for surgical operating rooms, single-machine job scheduling with stochastic setup and processing times, and on-line production re-scheduling.

Combinatorial Optimization problems (COPs)

#knapsack #TSP #GISP #BACOP

Study and improvement of solution approaches for classical COPs and their variants, such as TSP, bin packing, knapsack 0-1, matching problems, and so on.

Some studied problems are the Multidimensional Multiple-choice Knapsack Problem, the Subset-Sum Problem, the Generalized Independent Set Problem, and backup covering problems.

Finance problems

#portfolio #indextracking #cvar

Optimization approaches and scenarios generation techniques for single or multi-period portfolio selection, rebalancing, and index tracking problems with real features such as transaction costs, minimum transaction lots, threshold on investment, cardinality constraints, logical or decision dependency constraints. LP-computable risk-management models based on the most recent achievements in portfolio theory, risk, safety, and ratio measures (MAD, GMD, CVaR).