Limit Crossing

Combinatorial problems are ubiquitous in thesciences, engineering, and industry. These problemstend to be difficult to solve optimally as theytypically have an exponential number of feasiblesolutions. Bounds have been used to prune away largenumbers of feasible solutions, thus allowing thecomputation to optimality for some problems. LimitCrossing reflects on the history of the use of boundsand observes that the major focus has been on boundsderived from relaxations of constraints. Neglectedopportunities to exploit bounds are subsequentlyidentified, explored, and tabulated. Furthermore, amethodology for the use of these bounds is formulatedas a two-step procedure. This procedure is referredto as "limit crossing." Direct instantiations of thelimit-crossing method have produced twounconventional search strategies: Cut-and-Solve andBBF. These strategies are presented and their poweris demonstrated for solving difficult, real-worldproblems. Limit Crossing contains rich resources forkick-starting novel algorithm discoveries byinnovative computer scientists, mathematicians, andoperations researchers who are tackling defiantcombinatorial problems.