Planetary remote sensing missions are critical for advancing our understanding of extraterrestrial systems. They operate in highly uncertain environments where reliability and resolution are not always guaranteed, often compromising data analysis and scientific outcomes. In this paper, we consider the challenging task of estimating the quality of the signal acquired by MARSIS, the subsurface sounder aboard ESA’s Mars Express mission, which aims to map the presence of liquid water beneath the Martian surface. Quality estimation has a strategic impact on the scheduling of MARSIS observations, since the radar operates with strict constraints that greatly limit the number and size of observation opportunities available per day. Thus, maximizing the quality of scheduled observations becomes a crucial factor in reducing resource utilization and increasing the coverage of the target areas in search of liquid water. To this end, in a previous research we proposed a predict-then-optimize approach, which included a neural network regressor to predict signal quality achievable by future observation opportunities, based on contextual features. In this work, we advance the methodology by applying explainable artificial intelligence techniques that allow domain experts to interpret the results, by enhancing the comprehension of the physical phenomena that have an impact on signal acquisition. Specifically, we applied a SHAP analysis to the neural network predictions and trained an Explainable Boosting Machine (EBM) to provide interpretable models. We then analyzed and compared the results with existing domain knowledge, uncovering promising new avenues for investigation and highlighting limitations in the current dataset construction.

This study investigates the effectiveness of quantum methods in tackling the cubic knapsack problem (CKP). The CKP is not only NP-hard but also extremely difficult to solve in practice. Benchmark instances of small size (including some with only 60 items) remain unsolved to proven optimality. We solve the CKP using the latest Digital Annealer (DA) prototype, an extended Ising machine available through the Quantum-Inspired Integrated Optimization (QIIO) service on Fujitsu's Kozuchi platform. Specifically, we propose two formulations: a higher-order unconstrained binary optimization (HUBO) and a quadratic unconstrained binary optimization. The latter is derived by reformulating the HUBO model into an equivalent quadratic form. These models are solved using the QIIO solver and compared with three state-of-the-art algorithms, a greedy heuristic, and two mixed integer programs. Additionally, we introduce a postprocessing heuristic to ensure the feasibility of solutions generated by the DA solver, as within short time limits, it does not always produce feasible solutions. Computational experiments are conducted on instances with up to 200 items and varying densities of nonzero objective coefficients. The results indicate that the HUBO formulation is highly competitive with state-of-the-art algorithms, achieving the best new solutions for six large instances.

The microservices architecture has transformed application development by providing scalability, flexibility, and resilience. However, as organizations scale their infrastructure, deploying microservices across multiple clusters - whether for fault tolerance, geographic distribution, or workload optimization — presents several challenges. Efficient orchestration in these multi-cluster environments is essential to ensure seamless service provisioning, workload distribution, and inter-cluster communication. In this paper, we propose an extension of the OASIS TOSCA standard to support the need of application owners to define deployment schemes that enable them to distribute application components across multiple clusterized environments. To test the viability of the proposed extension, we set up a small-scaled, multi-cluster environment powered with Kubernetes and employed an orchestrator of microservice-based applications that implements the mentioned capability. For the test purpose, a real application from the logistics domain was employed.

Abstract This paper addresses a real‐world multi‐period orienteering problem arising in a large Italian company that needs to patrol an area in order to provide security services to a set of customers. Each customer requires different services on a weekly basis. Some services are mandatory, while others are optional. It might be impossible to perform all optional services, and each of them is assigned a score when performed. The challenge is to determine a set of routes, one per day, that maximizes a weighted sum of the total collected score and total working time, while meeting several operational constraints, including hard time windows, maximum riding time, minimum number of services performed, and minimum time between two consecutive visits for the same service at the same customer. To solve the problem, we propose an iterated local search that invokes at each iteration an inner variable neighborhood descent procedure. Computational tests performed on a large number of real‐world instances prove that the developed algorithm is very efficient, and finds in a short time solutions that are consistently better than those produced by a mathematical model, and those in use at the company.

