(Mixed) Integer Linear Programming

A Primal Approach to Facial Reduction for SDP Relaxations of Combinatorial Optimization Problems

  • Hao Hu
    • Categories (Mixed) Integer Linear Programming, Convex Optimization

    We propose a novel facial reduction algorithm tailored to semidefinite programming relaxations of combinatorial optimization problems with quadratic objective functions. Our method leverages the specific structure of these relaxations, particularly the availability of feasible solutions that can often be generated efficiently in practice. By incorporating such solutions into the facial reduction process, we substantially simplify … Read more

    Optimal personnel scheduling in hospital pharmacies considering management and operators priorities

  • Eduardo Souza
  • Walton P. Coutinho
  • Luciano Costa
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Scheduling Tags , ,

    In this paper, we address the problem of allocating and scheduling employees for work shifts in the pharmacy sector of a private hospital. To tackle this issue, we introduce the pharmacy staff scheduling problem (PSSP) in the literature. To solve the problem, we propose a mixed-integer programming formulation that considers various aspects, such as the … Read more

    A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxation

  • Alberto Del Pia
  • Dekun Zhou
    • Categories (Mixed) Integer Linear Programming, Data Science Algorithms, Semi-definite Programming

    Sparse Principal Component Analysis (SPCA) is a fundamental technique for dimensionality reduction, and is NP-hard. In this paper, we introduce a randomized approximation algorithm for SPCA, which is based on the basic SDP relaxation. Our algorithm has an approximation ratio of at most the sparsity constant with high probability, if called enough times. Under a … Read more

    Implied Integrality in Mixed-Integer Optimization

  • Rolf van der Hulst
  • Matthias Walter
    • Categories (Mixed) Integer Linear Programming, Integer Programming, Polyhedra Tags , , , ,

    Implied-integer detection is a well-known presolving technique that is used by many Mixed-Integer Linear Programming solvers. Informally, a variable is said to be implied integer if its integrality is enforced implicitly by integrality of other variables and the constraints of a problem. In this work we formalize the definition of implied integrality by taking a … Read more

    Best-Response Dynamics for Large-Scale Integer Programming Games with Applications to Aquatic Invasive Species Prevention

  • Hyunwoo Lee
  • Robert Hildebrand
  • Wenbo Cai
  • I. Esra Buyuktahtakin Toy
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Game Theory Tags , , , ,

    This paper presents a scalable algorithm for computing the best pure Nash equilibrium (PNE) in large-scale integer programming games (IPGs). While recent advances in IPG algorithms are extensive, existing methods are limited to a small number of players, typically đť‘› = 2, 3. Motivated by a county-level aquatic invasive species (AIS) prevention problem involving 84 … Read more

    A Dantzig-Wolfe Single-Level Reformulation for Mixed-Integer Linear Bilevel Optimization: Exact and Heuristic Approaches

  • Henri Lefebvre
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, Bilevel Optimization, Branch and Cut Algorithms Tags , , , ,

    Bilevel optimization problems arise in numerous real-world applications. While single-level reformulations are a common strategy for solving convex bilevel problems, such approaches usually fail when the follower’s problem includes integer variables. In this paper, we present the first single-level reformulation for mixed-integer linear bilevel optimization, which does not rely on the follower’s value function. Our … Read more

    Branch-and-Cut for Mixed-Integer Generalized Nash Equilibrium Problems

  • Alois Duguet
  • Tobias Harks
  • Martin Schmidt
  • Julian Schwarz
    • Categories (Mixed) Integer Linear Programming, Bilevel Optimization, Game Theory Tags , , , ,

    Generalized Nash equilibrium problems with mixed-integer variables form an important class of games in which each player solves a mixed-integer optimization problem with respect to her own variables and the strategy space of each player depends on the strategies chosen by the rival players. In this work, we introduce a branch-and-cut algorithm to compute exact … Read more

    On Multidimensonal Disjunctive Inequalities for Chance-Constrained Stochastic Problems with Finite Support

  • Diego Cattaruzza
  • Martine LabbĂ©
  • Matteo Petris
  • Marius Roland
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , , ,

    We consider mixed-integer linear chance-constrained problems for which the random vector that parameterizes the feasible region has finite support. Our key objective is to improve branch-and-bound or -cut approaches by introducing new types of valid inequalities that improve the dual bounds and, by this, the overall performance of such methods. We introduce so-called primal-dual as … Read more

    Inverse Optimization via Learning Feasible Regions

  • Ke Ren
  • Peyman Mohajerin Esfahani
  • Angelos Georghiou
    • Categories (Mixed) Integer Linear Programming, Nonsmooth Optimization, Robust Optimization Tags , , ,

    We study inverse optimization (IO), where the goal is to use a parametric optimization program as the hypothesis class to infer relationships between input-decision pairs. Most of the literature focuses on learning only the objective function, as learning the constraint function (i.e., feasible regions) leads to nonconvex training programs. Motivated by this, we focus on … Read more

    A surplus-maximizing two-sided multi-period non-convex ISO auction market

  • Richard O'Neill
  • Yonghong Chen
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Other Topics Tags , , ,

    Since the inception of ISOs, Locational Marginal Prices (LMPs) alone were not market clearing or incentive compatible because an auction winner who offered its avoidable costs could lose money at the LMPs. ISOs used make-whole payments to ensure that market participants did not lose money. Make-whole payments were not public, creating transparency issues. Over time, … Read more