Refine
Year of publication
- 2009 (6) (remove)
Document Type
- In Proceedings (4)
- ZIB-Report (2)
Language
- English (6)
Is part of the Bibliography
- no (6)
Keywords
- Connectivity (1)
- Generalization (1)
- Partition Inequalities (1)
- Paths (1)
- Pseudo-Boolean (1)
- Steiner Tree (1)
- constraint integer programming (1)
- domain propagation (1)
- linear relaxation (1)
- separation algorithm (1)
The Steiner connectivity problem is a generalization of the Steiner tree problem. It consists in finding a minimum cost set of simple paths to connect a subset of nodes in an undirected graph. We show that polyhedral and algorithmic results on the Steiner tree problem carry over to the Steiner connectivity problem, namely, the Steiner cut and the Steiner partition inequalities, as well as the associated polynomial time separation algorithms, can be generalized. Similar to the Steiner tree case, a directed formulation, which is stronger than the natural undirected one, plays a central role.
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.