In the Tutor Allocation Problem, the objective is to assign a set of tutors to a set of workshops in order to maximize tutors’ preferences. The problem is solved every year by many universities, each having its own specific set of constraints. In this work, we study the tutor allocation in the School of Mathematics at the University of Edinburgh, and solve it with an integer linear programming model. We tested the model on the 2019/2020 case, obtaining a significant improvement with respect to the manual assignment in use and we showed that such improvement could be maintained while optimizing other key metrics such as load balance among groups of tutors and total number of courses assigned. Further tests on randomly created instances show that the model can be used to address cases of broad interest. We also provide meaningful insights on how input parameters, such as the number of workshop locations and the length of the tutors’ preference list, might affect the performance of the model and the average number of preferences satisfied.

We consider binary integer programming problems with the min-max regret objective function under interval objective coefficients. We propose a heuristic framework, the iterated dual substitution (iDS) algorithm, which iteratively invokes a dual substitution heuristic and excludes from the search space any solution already checked in previous iterations. In iDS, we use a best scenario–based lemma to improve performance. We apply iDS to four typical combinatorial optimization problems: the knapsack problem, the multidimensional knapsack problem, the generalized assignment problem, and the set covering problem. For the multidimensional knapsack problem, we compare the iDS approach with two algorithms widely used for problems with the min-max regret criterion: a fixed-scenario approach, and a branch-and-cut approach. The results of computational experiments on a broad set of benchmark instances show that the proposed iDS approach performs best on most tested instances. For the knapsack problem, the generalized assignment problem, and the set covering problem, we compare iDS with state-of-the-art results. The iDS algorithm successfully updates best-known records for a number of benchmark instances. Summary of Contribution: This paper proposes a heuristic framework for binary integer programming (BIP) problems with the min-max regret objective function under interval objective coefficients. We selected four representative NP-hard combinatorial optimization problems: the knapsack problem, the multidimensional knapsack problem, the set covering problem, and the generalized assignment problem. We show the effectiveness and efficiency of the approach by comparing with state-of-the-art results.

The two-dimensional bin packing problem calls for packing a set of rectangular items into a minimal set of larger rectangular bins. Items must be packed with their edges parallel to the borders of the bins, cannot be rotated, and cannot overlap among them. The problem is of interest because it models many real-world applications, including production, warehouse management, and transportation. It is, unfortunately, very difficult, and instances with just 40 items are unsolved to proven optimality, despite many attempts, since the 1990s. In this paper, we solve the problem with a combinatorial Benders decomposition that is based on a simple model in which the two-dimensional items and bins are just represented by their areas, and infeasible packings are imposed by means of exponentially many no-good cuts. The basic decomposition scheme is quite naive, but we enrich it with a number of preprocessing techniques, valid inequalities, lower bounding methods, and enhanced algorithms to produce the strongest possible cuts. The resulting algorithm behaved very well on the benchmark sets of instances, improving on average on previous algorithms from the literature and solving for the first time a number of open instances. Summary of Contribution: We address the two-dimensional bin packing problem (2D-BPP), which calls for packing a set of rectangular items into a minimal set of larger rectangular bins. The 2D-BPP is a very difficult generalization of the standard one-dimensional bin packing problem, and it has been widely studied in the past because it models many real-world applications, including production, warehouse management, and transportation. We solve the 2D-BPP with a combinatorial Benders decomposition that is based on a model in which the two-dimensional items and bins are represented by their areas, and infeasible packings are imposed by means of exponentially many no-good cuts. The basic decomposition scheme is quite naive, but it is enriched with a number of preprocessing techniques, valid inequalities, lower bounding methods, and enhanced algorithms to produce the strongest possible cuts. The algorithm we developed has been extensively tested on the most well-known benchmark set from the literature, which contains 500 instances. It behaved very well, improving on average upon previous algorithms, and solving for the first time a number of open instances. We analyzed in detail several configurations before obtaining the best one and discussed several insights from this analysis in the manuscript.

