Integer Programming

Cover-based inequalities for the single-source capacitated facility location problem with customer preferences

  • Christina Büsing
  • Markus Leitner
  • Sophia Wrede
    • Categories Combinatorial Optimization, Integer Programming Tags , , ,

    The single-source capacitated facility location problem with customer preferences (SSCFLPCP) is known to be strongly NP-hard. Computational tests imply that state-of-the-art solvers struggle with computing exact solutions. In this paper, we contribute two novel preprocessing methods which reduce the size of the considered integer programming formulation, and introduce sets of valid inequalities which decrease the … Read more

    Equity-promoting Integer Programming Approaches For Medical Resident Rotation Scheduling

  • Karmel S. Shehadeh
  • Shutian Li
  • Frank E. Curtis
  • Beth Hochman
    • Categories Applications - OR and Management Sciences, Integer Programming, Multi-Criteria Optimization Tags , , ,

    Motivated by our collaboration with a residency program at an academic health system, we propose new integer programming (IP) approaches for the resident-to-rotation assignment problem (RRAP). Given sets of residents, resident classes, and departments, as well as a block structure for each class, staffing needs, rotation requirements for each class, program rules, and resident vacation … Read more

    Models for two-dimensional bin packing problems with customer order spread

  • Mateus Martin
  • Horacio Hideki Yanasse
  • Maristela O. Santos
  • Reinaldo Morabito
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences Tags , ,

    In this paper, we address an extension of the classical two-dimensional bin packing (2BPP) that considers the spread of customer orders (2BPP-OS). The 2BPP-OS addresses a set of rectangular items, required from different customer orders, to be cut from a set of rectangular bins. All the items of a customer order are dispatched together to … Read more

    A Row-wise Algorithm for Graph Realization

  • Rolf van der Hulst
  • Matthias Walter
    • Categories (Mixed) Integer Linear Programming, Graphs and Matroids, Network Optimization Tags , , , , ,

    Given a \(\{0,1\}\)-matrix \(M\), the graph realization problem for \(M\) asks if there exists a spanning forest such that the columns of \(M\) are incidence vectors of paths in the forest. The problem is closely related to the recognition of network matrices, which are a large subclass of totally unimodular matrices and have many applications … Read more

    An Asymptotically Optimal Coordinate Descent Algorithm for Learning Bayesian Networks from Gaussian Models

  • Tong Xu
  • Simge Küçükyavuz
  • Ali Shojaie
    • Categories (Mixed) Integer Nonlinear Programming

    This paper studies the problem of learning Bayesian networks from continuous observational data, generated according to a linear Gaussian structural equation model. We consider an \(\ell_0\)-penalized maximum likelihood estimator for this problem which is known to have favorable statistical properties but is computationally challenging to solve, especially for medium-sized Bayesian networks. We propose a new … Read more

    Machine Learning for Optimization-Based Separation: the Case of Mixed-Integer Rounding Cuts

  • Oscar Guaje
  • Aleksandr M. Kazachkov
  • Elias B. Khalil
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches

    Mixed-Integer Rounding (MIR) cuts are effective at improving the dual bound in Mixed-Integer Linear Programming (MIP). However, in practice, MIR cuts are separated heuristically rather than using optimization as the latter is prohibitively expensive. We present a hybrid cut generation framework in which we train a Machine Learning (ML) model to inform cut generation for … Read more

    Optimizing the lead time of operational flexibility trading from distributed industrial energy systems in future energy and flexibility markets

  • Daniel Bull
    • Categories (Mixed) Integer Linear Programming, Control Applications, Energy Tags , , , ,

    To meet the challenges of increasing volatile and distributed renewable energy generation in the electric grid, local flexibility and energy markets are currently investigated. These markets aim to encourage prosumers to trade their available flexible power locally, to be used if a grid congestion is being predicted. The markets are emerging, but the characterizing parameter … Read more

    The Overflowing Bin Packing Problem: Theoretical Results and a New Flow Formulation

  • John Martinovic
  • Nico Strasdat
    • Categories (Mixed) Integer Linear Programming Tags , , , ,

    We consider a recently proposed one-dimensional packing problem, called the overflowing bin packing problem (OBPP). In this scenario, we are given a set of items (of known sizes) and a set of bins (of known capacities). Roughly speaking, the task is to assign the items to the bins in such a way that the total … Read more

    An adaptive relaxation-refinement scheme for multi-objective mixed-integer nonconvex optimization

  • Gabriele Eichfelder
  • Moritz Link
  • Stefan Volkwein
  • Leo Warnow
    • Categories (Mixed) Integer Nonlinear Programming, Multi-Criteria Optimization Tags , , , ,

    In this work, we present an algorithm for computing an enclosure for multi-objective mixed-integer nonconvex optimization problems. In contrast to existing solvers for this type of problem, this algorithm is not based on a branch-and-bound scheme but rather relies on a relax-and-refine approach. While this is an established technique in single-objective optimization, several adaptions to … Read more

    A new framework to generate Lagrangian cuts in multistage stochastic mixed-integer programming

  • Christian Füllner
  • Xu Andy Sun
  • Steffen Rebennack
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , , , ,

    Based on recent advances in Benders decomposition and two-stage stochastic integer programming we present a new generalized framework to generate Lagrangian cuts in multistage stochastic mixed-integer linear programming (MS-MILP). This framework can be incorporated into decomposition methods for MS-MILPs, such as the stochastic dual dynamic integer programming (SDDiP) algorithm. We show how different normalization techniques … Read more