×

Using dual presolving reductions to reformulate cumulative constraints. (English) Zbl 1309.90066

Summary: Dual presolving reductions are a class of reformulation techniques that remove feasible or even optimal solutions while guaranteeing that at least one optimal solution remains, as long as the original problem was feasible. Presolving and dual reductions are important components of state-of-the-art mixed-integer linear programming solvers. In this paper, we introduce them both as unified, practical concepts in constraint programming solvers. Building on the existing idea of variable locks, we formally define and justify the use of dual information for cumulative constraints during a presolving phase of a solver. In particular, variable locks are used to decompose cumulative constraints, detect irrelevant variables, and infer variable assignments and domain reductions. Since the computational complexity of propagation algorithms typically depends on the number of variables and/or domain size, such dual reductions are a source of potential computational speed-up. Through experimental evidence on resource constrained project scheduling problems, we demonstrate that the conditions for dual reductions are present in well-known benchmark instances and that a substantial proportion of them can be solved to optimality in presolving – without search. While we consider this result very promising, we do not observe significant change in overall run-time from the use of our novel dual reductions

MSC:

90C11 Mixed integer programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Achterberg, T. (2007). Constraint integer programming. PhD thesis, Technische Universität Berlin. · Zbl 1169.90414
[2] Achterberg, T. (2009). SCIP: Solving constraint integer programs. Mathematical Programming Computation, 1(1), 1–41. · Zbl 1171.90476
[3] Aggoun, A., Beldiceanu, N. (1993). Extending chip in order to solve complex scheduling and placement problems. Mathematical and Computer Modelling, 17(7), 57–73. · Zbl 00269355
[4] Artigues, C., Demassey, S., Néron, E., (eds.) (2008). Resource-constrained project scheduling: Models, algorithms, extensions and applications. iSTE
[5] Baptiste, P., & Pape, C.L. (2000). Constraint propagation and decomposition techniques for highly disjunctive and highly cumulative project scheduling problems. Constraints, 5(1–2), 119–139. · Zbl 0941.90030
[6] Baptiste, P., Pape, C.L., Nuijten, W. (2001). Constraint-based scheduling. Kluwer Academic Publishers. · Zbl 1094.90002
[7] Baptiste, P., & Pape, C.L. (2005). Scheduling a single machine to minimize a regular objective function under setup constraints. Discrete Optimization, 2(1), 83–99. · Zbl 1140.90390
[8] Berthold, T., Heinz, S., Lübbecke, M.E., Möhring, R.H., Schulz, J. (2010). A constraint integer programming approach for resource-constrained project scheduling. In Lodi, A., Milano, M., Toth, P., (eds.) Integration of AI and OR techniques in constraint programming for combinatorial optimization problems (vol. 6140, pp. 313–317) of LNCS. Springer. · Zbl 1285.90045
[9] Berthold, T., Heinz, S., Schulz, J. (2011). An approximative criterion for the potential of energetic reasoning. In Marchetti-Spaccamela, A., Segal, M., (eds.) Theory and Practice of Algorithms in (Computer) systems (vol. 6595, pp. 229–239) of LNCS. Springer. · Zbl 1325.90035
[10] Bixby, R.E., & Wagner, D.K. (1987). A note on detecting simple redundancies in linear systems. Operation Research Letters, 6(1), 15–17. · Zbl 0624.90061
[11] Bordeaux, L., Cadoli, M., Mancini, T. (2008). A unifying framework for structural properties of CSPs: definitions, complexity, tractabilit. Journal of Artificial Intelligence Research, 32(1), 607–629. · Zbl 1182.68222
[12] Borrett, J.E., & Tsang, E.P.K. (2001). A context for constraint satisfaction problem formulation selection. Constraints, 6(4), 299–327. · Zbl 0983.68183
[13] Chu, G., & Stuckey, P.J. (2012). A generic method for identifying and exploiting dominance relations. In Milano, M., (ed.) Principles and practice of constraint programming - CP 2012 (vol. 7514, pp. 6–22) of LNCS.
[14] Dantzig, G.B., & Thapa, M.N. (2003). Linear programming 2. Springer Series in Operations Research. Springer. · Zbl 1029.90037
[15] de la Banda, M.J.G., Marriott, K., Rafeh, R., Wallace, M. (2006). The modelling language Zinc. In Benhamou, F., (ed.) Principles and practice of constraint programming - CP 2006 (vol. 4204, pp. 700–705). LNCS.
[16] Dechter, R. (2003). Constraint processing. Elsevier Morgan Kaufmann. · Zbl 1057.68114
[17] Frisch, A.M., Harvey, W., Jefferson, C., Martínez-Hernández, B., Miguel, I. (2008). ESSENCE: A constraint language for specifying combinatorial problems. Constraints, 13, 268–306. · Zbl 1147.68424
[18] Gent, I.P., Petrie, K.E., Puget, J.F. (2006). Symmetry in constraint programming. In Handbooks of constraint programming. Elsevier.
[19] Gent, I.P., Miguel, I., Rendl, A. (2007). Tailoring solver-independent constraint models: a case study with ESSENCE and MINION. In Miguel, I., Ruml, W., (eds.) Abstraction, Reformulation, and Approximation (vol. 4612, pp. 184–199) of LNCS.
[20] Guzelsoy, M. (2010). Dual methods in mixed integer linear programming. PhD thesis, Lehigh University,Industrial and Systems Engineering.
[21] Heinz, S., & Schulz, J. (2011). Explanations for the cumulative constraint: An experimental study. In Pardalos, P.M., Rebennack, S. (eds.) Experimental algorithms (vol. 6630, pp. 400–409) of LNCS. Springer.
[22] Imbert, J.L., & Hentenryck, P.V. (1996). Redundancy elimination with a lexicographic solved form. Annals of Mathematics and Artificial Intelligence, 17(1–2), 85–106. · Zbl 0887.90115
[23] Karwan, M.H., Lotfi, V., Telgen, J., Zionts, S. (1983). Redundancy in mathematical programming. A state-of-the-art survey. Volume 206 of Lecture Notes in Economics and Mathematical Systems. Springer. · Zbl 0524.90058
[24] Kiziltan, Z. (2004). Symmetry breaking ordering constraints: Thesis. AI Communications, 17, 167–169.
[25] Klein, R., & Scholl, A. (1999). Computing lower bounds by destructive improvement: An application to resource-constrained project scheduling. European Journal of Operational Research, 112(2), 322–346. · Zbl 0938.90030
[26] Koch, T., Achterberg, T., Andersen, E., Bastert, O., Berthold, T., Bixby, R.E., Danna, E., Gamrath, G., Gleixner, A.M., Heinz, S., Lodi, A., Mittelmann, H., Ralphs, T., Salvagnin, D., Steffy, D.E., Wolter, K. (2011). MIPLIB 2010. Mathematical Programming Computation, 3(2), 103–163. · Zbl 06110465
[27] Laurière, J.L. (1978). A language and a program for stating and solving combinatorial problems. Artificial Intelligence, 10(1), 29–127. · Zbl 0374.68060
[28] Mahajan, A. (2010). Presolving mixed-integer linear programs. Preprint ANL/MCS-P1752-0510, Mathematics and Computer Science Division.
[29] Marriott, K., Nethercote, N., Rafeh, R., Stuckey, P.J., de la Banda, M.G., Wallace, M. (2008). The design of the zinc modelling language. Constraints, 13(3), 229–267. · Zbl 1146.68352
[30] Möhring, R.H., Schulz, A.S., Stork, F., Uetz, M. (2003). Solving project scheduling problems by minimum cut computations. Management Science, 49(3), 330–350. · Zbl 1232.90213
[31] Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., Tack, G. (2007). MiniZinc: Towards a standard CP modelling language. In Bessiere, C., (ed.) Principles and Practice of Constraint Programming - CP 2007 (vol. 4741, pp. 529–543) of LNCS. Springer.
[32] Pesant, G., Quimper, C., Zanarini, A. (2012). Counting-based search: Branching heuristics for constraint satisfaction problems. Journal of Artificial Intelligence Research, 43, 173–210. · Zbl 1237.68193
[33] Prestwich, S.D., & Beck, J.C. (2004). Exploiting dominance in three symmetric problems. In Proceedings of the fourth international workshop on symmetry and constraint satisfaction problems.
[34] PSPLib: Project scheduling problem library. http://129.187.106.231/psplib/ .
[35] Puget, J.F. (2005). Automatic detection of variable and value symmetries. In van Beek, P. (ed.) Principles and practice of constraint programming - CP 2005 (vol. 3709, pp. 475–489) of LNCS. · Zbl 1153.68477
[36] Rendl, A. (2010). Effective compilation of constraint models. PhD thesis, University of St Andrews.
[37] Savelsbergh, M.W.P. (1994). Preprocessing and probing techniques for mixed integer programming problems. ORSA Journal on Computing, 6, 445–454. · Zbl 0814.90093
[38] Schutt, A., Feydy, T., Stuckey, P.J., Wallace, M.G. (2012). Solving rcpsp/max by lazy clause generation. Journal of Scheduling. (accepted). · Zbl 1280.90067
[39] van Hoeve, W.J. (2001). The all different constraint: A survey. CoRR cs.PL/0105015.
[40] Vilím, P. (2009). Max energy filtering algorithm for discrete cumulative resources. In van Hoeve, W.J., Hooker, J.N. (eds.) Integration of AI and OR techniques in constraint programming for combinatorial optimization problems (vol. 5547, pp. 294–308) of LNCS. · Zbl 1241.90125
[41] Yunes, T., Aron, I.D., Hooker, J.N. (2010). An integrated solver for optimization problems. Operations Research, 58(2), 342–356. · Zbl 1226.90047
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.