Abstract: We settle the computational complexity of
fundamental questions related to multicriteria integer linear
programs, when the dimensions of the strategy space and of the outcome
space are considered fixed constants. In particular we construct:
eprint arXiv:0707.1362 [math.OC].
Abstract: We investigate properties of Ehrhart polynomials for matroid
polytopes, independence matroid polytopes, and polymatroids. In the
first half of the paper we prove that for fixed rank their Ehrhart
polynomials are computable in polynomial time. The proof relies on the
geometry of these polytopes as well as a new refined analysis of the
evaluation of Todd polynomials. In the second half we discuss two
conjectures about the h*-vector and the coefficients of
Ehrhart polynomials of matroid polytopes; we provide theoretical and
computational evidence for their validity.
eprint arXiv:0710.4346 [math.CO].
Abstract: We show the existence of a fully polynomial-time approximation scheme
(FPTAS) for the problem of maximizing a non-negative polynomial over
mixed-integer sets in convex polytopes, when the number of variables is
fixed. Moreover, using a weaker notion of approximation, we show the
existence of a fully polynomial-time approximation scheme for the problem
of maximizing or minimizing an arbitrary polynomial over
mixed-integer sets in convex polytopes, when the number of variables is
fixed.
eprint arXiv:0706.2354 [math.OC],
Springer LINK
with PDF
Abstract: We introduce a general technique to create an extended formulation of a
mixed-integer program. We classify the integer variables into
blocks, each of which generates a finite set of vector values.
The extended formulation is constructed by creating a new binary
variable for each generated value. Initial experiments show that the
extended formulation can have a more compact complete description than
the original formulation.
We prove that, using this reformulation technique, the facet description
decomposes into one "linking
polyhedron" per block and the "aggregated polyhedron". Each of these
polyhedra can be analyzed separately. For the case of identical
coefficients in a block, we provide a complete description of the linking
polyhedron and a polynomial-time separation algorithm. Applied to the
knapsack with a fixed number of distinct coefficients, this theorem
provides a complete description in an extended space with a polynomial number
of variables.
Based on this theory, we propose a new branching scheme that analyzes the
problem structure. It is designed to be applied in
those subproblems of hard integer programs where LP-based
techniques do not provide good branching decisions.
Preliminary computational experiments show that it is successful for some
benchmark problems of multi-knapsack type.
eprint arXiv:math.OC/0603311,
Elsevier
ScienceDirect with PDF
Abstract: Computations with Barvinok's short rational generating functions are
traditionally being performed in the dual space, to avoid the combinatorial complexity
of inclusion--exclusion formulas for the intersecting proper faces of cones.
We prove that, on the level of indicator functions of polyhedra,
there is no need for using inclusion--exclusion formulas to
account for boundary effects: All linear identities in the space of
indicator functions can
be purely expressed using half-open variants of the full-dimensional polyhedra
in the identity. This gives rise to a practically efficient,
parametric Barvinok algorithm in the primal space.
Abstract:
We consider the survivable network design problem for fractional
flows and integral capacities and demands. While this problem was
modelled using so-called metric inequalities in the past, we will
present an integer program which is based on the automatic
linearization of non-linear constraints. It turns out that the linear
relaxation of the latter formulation is actually stronger than the
linear relaxations of the previously known models. Our model making
use of integrally indecomposable polytopes, we introduce a new way of
computing these polytopes via the chamber decomposition of the
parameter space.
Abstract:
We study the capacitated network design problem under survivability requirements in the model of complete
rerouting. Since there does not exist a dual characterization for the existence of integral multicommodity flows,
the literature only provides us with non-projected formulations.
In this paper, we give an algorithmic construction for a projected integer linear programming formulation for
survivable network design with integral flows. It is based on the exact automatic linearization of a nonlinear
model, using integral generating sets for families of discrete sets.
Abstract:
We introduce variants of Barvinok's algorithm for counting lattice points in
polyhedra. The new algorithms are based on irrational signed decomposition
in the primal space and the construction of rational generating functions
for cones with low index. We give computational results that show that the
new algorithms are faster than the existing algorithms by a large factor.
Abstract: This paper is based on the study of the set of nondecomposable
integer solutions in a Gomory corner polyhedron, which was recently used
in a reformulation method for integer linear programs. In this paper, we
present an algorithm for efficiently computing this set. We precompute
a database of nondecomposable solutions for cyclic groups up to
order 52. As a second application of this database,
we introduce an algorithm for computing
nontrivial simultaneous lifting coefficients. The lifting coefficients
are exact for a discrete relaxation of the integer program that consists of
a group relaxation plus bound constraints.
Preprint
(revised) (PDF), Springer LINK
with PDF
Abstract:
We classify, according to their computational complexity, integer
optimization problems whose constraints and objective functions are
polynomials with integer coefficients and the number of variables is
fixed. For the optimization of an integer polynomial over
the lattice points of a convex polytope, we show an algorithm to compute
lower and upper bounds for the optimal value.
For polynomials that are non-negative over the polytope,
these sequences of bounds lead to a fully polynomial-time approximation
scheme for the optimization problem.
Abstract: We show the existence of an FPTAS for the problem
of maximizing a non-negative polynomial over mixed-integer sets in
convex polytopes, when the number of variables is fixed.
eprint arXiv:math.OC/0505677.
Abstract: We present several types of extended formulations for integer programs,
based on irreducible integer solutions to Gomory's group relaxations. We
present an algorithm based on an iterative reformulation technique using these extended
formulations. We give computational results for benchmark problems, which
illustrate the primal and dual effect of the reformulation.
Preprint
(revised) (Postscript), Elsevier
ScienceDirect with text and PDF
Abstract: In this paper some operations are described that transform every graph
into a perfect graph by replacing nodes with sets of new nodes. The
transformation is done in such a way that every stable set in the perfect
graph corresponds to a stable set in the original graph. These
operations yield a purely combinatorial augmentation procedure for
finding a maximum weighted stable set in a graph. Starting with a
stable set in a given graph one defines a simplex type tableau whose
associated basic feasible solution is the incidence vector of the
stable set. In an iterative fashion, non-basic columns that would
lead to pivoting into non-integral basic feasible solutions, are
replaced by new columns that one can read off from special graph
structures such as odd holes, odd antiholes, and various
generalizations. Eventually, either a pivot leading to an integral
basic feasible solution is performed, or the optimality of the current
solution is proved.
Preprint (Postscript)
Abstract: We present a mixed integer version of the lattice
analogue of the Farkas Lemma. The result gives rise to a family of
mixed-integer rounding cutting planes for mixed integer programs,
which depend on the choice of a basis of a certain lattice. By
choosing a Lovász-reduced lattice basis, one can hope to generate
numerically advantageous cutting planes.
Preprint (revised
revised) (Postscript),
Elsevier
ScienceDirect with text and PDF
Abstract: This paper introduces an
algorithm for solving mixed integer programs. The core of the method
is an iterative technique for changing the representation of the
original mixed integer optimization problem.
Preprint
(revised) (Postscript).
Springer LINK
with PDF
Abstract: This paper introduces an exact primal augmentation
algorithm for solving general linear integer programs. The algorithm
iteratively substitutes one column in a tableau by other columns that
correspond to irreducible solutions of certain linear diophantine
inequalities. We prove that various versions of our algorithm are
finite. It is a major concern in this paper to show how the subproblem
of replacing a column can be accomplished effectively. An
implementation of the presented algorithms is given. Computational
results for a number of hard 0/1 integer programs from the MIPLIB
demonstrate the practical power of the method.
Preprint (Postscript),
Springer LINK
with PDF
Abstract: This paper addresses the question of
decomposing an infinite family of rational polyhedra in an integer
fashion. It is shown that there is a finite subset of this family that
generates the entire family. Moreover, an integer analogue of
Carathéodory's theorem carries over to this general setting. The
integer decomposition of a family of polyhedra has different
applications in integer and mixed integer programming.
Preprint
(Postscript), Springer
LINK with PDF
This is the conference version of the paper On the Way to Perfection: Primal Operations for Stable Sets in Graphs.
Abstract:
This paper introduces an exact algorithm for solving integer
programs, neither using cutting planes nor enumeration techniques.
It is a primal augmentation algorithm that relies on iteratively
substituting one column by columns that correspond to irreducible
solutions of certain linear diophantine inequalities. We demonstrate
the algorithm's potential by testing it
on some instances of the MIPLIB with up to 6000 variables.
Preprint (Postscript), BibTeX entry, Springer LINK with PDF
Abstract: Two well-known bifurcation routes to
chaos of two-dimensional coupled logistic maps are embedded in a
two-parameter plane of a canonical nonlinear oscillator which contains
a non-analytic analogon to the Mandelbrot set.
The dissertation is also available as a
PDF
file
from Shaker Verlag.
Thesis (Postscript, in German),
Abstract (Postscript, in
German), BibTeX entry
Abstract: This paper deals with algorithmic issues related
to the design of an augmentation algorithm for general and 0/1-integer
programs. We recall the approach of integer pivoting and introduce the
family of Gomory-Young augmentation vectors that can be derived from a
simplex tableau. Furthermore, a technique of combining Gomory-Young
vectors and combinatorial augmentation vectors in one augmentation
scheme is presented. Two computational experiments demonstrate the
potential of pivoting in an integer fashion.
Technical Report (Postscript)
- Publications -
- Theses -
- Technical Reports -