Integer Programming

Extending the reflect flow formulation to variable-sized one-dimensional cutting and skiving stock problems

  • Maxence Delorme
  • John Martinovic
    • Categories Combinatorial Optimization, Integer Programming Tags , , ,

    Flow formulations have been widely studied for the one-dimensional cutting stock problem and several of its extensions. Among these, the so-called reflect model has shown the best empirical performance when solved directly with a general-purpose integer linear programming solver due to its reduced number of variables and constraints. However, existing adaptations of reflect for the … Read more

    An exact approach for the Train Single-Routing Selection Problem

  • Anna Livia Croella
  • Fabio Furini
  • Ivana Ljubić
  • Pablo San Segundo
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Transportation Tags , , , ,

    Given a set of train routes with route costs and a set of compatible route pairs with pairing costs, the Train Single-Routing Selection Problem (TSRSP) seeks to assign one route to each train, minimizing the total cost while ensuring pairwise compatibility among the selected routes. This problem is of significant practical relevance in rail traffic … Read more

    Solving MINLPs to global optimality with FICO Xpress Global

  • Pietro Belotti
  • Timo Berthold
  • Tristan Gally
  • Leona Gottwald
  • Imre Pólik
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Optimization Software Design Principles Tags , ,

    We present the architecture and central parts of the FICO Xpress Global optimization solver. In particular, we focus on how we built a global solver for the general class of mixed-integer nonlinear optimization problems by combining and extending two existing components of the FICO Xpress Solver, namely the mixed-integer linear optimization solver and the successive … Read more

    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

    On the Structure of the Inverse-Feasible Region of a Multiobjective Integer Program

  • Tyler Perini
    • Categories Combinatorial Optimization, Integer Programming, Multi-Criteria Optimization Tags , ,

    Many optimization problems are made more challenging due to multiple, conflicting criteria. The subjective nature of balancing these criteria motivates techniques for inverse optimization. This study establishes foundations for an exact representation of the inverse feasible region of a multiobjective integer program. We provide the first insights into its exact structure, as well as two … 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