Optimization Online


On the Size of Integer Programs with Bounded Coefficients or Sparse Constraints

Christopher Hojny (hojny***at***mathematik.tu-darmstadt.de)
Hendrik Lüthen (luethen***at***mathematik.tu-darmstadt.de)
Marc E. Pfetsch (pfetsch***at***mathematik.tu-darmstadt.de)

Abstract: Integer programming formulations describe optimization problems over a set of integer points. A fundamental problem is to determine the minimal size of such formulations, in particular, if the size of the coefficients or sparsity of the constraints is bounded. This article considers lower and upper bounds on these sizes both in the original and in extended spaces, i.e., if additional variables are allowed. We show that every bounded (hole-free) integer set can be described by an extended integer formulation using at most three non-zero coefficients which are +1 or -1. In the original space, we provide lower bounds on the size of integer formulations with bounded coefficients. For 0/1-problems, we also introduce a technique to compute a tight lower bound on the number of non-zeros of integer formulations in the original space. Moreover, we present statistics on these bounds in small dimensions. Finally, we consider conditions on the representability of integer optimization problems with arbitrary objective function as mixed-integer programs. All results are illustrated by examples.

Keywords: mixed-integer program, bounded coefficients, sparsity, extended formulation

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Citation: TU Darmstadt, Department of Mathematics, Research Group Optimization, Dolivostr. 15, 64293 Darmstadt, June 2017

Download: [PDF]

Entry Submitted: 06/02/2017
Entry Accepted: 06/02/2017
Entry Last Modified: 01/19/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society