### Refine

#### Year of publication

#### Document Type

- ZIB-Report (15)
- In Proceedings (5)
- Article (4)
- Bachelor's Thesis (1)
- Master's Thesis (1)

#### Keywords

#### Institute

Primal heuristics are an important component of state-of-the-art codes for
mixed integer programming. In this paper, we focus on primal heuristics
that only employ computationally inexpensive procedures such as rounding
and logical deductions (propagation). We give an overview of eight
different approaches. To assess the impact of these primal heuristics on
the ability to find feasible solutions, in particular early during search,
we introduce a new performance measure, the primal integral. Computational
experiments evaluate this and other measures on MIPLIB~2010 benchmark
instances.

Many practically relevant problems can be formulated in terms of a mixed integer programming (MIP) model. MIP denotes the
optimization of a linear objective function under a certain number of linear side constraints including the need for
some of the involved variables to take integral solution values.
Applications of MIP based optimization can be found in the area of public transit,
scheduling, automatic vehicle routing,
network design, etc.
From a complexity point of view, MIP solving is known to be NP-hard and most commonly tried to be solved via
Branch-and-Bound based algorithms. Branch-and-Bound algorithms benefit from early and good feasible solutions of a MIP
in various ways.
Primal heuristics are aimed at finding new solutions during the MIP solving process. There are different types of primal heuristics:
while start heuristics are particularly
valuable to find an early solution, improvement heuristics hopefully drive a given solution further towards optimality.
This thesis focusses on primal heuristics which are part of the MIP-solving framework SCIP.
The first chapter comes with basic definitions and a brief description of SCIP and the test set which we used.
The remainder of the first chapter is an overview of the existing heuristics in SCIP which have been implemented by Achterberg
and Berthold.
In the following chapters we introduce three new heuristics which apply rounding or propagation techniques for their specific purpose,
namely the new rounding heuristic ZI Round, taken from Wallace, a 2-Opt improvement
heuristic for MIP and the propagation heuristic Shift-and-Propagate.
It is characteristic of all three heuristics that they mainly apply computationally inexpensive algorithms.
Each of them is presented in an own chapter, starting with an algorithmic description, followed by implementational details.
All chapters close with a discussion of the computational results obtained with the respective implementations in SCIP.

Shift-And-Propagate
(2013)

For mixed integer programming, recent years have seen a growing interest in the design of general purpose primal heuristics for use inside complete solvers. Many of these heuristics rely on an optimal LP solution. Finding this may itself take a significant amount of time.
The presented paper addresses this issue by the introduction of the Shift-And-Propagate heuristic. Shift-And-Propagate is a pre-root primal heuristic that does not require a previously found LP solution. It applies domain propagation techniques to quickly drive a variable assignment towards feasibility. Computational experiments indicate that this heuristic is a powerful supplement of existing rounding and propagation heuristics.

This article describes new features and enhanced algorithms made available in version 5.0 of the SCIP Optimization Suite. In its central component, the constraint integer programming solver SCIP, remarkable performance improvements have been achieved for solving mixed-integer linear and nonlinear programs. On MIPs, SCIP 5.0 is about 41 % faster than SCIP 4.0 and over twice as fast on instances that take at least 100 seconds to solve. For MINLP, SCIP 5.0 is about 17 % faster overall and 23 % faster on instances that take at least 100 seconds to solve. This boost is due to algorithmic advances in several parts of the solver such as cutting plane generation and management, a new adaptive coordination of large neighborhood search heuristics, symmetry handling, and strengthened McCormick relaxations for bilinear terms in MINLPs. Besides discussing the theoretical background and the implementational aspects of these developments, the report describes recent additions for the other software packages connected to SCIP, in particular for the LP solver SoPlex, the Steiner tree solver SCIP-Jack, the MISDP solver SCIP-SDP, and the parallelization framework UG.

