Integer Programming

Approximation Properties of Sum-Up Rounding in the Presence of Vanishing Constraints

  • Christian Kirches
  • Felix Lenders
  • Paul Manns
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms, Systems governed by Differential Equations Optimization Tags , ,

    Approximation algorithms like sum-up rounding that allow to compute integer-valued approximations of the continuous controls in a weak$^*$ sense have attracted interest recently. They allow to approximate (optimal) feasible solutions of continuous relaxations of mixed-integer control problems (MIOCPs) with integer controls arbitrarily close. To this end, they use compactness properties of the underlying state equation, … Read more

    On Integer and MPCC Representability of Affine Sparsity

  • Hongbo Dong
    • Categories (Mixed) Integer Nonlinear Programming, Complementarity and Variational Inequalities Tags , ,

    In addition to sparsity, practitioners of statistics and machine learning often wish to promote additional structures in their variable selection process to incorporate prior knowledge. Borrowing the modeling power of linear systems with binary variables, many of such structures can be faithfully modeled as so-called affine sparsity constraints (ASC). In this note we study conditions … Read more

    Layered graph approaches for combinatorial optimization problems

  • Luís Gouveia
  • Markus Leitner
  • Mario Ruthmair
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences Tags , , , ,

    Extending the concept of time-space networks, layered graphs associate information about one or multiple resource state values with nodes and arcs. While integer programming formulations based on them allow to model complex problems comparably easy, their large size makes them hard to solve for non-trivial instances. We detail and classify layered graph modeling techniques that … Read more

    Distributionally Robust Linear and Discrete Optimization with Marginals

  • Louis Chen
  • Karthik Natarajan
  • David Simchi-Levi
  • Will Ma
  • Zhenzhen Yan
    • Categories 0-1 Programming, Applications - OR and Management Sciences, Polyhedra Tags , ,

    In this paper, we study the class of linear and discrete optimization problems in which the objective coefficients are chosen randomly from a distribution, and the goal is to evaluate robust bounds on the expected optimal value as well as the marginal distribution of the optimal solution. The set of joint distributions is assumed to … Read more

    Parity Polytopes and Binarization

  • Dominik Ermel
  • Matthias Walter
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Polyhedra Tags , , ,

    We consider generalizations of parity polytopes whose variables, in addition to a parity constraint, satisfy certain ordering constraints. More precisely, the variable domain is partitioned into k contiguous groups, and within each group, we require the variables to be sorted nonincreasingly. Such constraints are used to break symmetry after replacing an integer variable by a … Read more

    On the Consistent Path Problem

  • David Bergman
  • Leonardo Lozano
  • Cole Smith
    • Categories 0-1 Programming, Combinatorial Optimization, Cutting Plane Approaches

    The application of decision diagrams in combinatorial optimization has proliferated in the last decade. In recent years, authors have begun to investigate how to utilize not one, but a set of diagrams, to model constraints and objective function terms. Optimizing over a collection of decision diagrams, the problem we refer to as the consistent path … Read more

    An Integrated Car-and-ride Sharing System for Mobilizing Heterogeneous Travelers with Application in Underserved Communities

  • Siqian Shen
  • Miao Yu
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming, Transportation Tags , , , ,

    The fast-growing carsharing and ride-hailing businesses are generating economic benefits and societal impacts in the modern society. However, both have limitation to cover demand from diverse populations, e.g., travelers in low-income, underserved communities. In this paper, we consider two types of travelers: Type~1 who rent shared cars and Type~2 who need shared rides. We propose … Read more

    Computing the Spark: Mixed-Integer Programming for the (Vector) Matroid Girth Problem

  • Andreas M. Tillmann
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Graphs and Matroids Tags , , , ,

    We investigate the NP-hard problem of computing the spark of a matrix (i.e., the smallest number of linearly dependent columns), a key parameter in compressed sensing and sparse signal recovery. To that end, we identify polynomially solvable special cases, gather upper and lower bounding procedures, and propose several exact (mixed-)integer programming models and linear programming … Read more

    Strong Convex Nonlinear Relaxations of the Pooling Problem

  • Claudia D'Ambrosio
  • Jeff Linderoth
  • James R. Luedtke
  • Jonas Schweiger
    • Categories Chemical Engineering, Cutting Plane Approaches, Global Optimization Tags , ,

    We investigate new convex relaxations for the pooling problem, a classic nonconvex production planning problem in which input materials are mixed in intermediate pools, with the outputs of these pools further mixed to make output products meeting given attribute percentage requirements. Our relaxations are derived by considering a set which arises from the formulation by … Read more

    Outer Approximation for Integer Nonlinear Programs via Decision Diagrams

  • Danial Davarnia
  • Willem-Jan van Hoeve
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Dynamic Programming Tags , , , ,

    As an alternative to traditional integer programming (IP), decision diagrams (DDs) provide a new solution technology for discrete problems based on their combinatorial structure and dynamic programming representation. While the literature mainly focuses on the competitive aspects of DDs as a stand-alone solver, we investigate their complementary role by studying IP techniques that can be … Read more