Mixed Integer Programming Workshop 2024

Welcome comments

Ted Ralphs – It's the Farkas Lemma All the Way Down: A Generalized Farkas Lemma and Its Implications

We present a generalized version of the Farkas Lemma that provides a unifying framework for understanding the relationships between solution algorithms for discrete optimization.problems with multiple objectives, multiple decision-makers, and/or multiple stages. A well-known geometric interpretation of Farkas' certificate of infeasibility for a linear optimization problem is as a hyperplane separating a given right-hand side vector from a convex cone. This interpretation generalizes in a natural way to the MILP setting and provides a geometric way of understanding MILP duality and related concepts. This geometric point of view also provides insight into the algorithms for a variety of optimization problems, As a motivating example, we'll describe how this point of view led to development of a class of algorithms for constructing the efficient frontier of a general multiobjective mixed integer linear optimization optimization problem with an arbitrary number of objectives in a single branch-and-bound tree.

Break

Merve Bodur – Incorporating Service Reliability in Multi-depot Vehicle Scheduling: A Chance-Constrained Approach

The multi-depot vehicle scheduling problem (MDVSP) is a principal planning challenge for transit agencies. We introduce a novel approach to MDVSP by incorporating service reliability through chance-constrained programming (CCP), targeting the pivotal issue of travel time uncertainty and its impact on transit service quality. We propose an exact branch-and-cut (B&C) scheme to solve our CCP model. We present several cut-generation procedures that exploit the underlying problem structure and analyze the relationship between the obtained cut families. Additionally, we design a Lagrangian-based heuristic to handle large-scale instances reflective of real-world transit operations. Our approach partitions the set of trips, each subset leading to a subproblem that can be efficiently solved with our B&C algorithm, and then employs a procedure to combine the subproblem solutions to create a vehicle schedule that satisfies all the planning constraints of the MDVSP. Our empirical evaluation demonstrates the superiority of our stochastic variant in achieving cost-effective schedules with reliable service guarantees compared to alternatives commonly used by practitioners, as well as the computational benefits of our methodologies.

Martina Cerulli – A bilevel approach for compensation and routing decisions in last-mile delivery

In last-mile delivery logistics, peer-to-peer logistic platforms play an important role in connecting senders, customers, and independent carriers to fulfill delivery requests. Since the carriers are not under the platform’s control, the platform has to anticipate their reactions, while deciding how to allocate the delivery operations. In this work, we model this problem using bilevel pro- gramming. At the upper level, the platform decides how to assign the orders to the carriers; at the lower level, each carrier solves a profitable tour problem to determine which offered requests to accept, based on her own profit maximiza- tion. Possibly, the platform can influence carriers’ decisions by determining also the compensation paid for each accepted request. The two considered settings result in two different formulations: the bilevel profitable tour problem with fixed compensation margins and with margin decisions, respectively. For each of them, we propose single-level reformulations and alternative formulations where the lower-level routing variables are projected out. A branch-and-cut algorithm is proposed to solve the bilevel models and extensive computational tests are performed to compare the proposed formulations and analyze solution characteristics. (slides)

Lunch

Jeff Poskin – Mixed Integer Optimization in Aerospace Engineering

Mixed integer optimization (MIO) is leveraged regularly across aerospace engineering, addressing problems in the design, manufacturing, production, and in-service life of commercial aircraft. This presentation will start with a brief overview of how Boeing’s Applied Math Group applies MIO to problems at Boeing. This presentation will then focus on a mixed integer nonlinear programming (MINLP) formulation for stringer centerline design in a commercial vehicle. Fuselage stringers are load-bearing components that run lengthwise along an aircraft and transfer aerodynamic loads acting on the skin into the stringers and frames. The design of stringer centerlines in commercial airplanes has traditionally been performed manually by structural engineers since stringer configurations are subject to a wide variety of design and integration requirements. These requirements include minimum and maximum spacing between pairs of centerlines, maximum area constraints on frame bays, and a host of integration requirements with additional features in the fuselage. The MINLP formulation uses discrete variables to assign stringers to drop out of the design at specific frame stations and continuous variables to control the path stringers take on the fuselage surface. We will efficiently enumerate this design space by checking the feasibility of several linear programs representing relaxations of the stringer spacing constraints. This enumeration is incorporated into a branch and bound algorithm that solves the centerline design problem to global optimality. This algorithm is compared to a piecewise linear modeling approach to solve the MINLP.

