ABSTRACT. Relaxed decision diagrams have been successfully applied to solve combinatorial optimization problems, but their performance is known to strongly depend on the variable ordering. We propose a portfolio approach to selecting the best ordering among a set of alternatives. We consider several different portfolio mechanisms: an offline predictive model of the single best algorithm using classifiers, an online low-knowledge algorithm selection, a static uniform time-sharing portfolio, and a dynamic online time allocator. As a case study, we compare and contrast their performance on the graph coloring problem. We find that on this problem domain, the dynamic online time allocator provides the best overall performance.

ABSTRACT. We consider the longest common subsequence (LCS) problem and propose a new method for obtaining tight upper bounds on the solution length. Our method relies on the compilation of a relaxed multi-valued decision diagram (MDD) in a special way that is based on the principles of A* search. An extensive experimental evaluation on several standard LCS benchmark instance sets shows that the novel construction algorithm clearly outperforms a traditional top-down construction (TDC) of MDDs. We are able to obtain stronger and at the same time more compact relaxed MDDs than TDC and this in shorter time. For several groups of benchmark instances new best known upper bounds are obtained. In comparison to existing simple upper bound procedures, the obtained bounds are on average 14.8% better.

ABSTRACT. Combinatorial optimization has found applications in numerous fields, from transportation to scheduling and planning. The goal is to find an optimal solution among a finite set of possibilities. Most exact approaches use relaxations to derive bounds on the objective function, which are embedded within a branch-and-bound algorithm. Decision diagrams provide a new approach for obtaining bounds that, in some cases, can be significantly better than those obtained with a standard linear programming relaxation. However, it is known that the quality of the bounds achieved through this bounding method depends on the ordering of variables considered for building the diagram. Recently, a deep reinforcement learning approach was proposed to compute a high-quality variable ordering. The bounds obtained exhibited improvements, but the mechanism proposed was not embedded in a branch-and-bound solver. This paper proposes to integrate learned optimization bounds inside a branch-and-bound solver, through the combination of reinforcement learning and decision diagrams. The results obtained show that the bounds can reduce the tree search size by a factor of at least three on the maximum independent set problem.

ABSTRACT. Recent work has demonstrated that neural sequence models can successfully solve combinatorial search problems such as program synthesis and routing problems. In these scenarios, the beam search algorithm is typically used to produce a set of high-likelihood candidate sequences that are evaluated to determine if they satisfy the goal criteria. If none of the candidates satisfy the criteria, the beam search can be restarted with a larger beam size until a satisfying solution is found. Inspired by works in combinatorial and heuristic search, we investigate whether heavy-tailed behavior can be observed in the search effort distribution of complete beam search in goal-oriented neural sequence decoding. We analyze four goal-oriented decoding tasks and find that the search effort of beam search exhibits fat- and heavy-tailed behavior. Following previous work on heavy-tailed behavior in search, we propose a randomized restarting variant of beam search. We conduct extensive empirical evaluation, comparing different randomization techniques and restart strategies, and show that the randomized restarting variant solves some of the hardest instances faster and outperforms the baseline.

ABSTRACT. The COVID-19 pandemic has forced educational institutions to make significant changes to safeguard the health and safety of their students and teachers. One of the most effective measures to reduce virus transmission is partitioning students into discrete cohorts.

In primary and middle schools, it is easy to create these cohorts (also known as "learning groups"), since students in each grade take the same set of required courses. However, in high schools, where there is much diversity in course preferences among individual students, it is extremely challenging to optimally partition students into cohorts to ensure that every section of a course only contains students from a single cohort.

In this paper, we define the Student Cohort Partitioning Problem, where our goal is to optimally assign cohorts to students and course sections, to maximize students being enrolled in their desired courses. We solve this problem by modeling it as an integer linear program, and apply our model to generate the Master Timetable for a Canadian all-boys high school, successfully enrolling students in 87% of their desired courses, including 100% of their required courses. We conclude the paper by explaining how our model can benefit all educational institutions that need to create optimal student cohorts when designing their annual timetable.

ABSTRACT. At the beginning of the pandemic last year some hospitals had to change their physician schedules to take into account infection risks and potential quarantines for personnel. This was especially important for hospitals that care for high-risk patients, like the St. Anna Children's Hospital in Vienna, which is a tertiary care center for pediatric oncology. It was very important to develop solving methods for this complex problem in a very short time. We relied on constraint solving technology which proved to be very useful in such critical situations.

In this paper we present a constraint model that includes the variety of requirements that are needed to ensure day-to-day operations as well as the additional constraints imposed by the pandemic situation. Physicians with different skills are assigned to various stations in several shift configurations. We introduce an innovative set of grouping constraints to partition the staff, with the intention to easily isolate a small group in case of an infection. The produced schedules also keep part of the staff as backup to replace personnel in quarantine.

In our case study, we evaluate and compare our proposed model on several state-of-the-art solvers. Our approach could successfully produce a high-quality schedule for the considered real-world planning scenario, also compared to solutions found by human planners with considerable effort.

ABSTRACT. For personnel scheduling problems, mixed-integer linear programming formulations based on state-expanded networks in which nodes correspond to rule-related states often have very strong LP relaxations. A challenge of these formulations is that they typically give rise to large model instances. If one is willing to trade in optimality for computation time, a way to reduce the size of the model instances is to heuristically remove unpromising nodes and arcs from the state-expanded networks.

In this paper, we propose to employ machine learning models for guiding the reduction of state-expanded networks for multi-activity shift scheduling problems. More specifically, we train a model that predicts the flow through a node from its state attributes, and based on this prediction, we decide whether to keep a node or not. In experiments with a well-known set of multi-activity shift scheduling instances, we show that our approach substantially reduces both the size of the model instances and their solution times while still obtaining optimal solutions for the vast majority of the instances. The results indicate that our approach is competitive with a state-of-the art Lagrangian-relaxation-based matheuristic for multi-activity shift scheduling problems.

