Integer Programming

Robustification of the k-Means Clustering Problem and Tailored Decomposition Methods: When More Conservative Means More Accurate

  • Jan Pablo Burgard
  • Carina Moreira Costa
  • Martin Schmidt
    • Categories (Mixed) Integer Nonlinear Programming, Robust Optimization Tags , , , ,

    k-means clustering is a classic method of unsupervised learning with the aim of partitioning a given number of measurements into k clusters. In many modern applications, however, this approach suffers from unstructured measurement errors because the k-means clustering result then represents a clustering of the erroneous measurements instead of retrieving the true underlying clustering structure. … Read more

    Personnel scheduling during Covid-19 pandemic

  • Manuel Iori
  • Anand Subramanian
  • Giorgio Zucchi
    • Categories (Mixed) Integer Linear Programming, Scheduling Tags , , ,

    This paper addresses a real-life personnel scheduling problem in the context of Covid-19 pandemic, arising in a large Italian pharmaceutical distribution warehouse. In this case study, the challenge is to determine a schedule that attempts to meet the contractual working time of the employees, considering the fact that they must be divided into mutually exclusive … Read more

    Linearization and Parallelization Schemes for Convex Mixed-Integer Nonlinear Optimization

  • Meenarli Sharma
  • Prashant Palkar
  • Ashutosh Mahajan
    • Categories (Mixed) Integer Nonlinear Programming, Parallel Algorithms Tags , , , ,

    We develop and test linearization and parallelization schemes for convex mixed-integer nonlinear programming. Several linearization approaches are proposed for LP/NLP based branch-and-bound. Some of these approaches strengthen the linear approximation to nonlinear constraints at the root node and some at the other branch-and-bound nodes. Two of the techniques are specifically applicable to commonly found univariate … Read more

    Solving Large-Scale Sparse PCA to Certifiable (Near) Optimality

  • Dimitris Bertsimas
  • Ryan Cory-Wright
  • Jean Pauphilet
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming, Statistics Tags , , ,

    Sparse principal component analysis (PCA) is a popular dimensionality reduction technique for obtaining principal components which are linear combinations of a small subset of the original features. Existing approaches cannot supply certifiably optimal principal components with more than $p=100s$ of variables. By reformulating sparse PCA as a convex mixed-integer semidefinite optimization problem, we design a … Read more

    A tactical maintenance optimization model for multiple interconnected energy production systems

  • Silvia Anna Cordieri
  • Federico Malucelli
  • Ola Jabali
    • Categories (Mixed) Integer Linear Programming, Facility Planning and Design Tags , , , ,

    Multiple interconnected energy production systems are a common solution to satisfy the energy demand of industrial processes. Such energy demand is usually the combination of various energy types such as heat and electricity. This implies the installation of different technologies able to produce one or multiple energy types, to satisfy all energy needs. However, multiple … Read more

    A Distributionally Robust Optimization Approach for Stochastic Elective Surgery Scheduling with Limited Intensive Care Unit Capacity

  • Rema Padman
  • Karmel S. Shehadeh
    • Categories (Mixed) Integer Linear Programming, Scheduling, Stochastic Programming Tags , , , , ,

    In this paper, we study the decision process of assigning elective surgery patients to available surgical blocks in multiple operating rooms (OR) under random surgery durations, random postoperative length-of-stay in the intensive care unit (ICU), and limited capacity of ICU. The probability distributions of random parameters are assumed to be ambiguous, and only the mean … Read more

    Mining for diamonds – matrix generation algorithms for binary quadratically constrained quadratic problems

  • Enrico Bettiol
  • Immanuel M. Bomze
  • Lucas Létocart
  • Francesco Rinaldi
  • Emiliano Traversi
    • Categories (Mixed) Integer Nonlinear Programming, Linear, Cone and Semidefinite Programming Tags , , ,

    In this paper, we consider binary quadratically constrained quadratic problems and propose a new approach to generate stronger bounds than the ones obtained using the Semidefinite Programming relaxation. The new relaxation is based on the Boolean Quadric Polytope and is solved via a Dantzig-Wolfe Reformulation in matrix space. For block-decomposable problems, we extend the relaxation … Read more

    Combinatorial Acyclicity Models for Potential-based Flows

  • Oliver Habeck
  • Marc E. Pfetsch
    • Categories (Mixed) Integer Nonlinear Programming, Network Optimization Tags , , ,

    Potential-based flows constitute a basic model to represent physical behavior in networks. Under natural assumptions, the flow in such networks must be acyclic. The goal of this paper is to exploit this property for the solution of corresponding optimization problems. To this end, we introduce several combinatorial models for acyclic flows, based on binary variables … Read more

    An Image-based Approach to Detecting Structural Similarity Among Mixed Integer Programs

  • Mark Karwan
  • Marco E. Lübbecke
  • Chase Murray
  • Zachary Steever
  • Junsong Yuan
    • Categories (Mixed) Integer Linear Programming Tags , , , ,

    Operations researchers have long drawn insight from the structure of constraint coefficient matrices (CCMs) for mixed integer programs (MIPs). We propose a new question: Can pictorial representations of CCM structure be used to identify similar MIP models and instances? In this paper, CCM structure is visualized using digital images, and computer vision techniques are employed … Read more

    An algorithm for assortment optimization under parametric discrete choice models

  • Andrea Lodi
  • Tien Mai
    • Categories 0-1 Programming, Applications - OR and Management Sciences Tags , , ,

    This work concerns the assortment optimization problem that refers to selecting a subset of items that maximizes the expected revenue in the presence of the substitution behavior of consumers specified by a parametric choice model. The key challenge lies in the computational difficulty of finding the best subset solution, which often requires exhaustive search. The … Read more