  


On the Size of Integer Programs with Bounded Coefficients or Sparse Constraints
Christopher Hojny(hojnymathematik.tudarmstadt.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 (holefree) integer set can be described by an extended integer formulation using at most three nonzero 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/1problems, we also introduce a technique to compute a tight lower bound on the number of nonzeros 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 mixedinteger programs. All results are illustrated by examples. Keywords: mixedinteger 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  