mixed-integer programming

Sparse Principal Component Analysis with Non-Oblivious Adversarial Perturbations

  • Yuqing He
  • Guanyi Wang
  • Yu Yang
    • Categories (Mixed) Integer Nonlinear Programming Tags , ,

    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

    Generator Subadditive Functions for Mixed-Integer Programs

  • Gustavo Angulo
  • Burak Kocuk
  • Diego Moran Ramirez
    • Categories (Mixed) Integer Nonlinear Programming, Cone Programming, Integer Programming Tags , , , ,

    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

    Bounding the number and the diameter of optimal compact Black-majority districts

  • Samuel Kroger
  • Hamidreza Validi
  • Illya V. Hicks
  • Tyler Perini
    • Categories Applications - OR and Management Sciences, Branch and Cut Algorithms, Combinatorial Optimization Tags , , ,

    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

    Benders decomposition with scaled cuts for multistage stochastic mixed-integer programs

  • Ward Romeijnders
  • Niels van der Laan
    • Categories Stochastic Programming Tags , ,

    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

    An Extended Validity Domain for Constraint Learning

  • Yilin Zhu
  • Samuel Burer
    • Categories Data Science Algorithms, Optimization in Data Science Tags , , , ,

    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

    Extended Formulations for Control Languages Defined by Finite-State Automata

  • Christoph Buchheim
  • Maximilian Merkert
    • Categories (Mixed) Integer Linear Programming, Optimization of Systems modeled by PDEs, Polyhedra Tags , , , ,

    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

    Heuristic Methods for Γ-Robust Mixed-Integer Linear Bilevel Problems

  • Yasmine Beck
  • Ivana Ljubić
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, Robust Optimization Tags , , ,

    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

    Solution methods for partial inverse combinatorial optimization problems in which weights can only be increased

  • Eva Ley
  • Maximilian Merkert
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Game Theory Tags , , ,

    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

    A proof system for certifying symmetry and optimality reasoning in integer programming

  • Jasper van Doornmalen
  • Leon Eifler
  • Ambros Gleixner
  • Christopher Hojny
    • Categories (Mixed) Integer Linear Programming Tags , , , ,

    We present a proof system for establishing the correctness of results produced by optimization algorithms, with a focus on mixed-integer programming (MIP). Our system generalizes the seminal work of Bogaerts, Gocht, McCreesh, and Nordström (2022) for binary programs to handle any additional difficulties arising from unbounded and continuous variables, and covers a broad range of … Read more

    Learning Optimal Classification Trees Robust to Distribution Shifts

  • Nathan Justin
  • Sina Aghaei
  • Andrés Gómez
  • Phebe Vayanos
    • Categories (Mixed) Integer Linear Programming, Robust Optimization Tags , , , ,

    We consider the problem of learning classification trees that are robust to distribution shifts between training and testing/deployment data. This problem arises frequently in high stakes settings such as public health and social work where data is often collected using self-reported surveys which are highly sensitive to e.g., the framing of the questions, the time … Read more