Poster Teaser #1

Break

Poster Teaser #2

Mathieu Tanneau – Trust, but verify: MIP-based verification of (trained) neural networks

Recent advances in Machine Learning, and artificial neural networks (ANN) in particular, has fueled a growing interest in deploying such models in safety-critical applications, from image recognition in self-driving cars to control systems in power grids. A major obstacle to this deployment, however, is the lack of formal guarantees on the performance of trained ANNs once deployed in real life. This, in turn, has motivated the so-called ANN verification problem, wherein one must verify whether the output of a trained ANN satisfies certain properties for any input in a given domain. All exact verification methods rely, some way or another, on a mixed-integer representation of the mapping between input and output of a ANN with fixed weights. Nevertheless, existing MIP solvers struggle on this class of problems, and are far outperformed by current state-of-the-art methods for ANN verification (as demonstrated by recent outcomes of the Verification of Neural Networks Competition). This talk will cover the challenges (and recent successes!) of MIP-based verification of trained neural networks, with a particular focus on problems arising from engineering applications. Numerical results will be presented on open instances from the VNN-COMP24, and from real-life applications in power systems.

Poster Session

Dolores Romero Morales – A tour of Mathematical Optimization Models for Group Counterfactual Explanations

Counterfactual Analysis has shown to be a powerful tool in the burgeoning field of Explainable Artificial Intelligence. In Supervised Classification, this means associating with each record a so-called counterfactual explanation: an instance that is close to the record and whose probability of being classified in the opposite class by a given classifier is high. While the literature mostly focuses on the problem of finding one counterfactual for one record, in this presentation we take a stakeholder perspective, and we address the more general setting in which a group of counterfactual explanations is sought for a group of instances. We introduce some mathematical optimization models as illustration of each possible allocation rule between counterfactuals and instances, for tabular as well as functional data, and tasks beyond Supervised Classification. (slides)

Break

Carla Michini – A polyhedral study of multivariate decision trees

Decision trees are a widely used tool for interpretable machine learning. Multivariate decision trees employ hyperplanes at the branch nodes to route datapoints throughout the tree and yield more compact models than univari- ate trees. Recently, mixed-integer programming (MIP) has been applied to formulate the optimal decision tree problem. A key component of most MIP formulations is a specification of how to route datapoints in the tree from the root to the leaves. Our goal is to provide polyhedral characterizations of realizable routings, i.e., routings that can be realized using multivariate branching rules. We first focus on shattering inequalities, a class of valid inequalities that can be used to strengthen almost any MIP formulation and that have been shown to be computationally effective. We prove that if all the feature vectors are in general position, then the shattering inequalities defined for the root of the tree are facet-defining for the convex hull of the realizable routings. We then show that every facet-defining inequality of a depth one tree involving at least two variables is also facet-defining for trees of arbitrary depth. Finally, we show that facet-defining inequalities characterizing realizable routings are also facet-defining for a complete MIP formulation. We validate our theoretical results by performing numerical experiments that specifically exploit shattering inequalities defined at the root node and we observe an improvement in performance for both numerical and categorical datasets, especially for decision trees of intermediate size. This a joint work with Zachary Zhou. (slides)

Sebastian Perez-Salazar – Stochastic Scheduling: Approximations via LP Relaxations

