Refine
Language
- English (10)
Keywords
- integer programming (2)
- symmetry breaking (2)
- Markov decision problem (1)
- column generation (1)
- lexicographic representatives (1)
- linear programming (1)
- orbitopes (1)
- variable fixing (1)
We discuss the problem to count, or, more modestly, to estimate
the number f(m; n) of unimodular triangulations of the planar grid of
size m * n.
Among other tools, we employ recursions that allow one to compute
the (huge) number of triangulations for small m and rather large n by
dynamic programming; we show that this computation can be done in
polynomial time if m is fixed, and present computational results from
our implementation of this approach.
We also present new upper and lower bounds for large m and n,
and we report about results obtained from a computer simulation of
the random walk that is generated by
ips.
We investigate the worst-case behavior of the simplex algorithm on linear programs
with 3 variables, that is, on 3-dimensional simple polytopes. Among the
pivot rules that we consider, the “random edge” rule yields the best asymptotic
behavior as well as the most complicated analysis. All other rules turn out to be
much easier to study, but also produce worse results: Most of them show essentially
worst-possible behavior; this includes both Kalai’s “random-facet” rule, which is
known to be subexponential without dimension restriction, as well as Zadeh’s deterministic
history-dependent rule, for which no non-polynomial instances in general
dimensions have been found so far.
Abstract. Let Xd,n be an n-element subset of {0, 1}d chosen uniformly
at random, and denote by Pd,n := conv Xd,n its convex hull. Let ∆d,n
be the density of the graph of Pd,n (i.e., the number of one-dimensional
faces of Pd,n divided by n ). Our main result is that, for any function 2
n(d), the expected value of ∆d,n(d) converges (with d → ∞) to one if, √
for some arbitrary ε < 0, n(d) ≤ ( 2 − ε)d holds for all large d, while it √
converges to zero if n(d) ≥ ( 2 + ε)d holds for all large d.
Abstract. Let P be a random 0/1-polytope in Rd with n(d) vertices, and denote by νr (P ) the
quotient of the number of faces of P with exactly r vertices and n(d) (the r-density of P ). For each
r
r ≥ 3, we establish the existence of a sharp threshold for the r-density and determine the values of
the threshold numbers τr such that, for all ε > 0,
E [νr (P )] =
1 − o(1)
o(1)
if n(d) ≤ 2(τr −ε)d for all d
if n(d) ≥ 2(τr +ε)d for all d
holds for the expected value of νr (P ). The threshold for r = 2 has already been determined in [8].
In particular, these results indicate that the high densities often encountered in polyhedral com-
binatorics (e.g., the cut-polytope has both 2- and 3-density equal to one) is due to the geometry of
0/1-polytopes rather than to the special combinatorics of the underlying problems.
We introduce orbitopes as the convex hulls of 0/1-matrices that are lexicographically maximal subject to a group acting on the
columns. Special cases are packing and partitioning orbitopes, which
arise from restrictions to matrices with at most or exactly one 1-entry
in each row, respectively. The goal of investigating these polytopes is to
gain insight into ways of breaking certain symmetries in integer programs
by adding constraints, e.g., for a well-known formulation of the graph
coloring problem.
We provide a thorough polyhedral investigation of packing and partitioning orbitopes for the cases in which the group acting on the columns
is the cyclic group or the symmetric group. Our main results are complete linear inequality descriptions of these polytopes by facet-defining
inequalities. For the cyclic group case, the descriptions turn out to be
totally unimodular, while for the symmetric group case both the description and the proof are more involved. Nevertheless, the associated
separation problem can be solved in linear time also in this case.
The standard computational methods for computing the optimal value functions of Markov Decision Problems (MDP) require the exploration of the entire state space. This is practically infeasible for applications with huge numbers of states as they arise, e.g., from modeling the decisions in online optimization problems by MDPs. Exploiting column generation techniques, we propose and apply an LP-based method to determine an epsilon-approximation of the optimal value function at a given state by inspecting only states in a small neighborhood. In the context of online optimization problems, we use these methods in order to evaluate the quality of concrete policies with respect to given initial states. Moreover, the tools can also be used to obtain evidence of the impact of single decisions. This way, they can be utilized in the design of policies.
The Bottleneck Shortest Path Problem is a basic problem
in network optimization. The goal is to determine the limiting capacity of any path between two specified vertices of the network. This is
equivalent to determining the unsplittable maximum flow between the
two vertices. In this note we analyze the complexity of the problem, its
relation to the Shortest Path Problem, and the impact of the underlying
machine/computation model.
We prove that the Random-Edge simplex algorithm requires an
expected number of at most 13n/pd pivot steps on any simple d-polytope with
n vertices. This is the first nontrivial upper bound for general polytopes. We
also describe a refined analysis that potentially yields much better bounds for
specific classes of polytopes. As one application, we show that for combinatorial
d-cubes, the trivial upper bound of 2d on the performance of Random-Edge
can asymptotically be improved by any desired polynomial factor in d.
Revlex-Initial 0/1-Polytopes
(2005)
Orbitopal Fixing
(2007)
The topic of this paper are integer programming models in which a subset of 0/1-variables encode a partitioning of a set of objects into disjoint subsets. Such models can be surprisingly hard to solve by branch-and-cut algorithms if the order of the subsets of the partition is irrelevant. This kind of symmetry unnecessarily blows up the branch-and-cut tree.
We present a general tool, called orbitopal fixing, for enhancing the capabilities of branch-and-cut algorithms in solving such symmetric integer programming models. We devise a linear time algorithm that,
applied at each node of the branch-and-cut tree, removes redundant parts
of the tree produced by the above mentioned symmetry. The method relies on certain polyhedra, called orbitopes, which have been investigated in (Kaibel and Pfetsch 2007). It does, however, not add inequalities to the model, and thus, it does not increase the difficulty of solving the linear programming relaxations. We demonstrate the computational power of orbitopal fixing at the example of a graph partitioning problem motivated from frequency planning in mobile telecommunication networks.