Integer Programming

The Minimization of the Weighted Completion Time Variance in a Single Machine: A Specialized Cutting-Plane Approach

  • Stefano Nasini
  • Rabia Nessah
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Scheduling

    This study addresses the problem of minimizing the weighted completion time variance (WCTV) in single-machine scheduling. Unlike the unweighted version, which has been extensively studied, the weighted variant introduces unique challenges due to the absence of theoretical properties that could guide the design of efficient algorithms. We propose a mathematical programming framework based on a … Read more

    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

    The complete edge relaxation for binary polynomial optimization

  • Alberto Del Pia
  • Aida Khajavirad
    • Categories 0-1 Programming, Global Optimization, Integer Programming Tags , , , , ,

    We consider the multilinear polytope defined as the convex hull of the feasible region of a linearized binary polynomial optimization problem. We define a relaxation in an extended space for this polytope, which we refer to as the complete edge relaxation. The complete edge relaxation is stronger than several well-known relaxations of the multilinear polytope, … Read more

    Anesthesiologist Scheduling with Handoffs: A Combined Approach of Optimization and Human Factors

  • Ankit Bansal
  • Osman Y. Ozaltin
    • Categories Integer Programming, Scheduling, Stochastic Programming

    We present a two-stage stochastic programming model for optimizing anesthesiologist schedules, explicitly accounting for uncertainty in surgery durations and anesthesiologist handoffs. To inform model design, we conducted an online survey at our partner institution to identify key factors affecting the quality of intraoperative anesthesiologist handoffs. Insights from the survey results are incorporated into the model, … 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

    Strength of the Upper Bounds for the Edge-Weighted Maximum Clique Problem

  • Fabio Ciccarelli
  • Valerio Dose
  • Fabio Furini
  • Marta Monaci
    • Categories Graphs and Matroids, Integer Programming Tags , ,

    We theoretically and computationally compare the strength of the two main upper bounds from the literature on the optimal value of the Edge-Weighted Maximum Clique Problem (EWMCP). We provide a set of instances for which the ratio between either of the two upper bounds and the optimal value of the EWMCP is unbounded. This result … Read more

    Random-Restart Best-Response Dynamics for Large-Scale Integer Programming Games and Their Applications

  • 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 scalable algorithms for computing pure Nash equilibria (PNEs) in large-scale integer programming games (IPGs), where existing exact methods typically handle only small numbers of players. Motivated by a county-level aquatic invasive species (AIS) prevention problem with 84 decision makers, we develop and analyze random-restart best-response dynamics (RR-BRD), a randomized search framework for … 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