ABSTRACT. The Volleyball Nations League is the elite annual international competition within volleyball, with the sixteen best nations per gender contesting the trophy in a tournament that spans over $6$ weeks. The first five weeks contain a single round robin tournament, where matches are played in different venues across the globe. As a result of this setup, there is a large discrepancy between the travel burdens of meeting teams, which is a disadvantage for the teams that have to travel a lot. We analyse this problem, and find that it is related to the well-known Social Golfer Problem. We propose a decomposition approach for the resulting optimization problem, leading to the so-called Venue Assignment Problem. Using integer programming methods, we find, for real-life instances, the fairest schedules with respect to the difference in travel distance.

ABSTRACT. Same-day delivery problems are challenging stochastic vehicle routing problems, where dynamically arriving orders have to be delivered to customers within a short time while minimizing costs. In this work, we consider the short-horizon planning of a problem variant where every order has to be delivered with the goal to minimize delivery tardiness, travel times, and labor costs of the drivers involved. Stochastic information as spatial and temporal order distributions is available upfront. Since timely routing decisions have to be made over the planning horizon of a day, the well-known sampling approach from the literature for considering expected future orders is not suitable due to its high runtimes. To mitigate this, we suggest to use a surrogate function for route durations that predicts the future delivery duration of the orders belonging to a route at its planned starting time. This surrogate function is directly used in the online optimization replacing the myopic current route duration. The function is trained offline by data obtained from running full day-simulations, sampling and solving a number of scenarios for each route at each decision point in time. We consider three different models for the surrogate function and compare with the classical sampling approach on challenging real-world inspired artificial instances. Results indicate that the new approach can outperform the sampling approach by orders of magnitude regarding runtime while significantly reducing travel costs in most cases.

ABSTRACT. Coordinating the mobile production fleet in underground mines becomes increasingly important as the machines are more and more automated. We present a scheduling approach that applies to several of the most important production methods used in underground mines. Our algorithm combines constraint programming with a large neighborhood search strategy that dynamically adjusts the neighborhood size. The resulting algorithm is complete and able to rapidly improve constructed schedules in practice. In addition, it has important benefits when it comes to the acceptance of the approach in real-life operations. Our approach is evaluated on both public and private industrial problem instances representing different mines and different production methods. We find significant improvements over the current industrial practice.

ABSTRACT. In this work, we consider a pipe routing problem where the goal is to connect an input configuration to an output configuration by using a pipe composed of a succession of straight sections and bends. The pipe is routed within a 3D continuous space divided into non-regular convex cells in order to take potential obstacles into account. Our objective is to consider several non-standard features such as the need to deal with a set of bends restricted to a bend catalog, which can contain both orthogonal and non-orthogonal bends, but also to deal with pipes that can have a rectangular section, which makes the pipe orientation important. An approach is introduced to automate the design of such pipe systems and help designers to manage the high number of constraints involved. Basically, this approach formulates the pipe routing problem as a shortest path problem in the space of routing plans, where a routing plan is specified by the parts composing the pipe and by geometrical constraints imposed on these parts. The problem is then solved using weighted A* search combined with a linear program that quickly evaluates the feasibility and the cost of a routing plan. The paper shows that the approach obtained has the capacity to solve realistic instances inspired by industrial problems.

ABSTRACT. This work proposes a novel matheuristic algorithm for solving the Production Routing Problem (PRP). The PRP is a hard-to-solve combinatorial optimization problem with numerous practical applications in the field of freight transportation, logistics and supply chain management. The generic PRP variant examined describes the situation in which a manufacturer of a product is responsible for production and replenishment of customers inventories over a given time horizon, ensuring that no stock-outs occur. The decision-maker is responsible for deciding: i) the time periods at which the production takes place, ii) the product quantities that are produced, iii) the timing for replenishing each customer inventory, iv) the associated replenishment quantity and v) the routing of all customer services, with respect to the minimization of the total cost of the system.

The contribution lies on the benefits enabled by integrated logistics models, the high complexity of PRP and the effectiveness of infeasible space search. In specific, the paper presents a novel matheuristic algorithm that oscillates between feasible and infeasible space of the basic PRP model. A new PRP two-commodity flow formulation is proposed along with adapted and new valid inequalities. The proposed matheuristic scheme is mainly based on a hybrid local search framework equipped with MIP and LP procedures to tackle various subproblems. The production-distribution decisions are taken by solving a PRP relaxation which considers approximated routing costs for customer visits. Afterwards, a heuristic GRASP algorithm completes the partial solution with routing information. The complete solution is then iteratively improved by a matheuristic framework. The matheuristic oscillates between infeasible and feasible space by allowing vehicle capacity infeasibilities and applying an infeasibility restoration MIP procedure, respectively.

Extensive computational experiments have been conducted on 1530 well-known PRP instances to analyze the proposed algorithm performance and to access its effectiveness. To motivate the proposed algorithm design, detailed experiments on the infeasible space contribution are provided. Finally, analytic comparisons of the proposed algorithm results against state-of-the-art PRP methodologies are drawn. Computational experiments demonstrate that the infeasibility space exploration significantly contributes to the quality of the final solutions. The results obtained by the proposed matheuristic outperform the known results by matching or generating new solutions for the majority of the instances examined. More specifically, for 1440 small-medium and 90 large problem instances, our algorithm matched or improved the best known solutions for 999 and 55 test cases, respectively. More precisely, 594 and 55 of these are new best solutions.