Motivated by applications where impatience is pervasive, such as serving customers in call centers and running jobs in the cloud spot market, we introduce a sequential job scheduling problem, where each job has unknown stochastic service and departure times. Initially, we have access to a single server and n jobs with known non-negative values. These jobs also have unknown stochastic service and departure times with known distributional information, which we assume to be independent. When the server is free, we can run a job that has neither been run nor departed and collect its value. Running a job fully occupies the server for an unknown amount of time, at which other jobs waiting to be run could depart. We aim to design a policy that maximizes the expected total value obtained from jobs run on the server. Natural formulations of this problem (e.g., using dynamic programming) suffer from the curse of dimensionality, making them intractable. Hence, we focus on heuristic approaches that provide provable approximations of the optimal policy. We devise a compact LP with an objective that upper bounds the value of the optimal policy. Additionally, from this LP, we design an implementable policy that guarantees a constant approximation of the optimal policy.

Lunch

Soroosh Shafieezadeh-Abadeh – Constrained Optimization of Low-Rank Functions with Indicator Variables

Optimization problems involving minimization of a low-rank convex function over constraints modeling restrictions on the support of the decision variables emerge in various machine learning applications. These problems are often modeled with indicator variables for identifying the support of the continuous variables. In this paper we investigate compact extended formulations for such problems through perspective reformulation techniques. In contrast to the majority of previous work that relies on support function arguments and disjunctive programming techniques to provide convex hull results, we propose a constructive approach that exploits a hidden conic structure induced by perspective functions. To this end, we first establish a convex hull result for a general conic mixed-binary set in which each conic constraint involves a linear function of independent continuous variables and a set of binary variables. We then demonstrate that extended representations of sets associated with epigraphs of low-rank convex functions over constraints modeling indicator relations naturally admit such a conic representation. This enables us to systematically give perspective formulations for the convex hull descriptions of these sets with nonlinear separable or non-separable objective functions, sign constraints on continuous variables, and combinatorial constraints on indicator variables. (slides)

Danial Davarnia – Convexification of Bilinear Terms over Network Polytopes

It is well-known that the McCormick relaxation for the bilinear constraint z = xy gives the convex hull over the box domains for x and y. In network applications where the domain of bilinear variables is described by a network polytope, the McCormick relaxation, also referred to as linearization, fails to provide the convex hull and often leads to poor dual bounds. We study the convex hull of the set containing bilinear constraints zi,j = xiyj where xi represents the arc-flow variable in a network polytope, and yj is in a simplex. For the case where the simplex contains a single y variable, we introduce a systematic procedure to obtain the convex hull of the above set in the original space of variables and show that all facet-defining inequalities of the convex hull can be obtained explicitly through identifying a special tree structure in the underlying network. For the generalization where the simplex contains multiple y variables, we design a constructive procedure to obtain an important class of facet-defining inequalities for the convex hull of the underlying bilinear set that is characterized by a special forest structure in the underlying network. Computational experiments conducted on different applications show the effectiveness of the proposed methods in improving the dual bounds obtained from alternative techniques. (slides)

Break

Gerald Gamrath – New Presolving Techniques in the Cardinal Optimizer

Presolving is an essential component of modern MIP solvers. It cleans up the model, identifies structures in the problem, and tightens the formulation before the branch-and-cut search starts. In this talk, we present new presolving techniques implemented in the Cardinal Optimizer (COPT). The discussed methods range from techniques based on specific structures like precedence graphs or symmetry relations to improvement of general techniques like probing. We address examples that caused our analysis of those structures and present the details of the new presolving reductions. For each reduction, we show computational results demonstrating its impact.

Computational Competition

Conference Dinner

Güzin Bayraksan – Bounds for Multistage Mixed-Integer Distributionally Robust Optimization

