We present a new flow-based formulation for identical parallel machine scheduling with a regular objective function and without idle time.  The formulation is constructed with the help of a decision diagram that represents all job sequences that respect specific ordering rules. These rules rely on a partition of the planning horizon into, generally non-uniform, periods and do not exclude all optimal solutions, but they constrain solutions to adhere to a canonical form.  The new formulation has numerous variables and constraints, and hence we apply a Dantzig-Wolfe decomposition in order to compute the linear programming relaxation in reasonable time; the resulting lower bound is stronger than the bound from the classical time-indexed formulation. We develop a branch-and-price framework that solves several instances from the literature for the first time. We compare the new formulation with the time-indexed and arc-time-indexed formulation by means of a series of computational experiments.

Slides

Column elimination is an exact algorithm to solve discrete optimization problems of a particular form. The problem is to find a minimum cost subset of sequences from a feasible set of sequences with additional constraints over the feasible subsets. We model the problem by constructing a dynamic program that represents the feasible set of sequences, and formulating a network flow model over the dynamic program. The exact formulation can be very large, so column elimination starts with a compact relaxation of the dynamic program and iterates between solving a relaxation of the network flow model and refining the dynamic program to remove infeasible sequences in the optimal solution to the relaxation. We use the method to solve open instances of the Graph Multicoloring problem, Vehicle Routing Problem with Time Windows, and the Pickup and Delivery Problem with Time Windows.

We investigate the following problem: given two finite point sets X and Y, what is the least number of facets of a polyhedron that contains all points of X and no points of Y? This quantity is called the relaxation complexity of X with respect to Y, denoted rc(X,Y), and computing it is known to be NP-hard. It can be related to the least number of constraints needed to model variable relations in an integer program without adding additional variables. We cast the problem of finding rc(X,Y) as a coloring problem on a hypergraph with vertex set Y and edges being formed by the subsets of Y that cannot simultaneously be separated from X with a single hyperplane. To color this hypergraph, we build on and generalize an existing column elimination algorithm for coloring ordinary graphs by Van Hoeve [Mathematical Programming, 192, 631 (2022)].

The column elimination algorithm uses a decision diagram to provide a compact representation of a superset of all the independent sets in the hypergraph. Iteratively, a candidate solution is created that covers every point of Y with a set from the diagram. Such coloring is improper when a color class contains a hyperedge. The difficulty in our application is that the hypergraphs may have exponentially many edges, which is why they are dynamically generated. The edges are used to iteratively refine the decision diagram until a feasible optimal solution is found. We compare an implementation of the column elimination algorithm with an existing column generation algorithm on a set of concrete problem instances.

Finding high-quality bounds is key to devising efficient exact solution approaches for Discrete Optimization (DO) problems. To this end, Decision Diagrams (DDs) provide strong and generic bounding mechanisms. This paper focuses on so-called relaxed DDs which, by merging nodes, over-approximate the solution space of DO problems and provide dual bounds the quality of which hinges upon the ordering of the variables in the DD compilation and on the selection of the nodes to merge. Addressing the Maximum Independent Set Problem, we present a novel dynamic variable ordering strategy relying on induced subgraphs of the original graph, and a new tie-based merge heuristic. In a set of computational experiments, we show that our strategies yield much stronger bounds than the standard state-of-the-art approaches. Furthermore, implementing our heuristics in a DD-based branch-and-bound, we reduce the solution times by around 33% on average and by more than 50% on hard instances.

I will present a dynamic programming model for the Tool Switching Problem, which combines elements of both sequencing and machine configuration. This problem becomes particularly challenging to solve to optimality when the number of jobs exceeds 25 and 10 tools. I will discuss our preliminary results to solving this problem using the decision diagram framework and variants of the A* algorithm. We also compare our results with state-of-the-art methods, including a Mixed Integer Programming (MIP) model and a Branch-and-Bound approach.

This work is in collaboration with Emma Legrand and Daniele Catanzaro.

The Travelling Salesman Problem (TSP) may be solved by searching for a best path in a state-transition graph which is derived from Bellman equations, and this state-transition graph may be easily extended to solve the TSP with Time-windows (TSPTW), where arrival times are constrained to belong to given time intervals, or with time-dependent cost functions, where travel times depend on departure times. In this talk, we will provide an overview of exact and anytime extensions of A* which may be used to search for best paths in state-transition graphs, and show how to combine them with local search (in order to faster find solutions of higher quality) and with bounding and time window constraint propagation (in order to filter the search space). We will present an experimental comparison with state-of-the-art approaches for solving the TSPTW and the time-dependent TSPTW.

