A Total Unimodularity Based Branch-and-Bound Method for Integer Programming

Author

Wang, Jun ; Long, Mei ; Li, Duan

Author_Institution

Dept. of Manage. Sci. & Eng., Qingdao Univ.

fYear

2006

fDate

4-7 Dec. 2006

Firstpage

642

Lastpage

645

Abstract

We consider a novel solution method for integer programming problems with a 0-plusmn1 constraint matrix, which include set covering problem (SCP) and satisfiability problem (SAT) as special cases. Specifically, a branching rule is designed to actively make a satisfaction of total unimodularity (TU), thus speeding up the convergence of the search process in the branch-and-bound method. This TU-based branch-and-bound method is tested for a family of random 3-SAT problems and is compared with the IP solver of ILOG CPLEX. Computational experience shows that this new solution scheme is efficient

Keywords

computability; integer programming; matrix algebra; tree searching; ILOG CPLEX; IP solver; branch-and-bound method; branching rule; constraint matrix; integer programming; satisfiability problem; search process; set covering problem; total unimodularity; Decision making; Engineering management; Heuristic algorithms; Linear programming; Polynomials; Research and development management; Sufficient conditions; Systems engineering and theory; Testing; Vectors;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 2006. APCCAS 2006. IEEE Asia Pacific Conference on

Conference_Location

Singapore

Print_ISBN

1-4244-0387-1

Type

conf

DOI

10.1109/APCCAS.2006.342089

Filename

4145475