Multistage mixed-integer distributionally robust optimization (DRO) forms a class of extremely challenging problems since their size grows exponentially with the number of stages. One way to model the uncertainty in multistage DRO is by creating sets of conditional distributions (the so-called conditional ambiguity sets) on a finite scenario tree and requiring that such distributions remain close to nominal conditional distributions according to some measure of similarity/distance. In this talk, new bounding criteria for this class of difficult decision problems are provided through scenario grouping and convolution of risk measures using the ambiguity sets associated with various commonly used φ-divergences and the Wasserstein distance. Our approach does not require any special problem structure such as linearity, convexity, stagewise independence, and so forth. Therefore, while we focus on multistage mixed-integer DRO, our bounds can be applied to a wide range of DRO problems including two-stage and multistage, with or without integer variables, convex or nonconvex, and nested or non-nested formulations. Numerical results on a multistage mixed-integer production problem show the efficiency of the proposed approach through different choices of partition strategies, ambiguity sets, and levels of robustness. (slides)

Break

Bernard Knueven – Solving the Grid Optimization Competition Challenge 3 Problem

The Grid Optimization Competition Challenge 3 Problem posed a multiperiod security-constrained unit commitment problem with base-case AC power flow. The problem formulation includes binary unit commitment decisions, nonlinear AC power flow and balance, dispatchable loads, and linearized contingency real power flow, among other features. This talk will present a modified consensus ADMM algorithm, which splits the problem into mixed-integer linear and nonlinear components, as a heuristic solution method for this large-scale mixed integer nonlinear program. We will present some computational results from the competition for our implementation and reflect on the challenges of participating the grid optimization competition. (slides)

Rui Chen – Recovering Dantzig-Wolfe Bounds by Cutting Planes

Dantzig-Wolfe (DW) decomposition is a well-known technique in mixed-integer programming (MIP) for decomposing and convexifying constraints to obtain potentially strong dual bounds. We investigate cutting planes that can be derived in the space of original variables using DW decomposition and show that these cuts can provide the same dual bounds as DW decomposition. Compared with the objective function cut one can simply write using the DW bound, this approach typically leads to a formulation with lower dual degeneracy that consequently has a better computational performance when solved by standard MIP solvers in the original space. We also discuss how to strengthen these cuts to improve the computational performance further. (slides)

Lunch

Mathieu Besançon – Better Strong Branching Usage with a Stochastic Branching Model

Strong Branching (SB) is a cornerstone of all modern branching rules used in the Branch-and-Bound (BnB) algorithm, which is at the center of Mixed-Integer Programming solvers. In its full form, SB evaluates all variables to branch on and then selects the one producing the best relaxation, leading to small trees, but high runtimes. State-of-the-art branching rules therefore use SB with empirical working limits to achieve both small enough trees and short run times. In this work, we define a stochastic tree model of the BnB algorithm where dual gains follow a given probability distribution. This model allows us to relate expected dual gains to tree sizes and explicitly compare the cost of sampling a SB candidate with the reward in expected tree size reduction. We then leverage the insight from the abstract model to design a new stopping criterion for SB which dynamically continues or interrupts SB, and show that it improves solving performance in both time and nodes over MIPLIB.

Yatharth Dubey – Branch-and-bound with predictions for variable selection

In this paper, we are interested in solving a binary integer program using the branch-and-bound method. The execution of the branch-and-bound method varies significantly with the choice of variable selection rule (sometimes called branching rule). To solve a given MILP with the smallest branch-and-bound tree possible, one would want to branch on a variable such that the two resulting subproblems are as "easy" as possible. Informally, given access to a function $\theta (S)$ that gives the size of the smallest branch-and-bound tree solving subproblem $S$, we can construct a smallest branch-and-bound tree by branching on the variable $j$ resulting in subproblems $S$_{x_j = 0}, S_{x_j = 1} such that $\theta (S$_{x_j = 0}) + θ(S_{x_j = 1}) is minimum over all choices of $j$. Of course, computing all of the necessary values of $\theta (S)$ is no easier than solving the integer program itself. This motivates the need for a good estimator $\theta ̂$ for $\theta$, which has been an implicit goal of several previous studies, including those employing machine learning techniques for variable selection. Indeed, one can view full strong branching as branching according to an estimator $\theta ̂$ that is a (monotone) function of only the additive integrality gap. Our study reflects the goals of the rapidly developing research on "algorithms with predictions", which focuses on how to leverage constantly advancing machine learning tools for improved algorithms. In particular, the goal of this work is to quantify the impact of the quality of the estimate $\sigma ̂$ when used for variable selection and to get a better understanding of what a good estimate looks like. We provide some theoretical results and discussion, as well as a computational study of strong branching under this context, and suggest some potential estimates that may result in smaller branch-and-bound trees. (slides)

