Integer Programming

An Exact Projection-Based Algorithm for Bilevel Mixed-Integer Problems with Nonlinearities

  • Maximilian Merkert
  • Galina Orlinskaya
  • Dieter Weninger
    • Categories (Mixed) Integer Nonlinear Programming, Game Theory, Global Optimization Tags , , , ,

    We propose an exact global solution method for bilevel mixed-integer optimization problems with lower-level integer variables and including nonlinear terms such as, \eg, products of upper-level and lower-level variables. Problems of this type are extremely challenging as a single-level reformulation suitable for off-the-shelf solvers is not available in general. In order to solve these problems … Read more

    On the Integrality Gap of Binary Integer Programs with Gaussian Data

  • Sander Borst
  • Daniel Dadush
  • Sophie Huiberts
  • Samarth Tiwari
    • Categories Integer Programming Tags , ,

    For a binary integer program (IP) $\max c^\T x, Ax \leq b, x \in \{0,1\}^n$, where $A \in \R^{m \times n}$ and $c \in \R^n$ have independent Gaussian entries and the right-hand side $b \in \R^m$ satisfies that its negative coordinates have $\ell_2$ norm at most $n/10$, we prove that the gap between the value … Read more

    Polyhedral Analysis of Symmetric Multilinear Polynomials over Box Constraints

  • Warren Adams
  • Akshay Gupte
  • Yibo Xu
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Polyhedra Tags , , , ,

    It is well-known that the convex and concave envelope of a multilinear polynomial over a box are polyhedral functions. Exponential-sized extended and projected formulations for these envelopes are also known. We consider the convexification question for multilinear polynomials that are symmetric with respect to permutations of variables. Such a permutation-invariant structure naturally implies a quadratic-sized … Read more

    On Recognizing Staircase Compatibility

  • Andreas Bärmann
  • Maximilian Merkert
  • Patrick Gemander
  • Alexander Martin
    • Categories 0-1 Programming, Graphs and Matroids, Scheduling Tags , , ,

    For the problem to find an m-clique in an m-partite graph, staircase compatibility has recently been introduced as a polynomial-time solvable special case. It is a property of a graph together with an m-partition of the vertex set and total orders on each subset of the partition. In optimization problems involving m-cliques in m-partite graphs … Read more

    A Distributionally-Robust Service Center Location Problem with Decision Dependent Demand Induced from a Maximum Attraction Principle

  • Fengqiao Luo
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Integer Programming Tags , , , ,

    We establish and analyze a service center location model with a simple but novel decision-dependent demand induced from a maximum attrac- tion principle. The model formulations are investigated in the distributionally- robust optimization framework. A statistical model that is based on the max- imum attraction principle for estimating customer demand and utility gain from service … Read more

    An Alternating Method for Cardinality-Constrained Optimization: A Computational Study for the Best Subset Selection and Sparse Portfolio Problems

  • Carina Moreira Costa
  • Dennis Kreber
  • Martin Schmidt
    • Categories (Mixed) Integer Nonlinear Programming, Finance and Economics, Statistics Tags , , , ,

    Cardinality-constrained optimization problems are notoriously hard to solve both in theory and practice. However, as famous examples such as the sparse portfolio optimization and best subset selection problems show, this class is extremely important in real-world applications. In this paper, we apply a penalty alternating direction method to these problems. The key idea is to … Read more

    Compact mixed-integer programming relaxations in quadratic optimization

  • Ben Beach
  • Robert Hildebrand
  • Joey Huchette
    • Categories (Mixed) Integer Nonlinear Programming, 0-1 Programming, Global Optimization

    We present a technique for producing valid dual bounds for nonconvex quadratic optimization problems. The approach leverages an elegant piecewise linear approximation for univariate quadratic functions due to Yarotsky, formulating this (simple) approximation using mixed-integer programming (MIP). Notably, the number of constraints, binary variables, and auxiliary continuous variables used in this formulation grows logarithmically in … Read more

    On Generating Lagrangian Cuts for Two-stage Stochastic Integer Programs

  • Rui Chen
  • James R. Luedtke
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , ,

    We investigate new methods for generating Lagrangian cuts to solve two-stage stochastic integer programs. Lagrangian cuts can be added to a Benders reformulation, and are derived from solving single scenario integer programming subproblems identical to those used in the nonanticipative Lagrangian dual of a stochastic integer program. While Lagrangian cuts have the potential to significantly … Read more

    A study of the relation between the single-row and the double-row facility layout problem

  • Mirko Dahlbeck
  • Anja Fischer
  • Philipp Hungerländer
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Facility Planning and Design Tags , ,

    The NP-hard Multi-Row Facility Layout Problem (MRFLP) consists of a set of one-dimensional departments and pairwise transport weights between them. It asks for a non-overlapping arrangement of the departments along a given number of rows such that the weighted sum of the horizontal center-to-center distances between the departments is minimized. We mainly focus on the … Read more

    Sparse Poisson regression via mixed-integer optimization

  • Kota Kudo
  • Yuichi Takano
  • Hiroki Saishu
    • Categories Integer Programming, Statistics Tags , , ,

    We present a mixed-integer optimization (MIO) approach to sparse Poisson regression. The MIO approach to sparse linear regression was first proposed in the 1970s, but has recently received renewed attention due to advances in optimization algorithms and computer hardware. In contrast to many sparse estimation algorithms, the MIO approach has the advantage of finding the … Read more