Several fields of application:-Urban applications -

We study pseudo-polynomial formulations for the classical bin packing and cutting stock problems. We first propose an overview of dominance and equivalence relations among the main pattern-based and pseudo-polynomial formulations from the literature. We then introduce reflect, a new formulation that uses just half of the bin capacity to model an instance and needs significantly fewer constraints and variables than the classical models. We propose upper- and lower-bounding techniques that make use of column generation and dual information to compensate reflect weaknesses when bin capacity is too high. We also present nontrivial adaptations of our techniques that solve two interesting problem variants, namely the variable-sized bin packing problem and the bin packing problem with item fragmentation. Extensive computational tests on benchmark instances show that our algorithms achieve state of the art results on all problems, improving on previous algorithms and finding several new proven optimal solutions.

The capacitated p-center problem requires to select p facilities from a set of candidates to service a number of customers, subject to facility capacity constraints, with the aim of minimizing the maximum distance between a customer and its associated facility.The problem is well known in the field of facility location, because of the many applications that it can model.In this paper, we solve it by means of search algorithms that iteratively seek the optimal distance by solving tailored subproblems.We present different mathematical formulations for the subproblems and improve them by means of several valid inequalities, including an effective one based on a 0-1 disjunction and the solution of subset sum problems.We also develop an alternative search strategy that finds a balance between the traditional sequential search and binary search.This strategy limits the number of feasible subproblems to be solved and, at the same time, avoids large overestimates of the solution value, which are detrimental for the search.We evaluate the proposed techniques by means of extensive computational experiments on benchmark instances from the literature and new larger test sets.All instances from the literature with up to 402 vertices and integer distances are solved to proven optimality, including 13 open cases, and feasible solutions are found in 10 minutes for instances with up to 3038 vertices.

Cutting and packing (C&P) is a fundamental research area that models a large number of managerial and industrial optimization issues. A solution to a C&P problem basically consists of a set of one-dimensional or multidimensional items packed in/cut from one or more bins, by satisfying problem constraints and minimizing a given objective function. Normal patterns are a well-known C&P technique used to build solutions where each item is aligned to the bottom of the bin along each dimension. They are used in several C&P techniques because they can reduce the search space while preserving optimality, but their limit is that their number grows consistently when number of items and size of the bin increase. In this paper we propose a new set of patterns, called meet in the middle, that preserves optimality and leads to several interesting results. Their computation is achieved with the same time complexity as that of the normal patterns, but their number is never higher, and in practical applications it frequently shows reductions of about 50%. These new patterns are applied to improve some exact state-of-the-art C&P techniques, including arc-flow formulations, combinatorial branch-and-bound algorithms, and mixed-integer linear programs. The efficacy of the improved techniques is assessed by extensive computational tests on a number of relevant applications. The online appendix is available at https://doi.org/10.1287/ijoc.2018.0806 .

We consider a generalization of the 0–1 knapsack problem in which the profit of each item can take any value in a range characterized by a minimum and a maximum possible profit. A set of specific profits is called a scenario. Each feasible solution associated with a scenario has a regret, given by the difference between the optimal solution value for such scenario and the value of the considered solution. The interval min–max regret knapsack problem (MRKP) is then to find a feasible solution such that the maximum regret over all scenarios is minimized. The problem is extremely challenging both from a theoretical and a practical point of view. Its decision version is complete for the second level of the polynomial hierarchy hence it is most probably not in 𝒩𝒫. In addition, even computing the regret of a solution with respect to a scenario requires the solution of an 𝒩𝒫-hard problem. We examine the behavior of classical combinatorial optimization approaches when adapted to the solution of the MRKP. We introduce an iterated local search approach and a Lagrangian-based branch-and-cut algorithm and evaluate their performance through extensive computational experiments.

