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 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
Sparse Principal Component Analysis (sparse PCA) is a fundamental dimension-reduction tool that enhances interpretability in various high-dimensional settings. An important variant of sparse PCA studies the scenario when samples are adversarially perturbed. Notably, most existing statistical studies on this variant focus on recovering the ground truth and verifying the robustness of classical algorithms when the … Read more
For equality-constrained linear mixed-integer programs (MIP) defined by rational data, it is known that the subadditive dual is a strong dual and that there exists an optimal solution of a particular form, termed generator subadditive function. Motivated by these results, we explore the connection between Lagrangian duality, subadditive duality and generator subadditive functions for general … Read more
Section 2 of the Voting Rights Act (VRA) prohibits voting practices that minimize or cancel out minority voting strength. While this section provides no clear framework for avoiding minority vote dilution and creating minority-majority districts, the Supreme Court proposed the Gingles test in the 1986 case Thornberg v Gingles. The Gingles test provides three conditions … Read more
We consider Benders decomposition algorithms for multistage stochastic mixed-integer programs (SMIPs) with general mixed-integer decision variables at every node in the scenario tree. We derive a hierarchy of convex polyhedral lower bounds for the value functions and expected cost to-go functions in multistage SMIPs using affine parametric cutting planes in extended spaces for the feasible … Read more
We consider embedding a predictive machine-learning model within a prescriptive optimization problem. In this setting, called constraint learning, we study the concept of a validity domain, i.e., a constraint added to the feasible set, which keeps the optimization close to the training data, thus helping to ensure that the computed optimal solution exhibits less prediction … Read more
Many discrete optimal control problems feature combinatorial constraints on the possible switching patterns, a common example being minimum dwell-time constraints. After discretizing to a finite time grid, for these and many similar types of constraints, it is possible to give a description of the convex hull of feasible (finite-dimensional) binary controls via extended formulations. In … Read more
Due to their nested structure, bilevel problems are intrinsically hard to solve–even if all variables are continuous and all parameters of the problem are exactly known. In this paper, we study mixed-integer linear bilevel problems with lower-level objective uncertainty, which we address using the notion of Γ-robustness. To tackle the Γ-robust counterpart of the bilevel … Read more
Partial inverse combinatorial optimization problems are bilevel optimization problems in which the leader aims to incentivize the follower to include a given set of elements in the solution of their combinatorial problem. If the set of required elements defines a complete follower solution, the inverse combinatorial problem is solvable in polynomial time as soon as … Read more