×

Dominance rules in combinatorial optimization problems. (English) Zbl 1237.90199

Summary: The aim of this paper is to study the concept of a “dominance rule” in the context of combinatorial optimization. A dominance rule is established in order to reduce the solution space of a problem by adding new constraints to it, either in a procedure that aims to reduce the domains of variables, or directly in building interesting solutions. Dominance rules have been extensively used over the last 50 years. Surprisingly, to our knowledge, no detailed description of them can be found in the literature other than a few short formal descriptions in the context of enumerative methods. We are therefore proposing an investigation into what dominance rules are. We first provide a definition of a dominance rule with its different nuances. Next, we analyze how dominance rules are generally formulated and what are the consequences of such formulations. Finally, we enumerate the common characteristics of dominance rules encountered in the literature and in the usual process of solving combinatorial optimization problems.

MSC:

90C27 Combinatorial optimization
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Manne, A., Programming of economic lot sizes, Management Science, 4, 2, 115-135 (1958)
[2] Levitan, R., A note on professor manne’s “dominance” theorem, Management Science, 5, 3, 332-334 (1959)
[3] Ignall, E.; Schrage, L., Applications of the branch-and-bound technique to some flow-shop scheduling problems, Operations Research, 13, 400-412 (1965)
[4] Fox, B., Discrete optimization via marginal analysis, Management Science, 13, 3, 210-216 (1966) · Zbl 0173.47503
[5] Proshan, F.; Bray, T., Optimum redundancy under multiple constraints, Operations Research, 13, 800-814 (1965)
[6] Weingartner, H.; Ness, D., Methods for the solution of the multidimensional 0/1 knapsack problem, Operations Research, 15, 1, 83-103 (1967)
[7] Elmaghraby, S., The one machine sequencing problem with delay costs, Journal of Industrial Engineering, 19, 105-108 (1968)
[8] Baker, K., Introduction to Sequencing and Scheduling (1974), John Wiley and Sons
[9] Kohler, W.; Steiglitz, K., Characterization and theoretical comparison of branch-and-bound algorithms for permutation problems, Journal of the ACM, 21, 1, 140-156 (1974) · Zbl 0279.68035
[10] Ibaraki, T., The power of dominance relations in branch-and-bound algorithm, Journal of the Association for Computing Machinery, 24, 2, 264-279 (1977) · Zbl 0357.90043
[11] Johnson, S., Optimal two- and three-stage production schedules with setup times included, Naval Research Logistic Quarterly, 1, 1, 61-68 (1954) · Zbl 1349.90359
[12] Smith, W., Various optimizers for single stage production, Naval Research Logistics Quarterly, 3, 59-66 (1956)
[13] Gomory, R., Outline of an algorithm for integer solutions to linear programs, Bulletin of the American Mathematical Society, 64, 275-278 (1958) · Zbl 0085.35807
[14] J. Swift, Isomorph rejection in exhaustive search techniques, in: American Mathematical Society Symposia in Applied Mathematics, vol. 10, 1960, pp. 195-200.; J. Swift, Isomorph rejection in exhaustive search techniques, in: American Mathematical Society Symposia in Applied Mathematics, vol. 10, 1960, pp. 195-200. · Zbl 0096.00505
[15] Giffler, B.; Thompson, G., Algorithms for solving production scheduling problems, Operations Research, 8, 487-503 (1960) · Zbl 0248.90022
[16] Baker, K.; Trietsch, D., Principles of Sequencing and Scheduling (2009), John Wiley and Sons · Zbl 1169.90009
[17] Garey, M.; Johnson, D., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman · Zbl 0411.68039
[18] Brucker, P., Scheduling Algorithms (1995), Springer: Springer Lehrbuch · Zbl 0839.90059
[19] Nemhauser, G.; Wolsey, L., Integer and Combinatorial Optimization (1998), Wiley: Wiley New York
[20] Golomb, S.; Baumert, D., Backtrack programming, Journal of the Association for Computing Machinery, 12, 516-524 (1965) · Zbl 0139.12305
[21] Agin, N., Optimum seeking with branch and bound, Management Science, 13, 4, 176-185 (1966)
[22] (Rossi, F.; Van Beek, P.; Walsh, T., Handbook of Constraint Programming (Foundations of Artificial Intelligence) (2006), Elsevier Science Inc.) · Zbl 1175.90011
[23] Baptiste, P.; Le Pape, C.; Nuijten, W., Constraint-based scheduling, applying constraint programming to scheduling problems, International Series in Operations Research and Management Science, vol. 39 (2001), Kluwer · Zbl 1094.90002
[24] Carlier, J.; Chrétienne, P., Problèmes d’ordonnancement: modélisation/complexitè/algorithmes (1988), Masson
[25] Kohler, W.; Steiglitz, K., Computer and job-shop scheduling theory, (Coffman, E. G., Ch. Enumerative and iterative computational approaches (1976), John Wiley & Sons), 229-287
[26] Emmons, H., One-machine sequencing to minimize certain functions of job tardiness, Operations Research, 17, 701-715 (1969) · Zbl 0176.50005
[27] Dessouky, M.; Deogun, D., Sequencing jobs with unequal ready times to minimize mean flow time, SIAM Journal on Computing, 10, 192-202 (1981) · Zbl 0454.68010
[28] C. Brown, L. Finkelstein, P. Purdom, Applied algebra, algebraic algorithms and error-correcting codes, Ch. Backtrack searching in the presence of symmetry, 1988.; C. Brown, L. Finkelstein, P. Purdom, Applied algebra, algebraic algorithms and error-correcting codes, Ch. Backtrack searching in the presence of symmetry, 1988.
[29] Glaisher, J., On the problem of the eight queens, Philosophical Magazine Series, 4, 48, 457-467 (1874) · JFM 08.0120.01
[30] E. Freuder, Eliminating interchangeable values in constraint satisfaction problems, in: Proceedings of AAAI-91: the Ninth National Conference on Artificial Intelligence, Anaheim, California, 1991.; E. Freuder, Eliminating interchangeable values in constraint satisfaction problems, in: Proceedings of AAAI-91: the Ninth National Conference on Artificial Intelligence, Anaheim, California, 1991.
[31] J. Puget, On the satisfiability of symmetrical constrained satisfaction problems, in: Proceedings of ISMIS’93, LNAI 689, 1993, pp. 350-361.; J. Puget, On the satisfiability of symmetrical constrained satisfaction problems, in: Proceedings of ISMIS’93, LNAI 689, 1993, pp. 350-361.
[32] B. Benhamou, Study of symmetry in constraint satisfaction problems, in: Proceedings of PPCP’94: the Second Workshop on Principles and Practice of Constraint Programming, 1994, pp. 281-294.; B. Benhamou, Study of symmetry in constraint satisfaction problems, in: Proceedings of PPCP’94: the Second Workshop on Principles and Practice of Constraint Programming, 1994, pp. 281-294.
[33] B. Smith, Reducing symmetry in a combinatorial design problem, in: Proceedings of CP-AI-OR’01, the Third International Workshop on Integration of AI and OR techniques in CP, 2001.; B. Smith, Reducing symmetry in a combinatorial design problem, in: Proceedings of CP-AI-OR’01, the Third International Workshop on Integration of AI and OR techniques in CP, 2001.
[34] T. Fahle, S. Schamberger, M. Sellmann, Symmetry in constraint optimization, in: Proceedings of CP’2001: the Seventh International Conference on Principles and Practice of Constraint Programming, 2001, pp. 93-107.; T. Fahle, S. Schamberger, M. Sellmann, Symmetry in constraint optimization, in: Proceedings of CP’2001: the Seventh International Conference on Principles and Practice of Constraint Programming, 2001, pp. 93-107. · Zbl 1067.68631
[35] S. Prestwich, C. Beck, Exploiting dominance in three symmetric problems, in: SymCon’04: the Fourth International Workshop on Symmetry in Constraint Satisfaction Problems, a Satellite Workshop of CP2004: the 10th International Conference on Principles and Practice of Constraint Programming, 2004, pp. 63-70.; S. Prestwich, C. Beck, Exploiting dominance in three symmetric problems, in: SymCon’04: the Fourth International Workshop on Symmetry in Constraint Satisfaction Problems, a Satellite Workshop of CP2004: the 10th International Conference on Principles and Practice of Constraint Programming, 2004, pp. 63-70.
[36] D. Cohen, P. Jeavons, C. Jefferson, K. Petrie, B. Smith, Symmetry definitions for constraint satisfaction problems, in: Proceedings of CP2005, the 11th International Conference on Principles and Practice of Constraint Programming, 2005, pp. 17-31.; D. Cohen, P. Jeavons, C. Jefferson, K. Petrie, B. Smith, Symmetry definitions for constraint satisfaction problems, in: Proceedings of CP2005, the 11th International Conference on Principles and Practice of Constraint Programming, 2005, pp. 17-31. · Zbl 1153.68454
[37] T. Walsh, General symmetry breaking constraints, in: Proceedings of CP-2006: the 12th International Conference on Principles and Practice of Constraint Programming, Lecture Notes in Computer Science, 2006.; T. Walsh, General symmetry breaking constraints, in: Proceedings of CP-2006: the 12th International Conference on Principles and Practice of Constraint Programming, Lecture Notes in Computer Science, 2006. · Zbl 1160.68571
[38] Carlier, J.; Pinson, E., Adjustments of heads and tails for the job-shop problem, European Journal of Operational Research, 78, 146-161 (1994) · Zbl 0812.90063
[39] L. Peridy, Le problème de job-shop: arbitrages et ajustements, Ph.D. thesis, Université de Technologie de Compiégne, France, 1996.; L. Peridy, Le problème de job-shop: arbitrages et ajustements, Ph.D. thesis, Université de Technologie de Compiégne, France, 1996.
[40] L. Peridy, Régles d’Éliminations pour les problèmes d’ordonnancement disjonctif, Habilitation á diriger des recherches, Université de Technologie de Compiègne, France, 2007.; L. Peridy, Régles d’Éliminations pour les problèmes d’ordonnancement disjonctif, Habilitation á diriger des recherches, Université de Technologie de Compiègne, France, 2007.
[41] Belouadah, H.; Posner, M.; Potts, C., Scheduling with release dates on a single machine to minimize total weighted completion time, Discrete Applied Mathematics, 36, 213-231 (1992) · Zbl 0757.90032
[42] Glover, F.; Kochenberger, G., Handbook of Metaheuristics, International Series in Operations Research and Management Science, vol. 57 (2003), Springer · Zbl 1058.90002
[43] Chu, C.; Portmann, M.-C., Some new efficients methods to solve the \(n | 1 | r_i | \sum T_i\), European Journal of Operational Research, 58, 404-413 (1991) · Zbl 0760.90055
[44] Chu, C., Efficient heuristics to minimize total flow time with release dates, Operations Research Letters, 12, 321-330 (1992) · Zbl 0769.90047
[45] Jouglet, A.; Savourey, D.; Carlier, J.; Baptiste, P., Dominance-based heuristics for one-machine total cost scheduling problems, European Journal of Operational Research, 184, 3, 879-899 (2008) · Zbl 1141.90019
[46] Dantzig, G., Linear Programming and Extensions (1963), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0108.33103
[47] Held, M.; Karp, R., A dynamic programming approach to sequencing problems, SIAM Journal on Applied Mathematics, 10, 1, 196-210 (1962) · Zbl 0106.14103
[48] Lawler, E.; Moore, J., A functional equation and its application to resource allocation and sequencing problems, Management Science, 16, 77-84 (1969) · Zbl 0184.23303
[49] Bellman, R., The theory of dynamic programming, Bulletin of the American Mathematical Society, 60, 503-515 (1954) · Zbl 0057.12503
[50] R. Walker, An enumerative technique for a class of combinatorial problems, in: American Mathematical Society Symposia in Applied Mathematics, vol. 10, 1960, pp. 91-94.; R. Walker, An enumerative technique for a class of combinatorial problems, in: American Mathematical Society Symposia in Applied Mathematics, vol. 10, 1960, pp. 91-94.
[51] Balas, E., Discrete programming by the filter method, Operations Research, 15, 915-957 (1967) · Zbl 0153.21401
[52] Mitten, L., Branch-and-bound methods: general formulation and properties, Operations Research, 18, 1, 24-34 (1970) · Zbl 0225.90030
[53] Land, A.; Doig, A., An automatic method for solving discrete programming problems, Econometrica, 28, 497-520 (1960) · Zbl 0101.37004
[54] Little, J.; Murty, K.; Sweeney, D.; Karel, C., An algorithm for the traveling salesman problem, Operations Research, 11, 972-989 (1963) · Zbl 0161.39305
[55] Bertier, P.; Roy, B., Procédure de résolution pour une classe de problèmes pouvant avoir un caractère combinatoire, Cahiers du Centre d’Études de Recherche Opérationnelle, 6, 202-208 (1964) · Zbl 0204.18903
[56] Lawler, E.; Wood, D., Branch-and-bound methods: a survey, Operations Research, 14, 4, 699-719 (1966) · Zbl 0143.42501
[57] Balas, E., A note on the branch-and-bound principle, Operations Research, 16, 442-445 (1968) · Zbl 0186.24901
[58] Roy, B., Procédure d’exploration par séparation et évaluation, Revue Française d’Informatique et de Recherche Opérationelle, 6, 61-90 (1969) · Zbl 0218.90032
[59] T. Walsh, Symmetry in constraint optimization, in: Proceedings of SymCon’07, the Seventh International Workshop on Symmetry and Constraint Satisfaction Problems, 2007.; T. Walsh, Symmetry in constraint optimization, in: Proceedings of SymCon’07, the Seventh International Workshop on Symmetry and Constraint Satisfaction Problems, 2007.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.