×

Efficient intelligent backtracking using linear programming. (English) Zbl 1238.90144

Summary: Intelligent backtracking is a technique used in constraint programming for reducing search in solving combinatorial feasibility problems. The technique uses information derived from small sets of infeasible constraints discovered in one part of the search space to avoid searching other, similar, regions. It is often able to reduce the size of the search space significantly. For many problems, however, the computational effort required to achieve this reduction in search space is prohibitive. We introduce an algorithm that uses intelligent backtracking inside a linear-programming based branch-and-bound framework. We show that minimal infeasible sets can immediately be deduced from the dual extreme ray associated with the infeasible linear program. This allows us to obtain the reduction in search space associated with intelligent backtracking, without paying the large computational cost. We show the implementation of our intelligent backtracking approach as a branch-and-cut algorithm, and present computational results.

MSC:

90C90 Applications of mathematical programming
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
68W40 Analysis of algorithms

Software:

MINTO; MIPLIB
PDFBibTeX XMLCite
Full Text: DOI