The double traveling salesman problem with multiple stacks is a variant of the pickup and delivery traveling salesman problem in which all pickups must be completed before any delivery. In addition, items can be loaded on multiple stacks in the vehicle, and each stack must obey the last-in-first-out policy. The problem consists of finding the shortest Hamiltonian cycles covering all pickup and delivery locations while ensuring the feasibility of the loading plan. We formulate the problem as two traveling salesman problems linked by infeasible path constraints. We also introduce several strengthenings of these constraints, which are used within a branch-and-cut algorithm. Computational results performed on instances from the literature show that the algorithm outperforms existing exact algorithms. Instances with up to 28 requests (58 nodes) have been solved to optimality.

We consider a particular bin packing problem in which some pairs of items may be in conflict and cannot be assigned to the same bin. The problem, denoted as the bin packing problem with conflicts, is of practical and theoretical interest because of its many real-world applications and because it generalizes both the bin packing problem and the vertex coloring problem. We present new lower bounds, upper bounds, and an exact approach, based on a set covering formulation solved through a branch-and-price algorithm. We investigate the behavior of the proposed procedures by means of extensive computational results on benchmark instances from the literature.

Abstract In the Traveling Salesman Problem with Pickup and Delivery (TSPPD) a single vehicle must serve a set of customer requests, each defined by an origin location where a load must be picked up, and a destination location where the load must be delivered. The problem consists of determining a shortest Hamiltonian cycle through all locations while ensuring that the pickup of each request is performed before the corresponding delivery. This article addresses a variant of the TSPPD in which pickups and deliveries must be performed according to a Last‐In First‐Out (LIFO) policy. We propose three mathematical formulations for this problem and several families of valid inequalities which are used within a branch‐and‐cut algorithm. Computational results performed on test instances from the literature show that most instances with up to 17 requests can be solved in less than 10 min, whereas the largest instance solved contains 25 requests. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

Given a set of jobs with associated processing times, and a set of identical machines, each of which can process at most one job at a time, the parallel machine scheduling problem is to assign each job to exactly one machine so as to minimize the maximum completion time of a job. The problem is strongly NP-hard and has been intensively studied since the 1960s. We present a metaheuristic and an exact algorithm and analyze their average behavior on a large set of test instances from the literature. The metaheuristic algorithm, which is based on a scatter search paradigm, computationally proves to be highly effective and capable of solving to optimality a very high percentage of the publicly available test instances. The exact algorithm, which is based on a specialized binary search and a branch-and-price scheme, was able to quickly solve to optimality all remaining instances.

Abstract This article addresses the well‐known Capacitated Vehicle Routing Problem (CVRP), in the special case where the demand of a customer consists of a certain number of two‐dimensional weighted items. The problem calls for the minimization of the cost of transportation needed for the delivery of the goods demanded by the customers, and carried out by a fleet of vehicles based at a central depot. In order to accommodate all items on the vehicles, a feasibility check of the two‐dimensional packing (2L) must be executed on each vehicle. The overall problem, denoted as 2L‐CVRP, is NP‐hard and particularly difficult to solve in practice. We propose a Tabu Search algorithm, in which the loading component of the problem is solved through heuristics, lower bounds, and a truncated branch‐and‐bound procedure. The effectiveness of the algorithm is demonstrated through extensive computational experiments. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008

for the Vehicle Routing Problem with Two-Dimensional Loading Constraints" by M. Gendreau et al., which appeared in the January issue of Networks (Networks 51 (2008), 4-18), the last author's name was misspelled. Silvano Martello's

Abstract We consider a combination of the capacitated vehicle routing problem and a class of additional loading constraints involving a parallel machine scheduling problem. The work is motivated by a real‐world transportation problem occurring to a wood‐products retailer, which delivers its products to a number of customers in a specific region. We solve the problem by means of two different metaheuristics algorithms: a Tabu Search and an Ant Colony Optimization. Extensive computational results are given for both algorithms, on instances derived from the vehicle routing literature and on real‐world instances. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(4), 294–307 2007