Break

Juan Pablo Vielma – MathOpt: Solver independent modeling and execution independent solving in Google's OR-Tools

OR-Tools MathOpt is a software library for algebraic modeling of mathematical optimization problems. MathOpt supports solver-independent modeling of a wide range of optimization problems including continuous and mixed-integer problems with linear or quadratic objectives and various classes of constraints (including linear, quadratic, second order cone and some specialized constraints). In this talk, we describe various aspects of MathOpt’s design and implementation including multi-language support (including C++ and Python), support for solver-independent callbacks and incremental solves, and remote solves using Google’s Operations Research API service.

Business Meeting

Bento Natura – A strongly polynomial algorithm for linear programs with at most two nonzero entries per row or column

We give a strongly polynomial algorithm for minimum cost generalized flow, and hence for optimizing any linear program with at most two non-zero entries per row, or at most two non-zero entries per column. Primal and dual feasibility were shown by Megiddo (SICOMP ’83) and Végh (MOR ’17) respectively. Our result can be viewed as progress towards understanding whether all linear programs can be solved in strongly polynomial time, also referred to as Smale’s 9th problem. Our approach is based on the recent primal- dual interior point method (IPM) due to Allamigeon, Dadush, Loho, Natura and Végh (FOCS ’22). The number of iterations needed by the IPM is bounded, up to a polynomial factor in the number of inequalities, by the straight line complexity of the central path. Roughly speaking, this is the minimum number of pieces of any piecewise linear curve that multiplicatively approximates the central path. As our main contribution, we show that the straight line complexity of any minimum cost generalized flow instance is polynomial in the number of arcs and vertices. By applying a reduction of Hochbaum (ORL ’04), the same bound applies to any linear program with at most two non-zeros per column or per row. To be able to run the IPM, one requires a suitable initial point. For this purpose, we develop a novel multistage approach, where each stage can be solved in strongly polynomial time given the result of the previous stage. Beyond this, substantial work is needed to ensure that the bit complexity of each iterate remains bounded during the execution of the algorithm. For this purpose, we show that one can maintain a representation of the iterates as a low complexity convex combination of vertices. Our approach is black-box and can be applied to any log-barrier path following method. Joint work with Daniel Dadush, Zhuan Khye Koh, Neil Olver, and László Végh. (slides)

Break

Maryam Daryalal – Reasoning in Description Logic: A Mixed-integer Programming Framework

Description Logics (DL) are formal languages for knowledge representation, enabling structured ontology creation and logical reasoning. This talk presents an optimization-based framework for enhancing reasoning in DL by employing mixed-integer programming methods. The framework exploits a novel approach of mapping DL axioms to a set of inequalities, enabling the use of advanced optimization techniques. The integration of column generation and branch-and-price algorithms addresses the complexity of the resulting inequality system, offering a scalable solution for handling large ontological datasets. In a preliminary set of experiments, the framework's performance is evidenced by its application to the ontology of the Canadian Parliament, where it outperforms traditional reasoning methods. This work could mark a significant advancement for the Semantic Web community by merging ontology reasoning with sophisticated optimization methods to meet the challenges of semantic data processing. (slides)

Concluding Remarks