On Using Cutting Planes in Pseudo-Boolean Optimization

作     者：Vasco M. Manquinho João Marques-Silva 

作者机构：IST/INESC-ID Technical University of Lisbon Portugal. E-mail: University of Southampton UK. E-mail: 

出 版 物：《Journal on Satisfiability, Boolean Modelling and Computation》 

年 卷 期：2006年第2卷第1-4期

页      面：209 - 219页

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：pseudo-Boolean optimization cutting planes search restarts 

摘      要：Cutting planes are a well-known, widely used, and very effective technique for Integer Linear Programming (ILP). However, cutting plane techniques are seldom used in Pseudo-Boolean Optimization (PBO) algorithms. This paper addresses the utilization of Gomory mixed-integer and clique cuts, in Satisfiability-based algorithms for PBO, and shows how these cuts can be used for computing lower bounds and for learning new constraints. A side result of learning new constraints is that the utilization of cutting planes enables non-chronological backtracking. Besides cutting planes, the paper also shows that the utilization of search restarts in PBO can be effective in practice, allowing the computation of tighter lower bounds each time the search restarts. The more aggressive lower bounds result from the constraints learned due to the utilization of cutting planes. Experimental results show that the integration of cutting planes and search restarts in a SAT-based algorithm for PBO yields a competitive new solution for PBO.