## 90C09 Boolean programming

### Refine

#### Document Type

- ZIB-Report (4)

#### Language

- English (4)

#### Has Fulltext

- yes (4)

#### Is part of the Bibliography

- no (4)

#### Keywords

- ATSP (1)
- Constraintprogrammierung (1)
- Ganzzahlige Programmierung (1)
- Konfliktanalyse (1)
- Primalheuristik (1)
- Pseudo-Boolean (1)
- bisection (1)
- conflict learning (1)
- constraint integer programming (1)
- constraint programming (1)

#### Institute

Learning during search allows solvers for discrete optimization problems to remember parts of the search that they have already performed and avoid revisiting redundant parts. Learning approaches pioneered by the SAT and CP communities have been successfully incorporated into the SCIP constraint integer programming platform. In this paper we show that performing a heuristic constraint programming search during root node processing of a binary program can rapidly learn useful nogoods, bound changes, primal solutions, and branching statistics that improve the remaining IP search.

Pseudo-Boolean problems lie on the border between satisfiability problems, constraint programming, and integer programming. In particular, nonlinear constraints in pseudo-Boolean optimization can be handled by methods arising in these different fields: One can either linearize them and work on a linear programming relaxation or one can treat them directly by propagation. In this paper, we investigate the individual strengths of these approaches and compare their computational performance. Furthermore, we integrate these techniques into a branch-and-cut-and-propagate framework, resulting in an efficient nonlinear pseudo-Boolean solver.

The recent spectral bundle method allows to compute, within reasonable time, approximate dual solutions of large scale semidefinite quadratic 0-1 programming relaxations. We show that it also generates a sequence of primal approximations that converge to a primal optimal solution. Separating with respect to these approximations gives rise to a cutting plane algorithm that converges to the optimal solution under reasonable assumptions on the separation oracle and the feasible set. We have implemented a practical variant of the cutting plane algorithm for improving semidefinite relaxations of constrained quadratic 0-1 programming problems by odd-cycle inequalities. We also consider separating odd-cycle inequalities with respect to a larger support than given by the cost matrix and present a heuristic for selecting this support. Our preliminary computational results for max-cut instances on toroidal grid graphs and balanced bisection instances indicate that warm start is highly efficient and that enlarging the support may sometimes improve the quality of relaxations considerably.

The m-Cost ATSP
(1999)

Although the m-ATSP (or multi traveling salesman problem) is well known for its importance in scheduling and vehicle routing, it has, to the best of our knowledge, never been studied polyhedraly, i.e., it has always been transformed to the standard ATSP. This transformation is valid only if the cost of an arc from node $i$ to node $j$ is the same for all machines. In many practical applications this is not the case, machines produce with different speeds and require different (usually sequence dependent) setup times. We present first results of a polyhedral analysis of the m-ATSP in full generality. For this we exploit the tight relation between the subproblem for one machine and the prize collecting traveling salesman problem. We show that, for $m\ge 3$ machines, all facets of the one machine subproblem also define facets of the m-ATSP polytope. In particular the inequalities corresponding to the subtour elimination constraints in the one machine subproblems are facet defining for m-ATSP for $m\ge 2$ and can be separated in polynomial time. Furthermore, they imply the subtour elimination constraints for the ATSP-problem obtained via the standard transformation for identical machines. In addition, we identify a new class of facet defining inequalities of the one machine subproblem, that are also facet defining for m-ATSP for $m\ge 2$. To illustrate the efficacy of the approach we present numerical results for a scheduling problem with non-identical machines, arising in the production of gift wrap at Herlitz PBS AG.