Two-stage stochastic programs (2SPs) with binary recourse are challenging to solve, and efficient solution methods for such problems have been limited. Leveraging the combinatorial nature of binary programs, we convexify the second-stage problems using binary decision diagrams (BDDs) to make the problem amenable to the Benders decomposition algorithm. More specifically, we first generalize an existing BDD-based approach to allow settings where logical expressions of the first-stage solutions enforce constraints in the second stage, making it applicable to a wide array of problems. We also propose a complementary problem where second-stage objective coefficients are impacted by logical expressions of the first-stage decisions, and develop a distinct BDD-based algorithm to solve this novel problem class. In the two alternative settings, while convexifying the second-stage problems, we parametrize either the arc costs or capacities of the BDDs with first-stage solutions. We further extend this work by incorporating conditional value-at-risk, and we propose, to our knowledge, the first decomposition method for 2SPs with binary recourse and a risk measure. We apply these methods to a novel stochastic dominating set problem and present numerical results to demonstrate the effectiveness of the proposed methods.

Integer bilevel programs are notoriously difficult to solve due to the absence of strong and efficiently computable relaxations. This work introduces a novel single-level reformulation of these programs by leveraging a network flow-based representation of the follower’s value function, utilizing decision diagrams and linear programming duality. Additionally, we explain how to derive dual bounds from restricted decision diagrams, reduce the size of the resulting reformulation, and address the pessimistic version of the problem. Finally, we compare our method against state-of-the-art bilevel programming solvers, demonstrating competitive performance, particularly for problem instances where the follower’s problem exhibits a combinatorial structure suitable for decision diagrams.

Many real-world scenarios involve solving bilevel optimization problems in which there is an outer discrete optimization problem, and an inner problem involving expensive or black-box computation. This arises in space-time dependent variants of the Traveling Salesman Problem, such as when planning space missions that visit multiple astronomical objects. Planning these missions presents significant challenges due to the constant relative motion of the objects involved. There is an outer combinatorial problem of finding the optimal order to visit the objects and an inner optimization problem that requires finding the optimal departure time and trajectory to travel between each pair of objects. The constant motion of the objects complicates the inner problem, making it computationally expensive.

This work introduces a novel framework utilizing decision diagrams (DDs) and a DD-based branch-and-bound technique, Peel-and-Bound, to achieve exact solutions for such bi-level optimization problems, assuming sufficient inner problem optimizer quality. The framework leverages problem-specific knowledge to expedite search processes and minimize the number of expensive evaluations required.

As a case study, we apply this framework to the Asteroid Routing Problem (ARP), a benchmark problem in global trajectory optimization. Experimental results demonstrate the framework's scalability and ability to generate robust heuristic solutions for ARP instances. Many of these solutions are exact, contingent on the assumed quality of the inner problem's optimizer.

Our algorithms are becoming increasingly complex, how can we trust that our algorithms are both correctly designed and implemented? 

While this remains a grand challenge, researchers have been approaching this from a more practical perspective: requiring algorithms to additionally output a certificate that can be used to verify claims of infeasibility or optimality. By verifying such a certificate—a much easier task than solving the original problem—we can substantially increase our confidence that the output of the algorithm is correct.

In this talk, I will present this general idea for combinatorial optimisation, touch upon our recent work to efficiently generate certificates for constraint programming [1], and show how we can do better by leveraging the dynamic programming structure of problems to directly generate certificates of infeasibility or optimality [2], all with only minor additions to existing solvers. I will also discuss the connection with transition systems such as decision diagrams.

The main message of the talk is that certificate generation is a promising avenue towards trustworthy combinatorial optimisation, and I hope to discuss interesting use-cases with the participants.

[1] "A Multi-Stage Proof Logging Framework to Certify the Correctness of CP Solvers"; Flippo, Sidorov, Marijnissen, Smits, Demirović; CP'24.

[2] "Pseudo-Boolean Reasoning about States and Transitions to Certify Dynamic Programming and Decision Diagram Algorithms"; Demirović, McCreesh, McIlree, Nordström, Oertel, Sidorov; CP'24

As a CP constraint, the MDD constraint is part of the family of the extensional constraints. This family includes constraints based on explicit representation of their solutions, such as tables or diagrams. 

For table constraints, the state-of-the-art propagator is Compact-Table, a propagator based on bitsets and bitwise operations. 

In this presentation, you will learn about Compact-Diagram, a CP propagator for the MDD constraint (and diagram constraint in general) inspired by Compact-Table.

We consider combinatorial optimization problems with unknown components, such as their objective function and/or constraints, for which the functional form is unknown. To tackle these problems, we propose a generative AI end-to-end approach based on transformers augmented with constraint reasoning tools (including decision diagrams), as a generalization of inverse optimization. We compare our method with a machine-learning-based approach and an inverse optimization approach. We use the knapsack problem with an unknown objective as a case study, considering different functional forms: linear, quadratic, and heuristic-constructed solutions.