Modern MIP solvers employ dozens of auxiliary algorithmic components to support the branch-and-bound search in finding and improving primal solutions and in strengthening the dual bound.
Typically, all components are tuned to minimize the average running time to prove optimality. In this article, we take a different look at the run of a MIP solver. We argue that the solution process consists of three different phases, namely achieving feasibility, improving the incumbent solution, and proving optimality. We first show that the entire solving process can be improved by adapting the search strategy with respect to the phase-specific aims using different control tunings. Afterwards, we provide criteria to predict the transition between the individual phases and evaluate the performance impact of altering the algorithmic behavior of the MIP solver SCIP at the predicted phase transition points.

Shift-and-Propagate
(2014)

In recent years, there has been a growing interest in the design of general purpose primal heuristics for use inside complete mixed integer programming solvers. Many of these heuristics rely on an optimal LP solution, which may take a significant amount of time to find. In this paper, we address this issue by introducing a pre-root primal heuristic that does not require a previously found LP solution. This heuristic, named Shift-and-Propagate , applies domain propagation techniques to quickly drive a variable assignment towards feasibility. Computational experiments indicate that this heuristic is a powerful supplement to existing rounding and propagation heuristics.

Modern solving software for mixed-integer programming (MIP)
incorporates numerous algorithmic components whose behavior is
controlled by user parameter choices,
and whose usefulness dramatically varies depending on the progress of the solving process.
In this thesis, our aim is to
construct a phase-based solver that dynamically reacts
on phase transitions with an appropriate change of its component behavior.
Therefore, we decompose the branch-and-bound solving process into three distinct phases:
The first phase objective is to find a feasible solution. During the second phase,
a sequence of incumbent solutions gets constructed
until the incumbent is eventually optimal. Proving
optimality is the central objective of the remaining third phase.
Based on the MIP-solver SCIP we construct a phase-based solver to make use of the phase concept in two steps:
First, we identify promising components for every solving phase individually and show that their
combination is beneficial on a test bed of practical MIP instances.
We then present and evaluate three heuristic criteria to make use of the phase-based solver
in practice, where it is infeasible to distinguish between the last two phases
before the termination of the solving process.

The selection of a good branching variable is crucial for small search trees in Mixed Integer Programming. Most modern solvers employ a strategy guided by history information, mainly the variable pseudo-costs, which are used to estimate the objective gain. At the beginning
of the search, such information is usually collected via an expensive look-ahead strategy called strong-branching until variables are considered reliable.
The reliability notion is thereby mostly based on fixed-number thresholds, which may lead to ineffective branching decisions on problems with highly varying objective gains.
We suggest two new notions of reliability motivated by mathematical statistics that take into account the sample variance of the past observations on each variable individually. The first method prioritizes additional strong-branching look-aheads on variables whose pseudo-costs
show a large variance by measuring the relative error of a pseudo-cost confidence interval. The second method performs a two-sample Student-t test for filtering branching candidates with a high probability to be better than the best history candidate.
Both methods were implemented in the MIP-solver SCIP and computational results on standard MIP test sets are presented.

The selection of a good branching variable is crucial for small search trees in Mixed Integer Programming. Most modern solvers employ a strategy guided by history information, mainly the variable pseudo-costs, which are used to estimate the objective gain. At the beginning of the search, such information is usually collected via an expensive look-ahead strategy called strong branching until variables are considered reliable.
The reliability notion is thereby mostly based on fixed-number thresholds, which may lead to ineffective branching decisions on problems with highly varying objective gains.
We suggest two new notions of reliability motivated by mathematical statistics that take into account the sample variance of the past observations on each variable individually. The first method prioritizes additional strong branching look-aheads on variables whose pseudo-costs show a large variance by measuring the relative error of a pseudo-cost confidence interval. The second method performs a specialized version of a two-sample Student’s t -test for filtering branching candidates with a high probability to be better than the best history candidate.
Both methods were implemented in the MIP-solver SCIP and computational results on standard MIP test sets are presented.