ZIB-Report
Refine
Year of publication
Document Type
- ZIB-Report (425)
- Habilitation (4)
Keywords
- mixed integer programming (25)
- integer programming (21)
- constraint integer programming (13)
- branch-and-bound (11)
- mixed-integer programming (11)
- Mixed Integer Programming (9)
- Optimierung (9)
- MINLP (8)
- combinatorial optimization (8)
- line planning (8)
Institute
- Mathematical Optimization (429) (remove)
13-42
Primal heuristics are an important component of state-of-the-art codes for mixed integer nonlinear programming (MINLP). In this article we give a compact overview of primal heuristics for MINLP that have been suggested in the literature of recent years. We sketch the fundamental concepts of different classes of heuristics and discuss specific implementations. A brief computational experiment shows that primal heuristics play a key role in achieving feasibility and finding good primal bounds within a global MINLP solver.
13-45
Usually complete linear descriptions of polytopes consist of
an enormous number of facet-defining inequalities already
for very small problem sizes. In this paper, we describe a method
for dividing the inequalities into equivalence classes without resorting to a normal form. Within each
class, facets are related by certain symmetries and it is sufficient
to list one representative of each class to give a complete
picture of the structural properties of a polytope. We propose an algorithm
for the classification and illustrate its efficiency on a broad range of combinatorial optimization problems including the Traveling Salesman and the Linear Ordering Problem.
13-39
Let the design of an
experiment be represented by an $s$-dimensional vector
$\vec{w}$ of weights with non-negative components. Let the quality of
$\vec{w}$ for the estimation of the parameters of the statistical model
be measured by the criterion of $D$-optimality defined as the $m$-th root
of the determinant of the information matrix $M(\vec{w})=\sum_{i=1}^s
w_iA_iA_i^T$, where $A_i$, $i=1,...,s$, are known matrices with $m$ rows.
In the paper, we show that the criterion of $D$-optimality is second-order
cone representable. As a result, the method of second order cone
programming can be used to compute an approximate $D$-optimal design with
any system of linear constraints on the vector of weights. More
importantly, the proposed characterization allows us to compute an
\emph{exact} $D$-optimal design, which is possible thanks to high-quality
branch-and-cut solvers specialized to solve mixed integer second order cone
problems.
We prove that some other widely used criteria are also second order cone
representable, for instance the criteria of $A$-, and $G$-optimality, as
well as the criteria of $D_K$- and $A_K$-optimality, which are extensions
of $D$-, and $A$-optimality used in the case when only a specific system of
linear combinations of parameters is of interest.
We present several numerical examples demonstrating the efficiency and
universality of the proposed method. We show that in many cases the mixed
integer second order cone programming approach allows us to find a provably
optimal exact design, while the standard heuristics systematically miss the
optimum.
13-54
We extend the primal-dual approximation technique of Goemans and Williamson to the Steiner connectivity problem, a kind of Steiner tree problem in hypergraphs. This yields a (k+1)-approximation algorithm for the case that k is the minimum of the maximal number of nodes in a hyperedge minus 1 and the maximal number of terminal nodes in a hyperedge. These results require the proof of a degree property for terminal nodes in hypergraphs which generalizes the well-known graph property that the average degree of terminal nodes in Steiner trees is at most 2.
13-55
Recently, parallel computing environments have become significantly popular. In order to obtain the benefit of using parallel computing environments, we have to deploy our programs for these effectively. This paper focuses on a parallelization of SCIP (Solving Constraint Integer Programs), which is a MIP solver and constraint integer programming framework available in source code. There is a parallel extension of SCIP named ParaSCIP, which parallelizes SCIP on massively parallel distributed memory computing environments. This paper describes FiberSCIP, which is yet another parallel extension of SCIP to utilize multi-threaded parallel computation on shared memory computing environments, and has the following contributions: First, the basic concept of having two parallel extensions and the relationship between them and the parallelization framework provided by UG (Ubiquity Generator) is presented, including an implementation of deterministic parallelization. Second, the difficulties to achieve a good performance that utilizes all resources on an actual computing environment and the difficulties of performance evaluation of the parallel solvers are discussed. Third, a way to evaluate the performance of new algorithms and parameter settings of the parallel extensions is presented. Finally, current performance of FiberSCIP for solving mixed-integer linear programs (MIPs) and mixed-integer non-linear programs (MINLPs) in parallel is demonstrated.
13-66
Contemporary supercomputers can easily provide years of
CPU time per wall-clock hour. One challenge of today's software
development is how to harness this wast computing power in order to solve
really hard mixed integer programming instances. In 2010, two out of
six open MIPLIB2003 instances could be solved by ParaSCIP in more than
ten consecutive runs, restarting from checkpointing files.
The contribution of this paper is threefold:
For the first time, we present computational results of single runs for
those two instances. Secondly, we provide new improved upper and lower
bounds for all of the remaining four open MIPLIB2003 instances.
Finally, we explain which new developments led to these results and
discuss the current progress of ParaSCIP. Experiments were conducted on
HLRNII, on HLRN III, and on the Titan supercomputer, using up to 35,200 cores.
13-48
Presolving attempts to eliminate redundant information from the problem formulation and simultaneously tries to strengthen the formulation. It can be very effective and is often essential for solving instances. Especially for mixed integer programming problems, fast and effective presolving algorithms are very important. In this paper, we report on three new presolving techniques. The first method searches for singleton continuous columns and tries to fix the corresponding variables. Then we present a presolving technique which exploits a partial order of the variables to induce fixings. Finally, we show an approach based on connected components in graphs. Our computational results confirm the profitable use of the algorithms in practice.
13-47
One of the essential components of a branch-and-bound based mixed-integer linear programming (MIP) solver is the branching rule. Strong branching is a method used by many state-of-the-art branching rules to select the variable to branch on. It precomputes the dual bounds of potential child nodes by solving auxiliary linear programs (LPs) and thereby helps to take good branching decisions that lead to a small search tree. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Domain propagation is a technique usually used at every node of the branch-and-bound tree to tighten the local domains of variables. Computational experiments on standard MIP instances indicate that our improved strong branching method significantly improves the quality of the predictions and causes almost no additional effort. For a full strong branching rule, we are able to obtain substantial reductions of the branch-and-bound tree size as well as the solving time. Moreover, also the state-of-the-art hybrid branching rule can be improved this way.
This paper extends previous work by the author published in the proceedings of the CPAIOR 2013.
13-67
We consider a system dynamics model that describes the effect of human activity on natural resources. The central stocks are the accumulated profit, the industry structures, and the water resources. The model can be controlled through two time-dependent parameters. The goal in this paper is to find a parameter setting that leads to a maximization of a performance index, which reflects both environmental and economic aspects. Thus, the goal is to identify the most sustainable stock of industry structures within the model's constraints and assumptions. In order to find a proven global optimal parameter set, we formulate the System Dynamics Optimization model as a mixed-integer nonlinear problem that is accessible for numerical solvers. Due to the dynamic structure of the model, certain steps of the solution process must be handled with greater care, compared to standard non-dynamic problems. We describe our approach of solving the industry structure model and present computational results. In addition, we discuss the limitations of the approach and next steps.