×

zbMATH — the first resource for mathematics

Bounding, filtering and diversification in CP-based local branching. (English) Zbl 1358.90158
Summary: Local branching is a general purpose heuristic method which searches locally around the best known solution by employing tree search. It has been successfully used in Mixed-Integer Programming where local branching constraints are used to model the neighborhood of an incumbent solution and improve the bound. We propose the integration of local branching in Constraint Programming (CP). This integration is not simply a matter of implementation, but requires a number of significant extensions. The original contributions of this paper are: the definition of an efficient and incremental bound computation for the neighborhood, a cost-based filtering algorithm for the local branching constraint and a novel diversification strategy that can explore arbitrarily far regions of the search tree w.r.t. the already found solutions. We demonstrate the practical value of local branching in CP by providing an extensive experimental evaluation on the hard instances of the Asymmetric Traveling Salesman Problem with Time Windows.

MSC:
90C59 Approximation methods and heuristics in mathematical programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Software:
COMET; TSPTW
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ascheuer, N.: Hamiltonian path problems in the on-line optimization of flexible manufacturing systems. PhD thesis, Technische Universität Berlin (1995) · Zbl 0859.90080
[2] Baldacci, R., Mingozzi, A., Roberti, R.: New state space relaxations for solving the traveling salesman problem with time windows. Technical Report University of Bologna (2010) · Zbl 06599275
[3] Baptiste, P., Le Pape, C., Nuijten, W.: Constraint-based Scheduling. Kluwer Academic, Dordrecht (2001) · Zbl 1094.90002
[4] Solution-guided multi-point constructive search for job shop scheduling, J. Artif. Intell. Res., 29, 49-77, (2007) · Zbl 1182.68058
[5] Exploring relaxation induced neighborhoods to improve mip solutions, Math. Program., 102, 71-90, (2004) · Zbl 1131.90036
[6] Time constrained routing and scheduling, 35-139, (1995) · Zbl 0861.90052
[7] Local branching, Math. Program., 98, 23-47, (2003) · Zbl 1060.90056
[8] An additive bounding procedure for combinatorial optimization problems, Oper. Res., 37, 319-328, (1989) · Zbl 0676.90049
[9] Optimization-oriented global constraints, Constraints, 7, 351-365, (2002) · Zbl 1028.68024
[10] A hybrid exact algorithm for the TSPTW, INFORMS J. Comput., 14, 403-417, (2002) · Zbl 1238.90054
[11] Limited discrepancy search, 607-615, (1995), San Mateo
[12] Finding diverse and similar solutions in constraint programming, 372-377, (2005), Cambridge
[13] Automated configuration of mixed integer programming solvers, 186-202, (2010)
[14] CP-based local branching, No. 4741, 847-855, (2007), Berlin · Zbl 1145.68520
[15] An effective heuristic algorithm for the traveling-salesman problem, Oper. Res., 21, 498-516, (1973) · Zbl 0256.90038
[16] Discrepancy based additive bounding for the all different constraint, No. 2833, 510-524, (2003), Berlin
[17] Milano, M.: Constraint and Integer Programming: Toward a Unified Methodology. Kluwer Academic, Dordrecht (2003). Chap. 9. · Zbl 1054.90005
[18] Minimising conflicts: a heuristic repair method for constraint satisfaction and scheduling problems, Artif. Intell., 58, 161-205, (1992) · Zbl 0782.90054
[19] Variable neighbourhood search, Comput. Oper. Res., 24, 1097-1100, (1997) · Zbl 0889.90119
[20] A constraint programming framework for local search methods, J. Heuristics, 5, 255-279, (1999) · Zbl 1064.90577
[21] Cost-based arc consistency for global cardinality constraints, Constraints, 3-4, 7, 387-405, (2002) · Zbl 1028.68157
[22] An evolutionary algorithm for polishing mixed integer programming solutions, INFORMS J. Comput., 19, 534-541, (2007) · Zbl 1241.90092
[23] Heuristic constraint propagation—using local search for incomplete pruning and domain filtering of redundant constraints for the social golfer problem, 191-204, (2002)
[24] Constraint programming based Lagrangian relaxation for the automatic recording problem, Ann. Oper. Res., 118, 17-33, (2003) · Zbl 1026.90510
[25] Using constraint programming and local search methods to solve vehicle routing problems, No. 1520, 417-431, (1998), Berlin
[26] Constraint programming and local search hybrids, 271-304, (2011), Berlin · Zbl 1206.90182
[27] van Hentenryck, P., Michel, L.: Constraint-based Local Search. MIT Press, Cambridge (2005) · Zbl 1160.68556
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.