zbMATH — the first resource for mathematics

A first look at picking dual variables for maximizing reduced cost fixing. (English) Zbl 06756588
Salvagnin, Domenico (ed.) et al., Integration of AI and OR techniques in constraint programming. 14th international conference, CPAIOR 2017, Padua, Italy, June 5–8, 2017. Proceedings. Cham: Springer (ISBN 978-3-319-59775-1/pbk; 978-3-319-59776-8/ebook). Lecture Notes in Computer Science 10335, 221-228 (2017).
Summary: Reduced-cost-based filtering in constraint programming and variable fixing in integer programming are techniques which allow to cut out part of the solution space which cannot lead to an optimal solution. These techniques are, however, dependent on the dual values available at the moment of pruning. In this paper, we investigate the value of picking a set of dual values which maximizes the amount of filtering (or fixing) that is possible. We test this new variable-fixing methodology for arbitrary mixed-integer linear programming models. The resulting method can be naturally incorporated into existing solvers. Preliminary results on a large set of benchmark instances suggest that the method can effectively reduce solution times on hard instances with respect to a state-of-the-art commercial solver.
For the entire collection see [Zbl 1364.68017].

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization
Full Text: DOI
[1] MIPLIB2010. http://miplib.zib.de/miplib2010-benchmark.php
[2] Balas, E., Martin, C.H.: Pivot and complement-a heuristic for 0–1 programming. Manage. Sci. 26(1), 86–96 (1980) · Zbl 0442.90060 · doi:10.1287/mnsc.26.1.86
[3] Bergman, D., Cire, A.A., Hoeve, W.-J.: Improved constraint propagation via lagrangian decomposition. In: Pesant, G. (ed.) CP 2015. LNCS, vol. 9255, pp. 30–38. Springer, Cham (2015). doi: 10.1007/978-3-319-23219-5_3 · Zbl 06483396 · doi:10.1007/978-3-319-23219-5_3
[4] Bixby, E.R., Fenelon, M., Gu, Z., Rothberg, E., Wunderling, R.: MIP: theory and practice – closing the gap. In: Powell, M.J.D., Scholtes, S. (eds.) CSMO 1999. ITIFIP, vol. 46, pp. 19–49. Springer, Boston, MA (2000). doi: 10.1007/978-0-387-35514-6_2 · Zbl 0986.90025 · doi:10.1007/978-0-387-35514-6_2
[5] Chvátal, V.: Linear Programming. Freeman, New York (1983). Reprints: (1999), (2000), (2002) · Zbl 0537.90067
[6] Fahle, T., Sellmann, M.: Cost-based filtering for the constrained knapsack problem. Ann. Oper. Res. 115, 73–93 (2002) · Zbl 1013.90105 · doi:10.1023/A:1021193019522
[7] Focacci, F., Lodi, A., Milano, M.: Cost-based domain filtering. In: Jaffar, J. (ed.) CP 1999. LNCS, vol. 1713, pp. 189–203. Springer, Heidelberg (1999). doi: 10.1007/978-3-540-48085-3_14 · doi:10.1007/978-3-540-48085-3_14
[8] Focacci, F., Lodi, A., Milano, M., Vigo, D.: Solving TSP through the integration of OR and CP techniques. Electron. Notes Discrete Math. 1, 13–25 (1999) · Zbl 0990.90553 · doi:10.1016/S1571-0653(04)00002-2
[9] Focacci, F., Milano, M., Lodi, A.: Solving TSP with time windows with constraints. In: Proceedings of the 1999 International Conference on Logic programming, Massachusetts Institute of Technology, pp. 515–529 (1999)
[10] Klabjan, D.: A new subadditive approach to integer programming. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol. 2337, pp. 384–400. Springer, Heidelberg (2002). doi: 10.1007/3-540-47867-1_27 · Zbl 1049.90045 · doi:10.1007/3-540-47867-1_27
[11] Lodi, A.: Mixed integer programming computation. In: Jünger, M., Liebling, T.M., Naddef, D., Nemhauser, G.L., Pulleyblank, W.R., Reinelt, G., Rinaldi, G., Wolsey, L.A. (eds.) 50 Years of Integer Programming 1958–2008, pp. 619–645. Springer, Heidelberg (2010) · Zbl 1187.90206 · doi:10.1007/978-3-540-68279-0_16
[12] Mahajan, A.: Presolving mixed-integer linear programs. In: Wiley Encyclopedia of Operations Research and Management Science (2010)
[13] Nemhauser, G.L., Wolsey, L.A.: Integer Programming and Combinatorial Optimization (1988)
[14] Chichester, W., Nemhauser, G.L., Savelsbergh, M.W.P., Sigismondi, G.S.: Constraint Classification for Mixed Integer Programming Formulations. COAL Bulletin, vol. 20, pp. 8–12 (1992)
[15] Refalo, P.: Linear formulation of constraint programming models and hybrid solvers. In: Dechter, R. (ed.) CP 2000. LNCS, vol. 1894, pp. 369–383. Springer, Heidelberg (2000). doi: 10.1007/3-540-45349-0_27 · Zbl 1044.68792 · doi:10.1007/3-540-45349-0_27
[16] Sellmann, M.: Theoretical foundations of CP-based lagrangian relaxation. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, pp. 634–647. Springer, Heidelberg (2004). doi: 10.1007/978-3-540-30201-8_46 · Zbl 1152.68584 · doi:10.1007/978-3-540-30201-8_46
[17] Thorsteinsson, E.S., Ottosson, G.: Linear relaxations and reduced-cost based propagation of continuous variable subscripts. Ann. Oper. Res. 115(1), 15–29 (2002) · Zbl 1011.90030 · doi:10.1023/A:1021136801775
[18] Wolsey, L.A.: Integer Programming, vol. 4. Wiley, New York (1998) · Zbl 0930.90072
[19] Yunes, T., Aron, I.D., Hooker, J.N.: An integrated solver for optimization problems. Oper. Res. 58(2), 342–356 (2010) · Zbl 1226.90047 · doi:10.1287/opre.1090.0733
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.