The recent performance improvements in mixed-integer programming (MIP) have been accompanied by a significantly increased complexity of the codes of MIP solvers, which poses challenges in fixing implementation errors. In this paper, we introduce MIP-DD, a solver-independent tool, which to the best of our knowledge is the first open-source delta debugger for MIP. Delta debugging … Read more
Problem definition: More than one-third of US domestic flights are operated by regional airlines. This paper focuses on optimizing medium-term schedule planning decisions for a network of regional airlines through the joint optimization of frequency planning, timetable development, fleet assignment, and some limited aspects of route planning, while capturing passengers’ travel decisions through a general … Read more
Antibiotic resistance, which is a serious healthcare issue, emerges due to uncontrolled and repeated antibiotic use that causes bacteria to mutate and develop resistance to antibiotics. The Antibiotics Time Machine Problem aims to come up with treatment plans that maximize the probability of reversing these mutations. Motivated by the severity of the problem, we develop … Read more
We introduce Mixed Integer Linear Programming (MILP) formulations for the two-stage robust surgery scheduling problem (2SRSSP). We derive these formulations by modeling the second-stage problem as a longest path problem on a layered acyclic graph and subsequently converting it into a linear program. This linear program is then dualized and integrated with the first-stage, resulting … Read more
Inspired by the impact of the Goemans-Williamson algorithm on combinatorial optimization, we construct an analogous relax-then-round strategy for low-rank optimization problems. First, for orthogonally constrained quadratic optimization problems, we derive a semidefinite relaxation and a randomized rounding scheme that obtains provably near-optimal solutions, building on the blueprint from Goemans and Williamson for the Max-Cut problem. … Read more
We study proximity (resp. integrality gap), that is, the distance (resp. difference) between the optimal solutions (resp. optimal values) of convex integer programs (IP) and the optimal solutions (resp. optimal values) of their continuous relaxations. We show that these values can be upper bounded in terms of the recession cone of the feasible region of … Read more
We study multi-follower bilevel optimization problems with binary linking variables where the second level consists of many independent integer-constrained subproblems. This problem class not only generalizes many classical interdiction problems but also arises naturally in many network design problems where the second-level subproblems involve complex routing decisions of the actors involved. We propose a novel … Read more
We present a novel framework that combines machine learning with mixed-integer optimization to solve the Capacitated Location-Routing Problem (CLRP). The CLRP is a classical yet NP-hard problem that integrates strategic facility location with operational vehicle routing decisions, aiming to simultaneously minimize both fixed and variable costs. The proposed method first trains a permutationally invariant neural … Read more
We study bilevel problems with a convex quadratic mixed-integer upper-level, integer linking variables, and a nonconvex quadratic, purely continuous lower-level problem. We prove $\Sigma_p^2$-hardness of this class of problems, derive an iterative lower- and upper-bounding scheme, and show its finiteness and correctness in the sense that it computes globally optimal points or proves infeasibility of … Read more
The traveling salesman problem is a widely studied classical combinatorial problem for which there are several integer linear formulations. In this work, we consider the Miller-Tucker-Zemlin (MTZ), Desrochers-Laporte (DL) and Single Commodity Flow (SCF) formulations. We argue that the choice of some parameters of these formulations is arbitrary and, therefore, there are families of formulations … Read more