Order and Bound: a New Method to Solve 0-1 Integer Programs

The Order and Bound method solves general 0-1 problems of the form: P: Min cx s.t. { Ax ≥ b; xi ∈ {0, 1} ∀ i = 1... n} where c ∈ <n, b ∈ <m, A ∈ <m×n and rational; or, in general, where x ∈ S ∩Bn, S being any subset in <n. Without loss of generality we may always assume (up to renaming variables) that the vector c is ordered, i.e. ci ≤ cj if i < j. Here, we will hold true this assumption unless otherwise stated. The rationale behind the ”Order and Bound ” algorithm is very simple. We, first, partition the set S = {x ∈ Bn/Ax ≥ b} through the set Sk = {x ∈ Bn/Ax ≥ b,∑ni=1 xi = k} for k = 0... n. We know that we can solve problem P by solving at most n+1 problems P k i.e. by finding Zk = min {cx/x ∈ Sk} for all k = 0... n since Z = min {cx/x ∈ S} = min{Zk} k = 0... n. Hence, we can efficiently solve problem P by efficiently solving problem P k. Actually, on average, one would solve a small number of problem P k by using the following stopping criterion: Zk ≤ l where l ≤ min{lj} for j ∈ M for some subset M ⊂ {1,... n} and where lj is a lower bound to problem P j. Then, we notice that, were not for constraint Ax ≥ b, the optimal solution to problem P k would have simply been the point z/zi = 1 for all i ≤ k and zi = 0 otherwise. What we, hence, would like to do is to build a sequence of point, (xi) ⊆ Bn such that ∑nl=1 xl = k, ∑nl=1 clxil ≤ ∑nl=1 clxjl if i < j. Given this sequence, the optimal solution to problem P k is xj where j = min{i/xi ∈ Sk}. The problem becomes now how to built efficiently such a sequence. We will present next a very efficient algorithm that accomplish this. Nevertheless, this approach is too slow if a feasible solution is found down the sequence so that, in the worst case al