Limit Crossing - Guide for Solving Combinatorial Problems by Exploiting Bounds

Combinatorial problems are ubiquitous in the sciences, engineering, and industry. These problems tend to be difficult to solve optimally as they typically have an exponential number of feasible solutions. Bounds have been used to prune away large numbers of feasible solutions, thus allowing the computation to optimality for some problems. Limit Crossing reflects on the history of the use of bounds and observes that the major focus has been on bounds derived from relaxations of...
More Description

Combinatorial problems are ubiquitous in the sciences, engineering, and industry. These problems tend to be difficult to solve optimally as they typically have an exponential number of feasible solutions. Bounds have been used to prune away large numbers of feasible solutions, thus allowing the computation to optimality for some problems. Limit Crossing reflects on the history of the use of bounds and observes that the major focus has been on bounds derived from relaxations of constraints. Neglected opportunities to exploit bounds are subsequently identified, explored, and tabulated. Furthermore, a methodology for the use of these bounds is formulated as a two-step procedure. This procedure is referred to as "limit crossing." Direct instantiations of the limit-crossing method have produced two unconventional search strategies: Cut-and-Solve and BBF. These strategies are presented and their power is demonstrated for solving difficult, real-world problems. Limit Crossing contains rich resources for kick-starting novel algorithm discoveries by innovative computer scientists, mathematicians, and operations researchers who are tackling defiant combinatorial problems.