Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > INTEGER PROGRAMMING:
Reports tagged with integer programming:
TR99-020 | 9th June 1999
Marek Karpinski

#### Randomized Complexity of Linear Arrangements and Polyhedra

We survey some of the recent results on the complexity of recognizing
n-dimensional linear arrangements and convex polyhedra by randomized
algebraic decision trees. We give also a number of concrete applications
of these results. In particular, we derive first nontrivial, in fact
quadratic, ... more >>>

TR00-017 | 3rd March 2000
Valentin E. Brimkov, Stefan S. Dantchev

#### On the Algebraic Complexity of Integer Programming

In the framework of the Blum-Shub-Smale real number model \cite{BSS}, we study the {\em algebraic complexity} of the integer linear programming problem
(ILP$_{\bf R}$) : Given a matrix $A \in {\bf R}^{m \times n}$ and vectors
$b \in {\bf R}^m$, $d \in {\bf R}^n$, decide if there is $x ... more >>> TR03-041 | 29th May 2003 Albert Atserias, Maria Luisa Bonet, Jordi Levy #### On Chvatal Rank and Cutting Planes Proofs We study the Chv\'atal rank of polytopes as a complexity measure of unsatisfiable sets of clauses. Our first result establishes a connection between the Chv\'atal rank and the minimum refutation length in the cutting planes proof system. The result implies that length lower bounds for cutting planes, or even for ... more >>> TR07-010 | 4th January 2007 Arist Kojevnikov #### Improved Lower Bounds for Resolution over Linear Inequalities Revisions: 1 We continue a study initiated by Krajicek of a Resolution-like proof system working with clauses of linear inequalities, R(CP). For all proof systems of this kind Krajicek proved an exponential lower bound that depends on the maximal absolute value of coefficients in the given proof and the maximal clause width. ... more >>> TR07-107 | 26th October 2007 Nathan Segerlind #### Exponential lower bounds and integrality gaps for tree-like Lovasz-Schrijver procedures The matrix cuts of Lov{\'{a}}sz and Schrijver are methods for tightening linear relaxations of zero-one programs by the addition of new linear inequalities. We address the question of how many new inequalities are necessary to approximate certain combinatorial problems with strong guarantees, and to solve certain instances of Boolean satisfiability. ... more >>> TR14-024 | 19th February 2014 Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider #### 0-1 Integer Linear Programming with a Linear Number of Constraints We give an exact algorithm for the 0-1 Integer Linear Programming problem with a linear number of constraints that improves over exhaustive search by an exponential factor. Specifically, our algorithm runs in time$2^{(1-\text{poly}(1/c))n}$where$n$is the number of variables and$cn\$ is the number of constraints. The key ... more >>>

TR21-012 | 9th February 2021
Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson

#### On the Power and Limitations of Branch and Cut

Revisions: 1

The Stabbing Planes proof system was introduced to model the reasoning carried out in practical mixed integer programming solvers. As a proof system, it is powerful enough to simulate Cutting Planes and to refute the Tseitin formulas -- certain unsatisfiable systems of linear equations mod 2 -- which are canonical ... more >>>

ISSN 1433-8092 | Imprint