×

On the consistent path problem. (English) Zbl 1457.90126

Summary: The application of decision diagrams in combinatorial optimization has proliferated in the last decade. In recent years, authors have begun to investigate how to use not one, but a set of diagrams, to model constraints and objective function terms. Optimizing over a collection of decision diagrams, the problem we refer to as the consistent path problem (CPP) can be addressed by associating a network-flow model with each decision diagram, jointly linked through channeling constraints. A direct application of integer programming to the ensuing model has already been shown to result in algorithms that provide orders-of-magnitude performance gains over classical methods. Lacking, however, is a careful study of dedicated solution methods designed to solve the CPP. This paper provides a detailed study of the CPP, including a discussion on complexity results and a complete polyhedral analysis. We propose a cut-generation algorithm, which, under a structured ordering property, finds a cut, if one exists, through an application of the classical maximum flow problem, albeit in an exponentially sized network. We use this procedure to fuel a cutting-plane algorithm that is applied to unconstrained binary cubic optimization and a variant of the market split problem, resulting in an algorithm that compares favorably with CPLEX, using standard integer programming formulations for both problems.

MSC:

90C27 Combinatorial optimization
90C35 Programming involving graphs or networks

Software:

BARON; MIPLIB; CPLEX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aardal K, Hurkens CA, Lenstra AK (2000a) Solving a system of linear diophantine equations with lower and upper bounds on the variables. Math. Oper. Res. 25(3):427-442.Link, Google Scholar · Zbl 1073.90528
[2] Aardal K, Bixby RE, Hurkens CA, Lenstra AK, Smeltink JW (1999) Market split and basis reduction: Toward a solution of the Cornuéjols-Dawande instances. Cornuéjols G, Burkard RE, Woeginger GJ, eds. Internat. Conf. Integer Programming Combinatorial Optim. (Springer, New York), 1-16.Google Scholar · Zbl 0948.90108
[3] Aardal K, Bixby RE, Hurkens CA, Lenstra AK, Smeltink JW (2000b) Market split and basis reduction: Toward a solution of the Cornuéjols-Dawande instances. INFORMS J. Comput. 12(3):192-202.Link, Google Scholar · Zbl 1040.90023
[4] Becker B, Behle M, Eisenbrand F, Wimmer R (2005) BDDs in a branch and cut framework. Nikoletseas S, ed. Proc. 4th Internat. Workshop Experiment. Efficient Algorithms (WEA 05), Lecture Notes in Computer Science, vol. 3503 (Springer, Berlin, Heidelberg), 452-463.Google Scholar · Zbl 1121.90422
[5] Bergman D, Ciré AA (2016) Decomposition based on decision diagrams. Quimper CG, ed. Integration of AI and OR Techniques in Constraint Programming: 13th Internat. Conf., CPAIOR, Lecture Notes in Computer Science, vol. 9676 (Springer International Publishing, New York), 45-54.Google Scholar · Zbl 1475.68336
[6] Bergman D, Ciré AA (2018) Discrete nonlinear optimization by state-space decompositions. Management Sci. 46(10):4700-4720.Link, Google Scholar
[7] Bergman D, Ciré AA, van Hoeve WJ (2014) MDD propagation for sequence constraints. J. Artificial Intelligence Res. 50(1):697-722.Google Scholar · Zbl 1366.68072
[8] Bergman D, van Hoeve WJ, Hooker JN (2011) Manipulating MDD relaxations for combinatorial optimization. Achterberg T, Beck JC, eds. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems: 8th Internat. Conf., CPAIOR, Lecture Notes in Computer Science, vol. 6697 (Springer, New York), 20-35.Google Scholar · Zbl 1302.90166
[9] Bergman D, Ciré AA, van Hoeve W, Hooker JN (2016a) Decision Diagrams for Optimization. Artificial Intelligence: Foundations, Theory, and Algorithms (Springer, Cham, Switzerland).Crossref, Google Scholar · Zbl 06653190 · doi:10.1007/978-3-319-42849-9
[10] Bergman D, Ciré AA, van Hoeve WJ, Hooker JN (2016b) Discrete optimization with decision diagrams. INFORMS J. Comput. 28(1):47-66.Link, Google Scholar · Zbl 1338.90260
[11] Bixby RE, Ceria S, McZeal CM, Savelsbergh MW (1998) An updated mixed integer programming library: MIPLIB 3.0. Technical report, https://hdl.handle.net/1911/101898.Google Scholar
[12] Canfield RA (2004) Multipoint cubic surrogate function for sequential approximate optimization. Structural Multidisciplinary Optim. 27(5):326-336.Google Scholar
[13] Cornuéjols G, Dawande M (1999) A class of hard small 0-1 programs. INFORMS J. Comput. 11(2):205-210.Link, Google Scholar · Zbl 1040.90534
[14] Crama Y, Rodríguez-Heck E (2017) A class of valid inequalities for multilinear 0-1 optimization problems. Discrete Optim. 25:28-47.Crossref, Google Scholar · Zbl 1387.90125 · doi:10.1016/j.disopt.2017.02.001
[15] Del Pia A, Khajavirad A (2017) A polyhedral study of binary polynomial programs. Math. Oper. Res. 42(2):389-410.Link, Google Scholar · Zbl 1364.90225
[16] Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. (W. H. Freeman & Co., Princeton, NJ).Google Scholar · Zbl 0411.68039
[17] Hadz̆ić T, Hooker JN (2006) Postoptimality analysis for integer programming using binary decision diagrams. Technical report, Carnegie Mellon University, Pittsburgh.Google Scholar
[18] Hadz̆ić T, Hooker JN (2007) Cost-bounded binary decision diagrams for 0-1 programming. Loute E, Wolsey L, eds. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems: 4th Internat. Conf., CPAIOR, Lecture Notes in Computer Science, vol. 4510 (Springer, New York), 84-98.Google Scholar · Zbl 1214.90084
[19] Hadz̆ić T, Hooker JN, O’Sullivan B, Tiedemann P (2008) Approximate compilation of constraints into multivalued decision diagrams. Stuckey PJ, ed. Principles and Practice of Constraint Programming (CP 2008), Lecture Notes in Computer Science, vol. 5202 (Springer, Berlin, Heidelberg), 448-462.Crossref, Google Scholar · doi:10.1007/978-3-540-85958-1_30
[20] Hadz̆ić T, O’Mahony E, O’Sullivan B, Sellmann M (2009) Enhanced inference for the market split problem. 21st IEEE Internat. Conf. Tools Artificial Intelligence (IEEE Computer Society, Los Alamitos, CA), 716-723.Google Scholar
[21] Håstad J (2001) Some optimal inapproximability results. J. ACM 48(4):798-859.Crossref, Google Scholar · Zbl 1127.68405 · doi:10.1145/502090.502098
[22] Håstad J, Venkatesh S (2004) On the advantage over a random assignment. Random Structures Algorithms 25(2):117-149.Crossref, Google Scholar · Zbl 1078.68159 · doi:10.1002/rsa.20031
[23] He S, Li Z, Zhang S (2013) Approximation algorithms for discrete polynomial optimization. J. Oper. Res. Soc. China 1(1):3-36.Crossref, Google Scholar · Zbl 1281.90026 · doi:10.1007/s40305-013-0003-1
[24] Hoda S, van Hoeve WJ, Hooker JN (2010) Cohen D, ed. A systematic approach to MDD-based constraint programming. Principles and Practice of Constraint Programming - CP 2010. (Springer, Berlin, Heidelberg), 266-280.Google Scholar
[25] Hooker JN (2013) Decision diagrams and dynamic programming. Gomes C, Sellmann M, eds. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems: 10th Internat. Conf., CPAIOR, Lecture Notes in Computer Science, vol. 7874 (Springer, Berlin, Heidelberg), 94-110.Google Scholar · Zbl 1382.90113
[26] Khot S, Naor A (2007) Linear equations modulo 2 and the l1 diameter of convex bodies. 48th Annual IEEE Sympos. Foundations of Computer Science (FOCS’07) (IEEE, Washington, DC), 318-328.Google Scholar
[27] Kochenberger G, Hao JK, Glover F, Lewis M, Lü Z, Wang H, Wang Y (2014) The unconstrained binary quadratic programming problem: a survey. J. Combin. Optim. 28(1):58-81.Crossref, Google Scholar · Zbl 1303.90066 · doi:10.1007/s10878-014-9734-0
[28] Lenstra AK, Lenstra HW, Lovász L (1982) Factoring polynomials with rational coefficients. Math. Ann. 261(4):515-534.Crossref, Google Scholar · Zbl 0488.12001 · doi:10.1007/BF01457454
[29] Li Z, He S, Zhang S (2012) Approximation Methods for Polynomial Optimization: Models, Algorithms, and Applications (Springer Science & Business Media, Secaucus, NJ).Crossref, Google Scholar · Zbl 1298.90003 · doi:10.1007/978-1-4614-3984-4
[30] Lin C, Chang P, Luh J (1983) Formulation and optimization of cubic polynomial joint trajectories for industrial robots. IEEE Trans. Automat. Control 28(12):1066-1074.Crossref, Google Scholar · Zbl 0525.93035 · doi:10.1109/TAC.1983.1103181
[31] Nesterov Y (2008) Accelerating the cubic regularization of Newton’s method on convex problems. Math. Program. 112(1):159-181.Crossref, Google Scholar · Zbl 1167.90013 · doi:10.1007/s10107-006-0089-x
[32] Perez G, Régin JC (2015) Relations between MDDs and tuples and dynamic modifications of MDDs based constraints. Preprint, submitted May 11, https://arxiv.org/abs/1505.02552.Google Scholar
[33] Sahinidis NV (2016) BARON 15.6.5: Global Optimization of Mixed-Integer Nonlinear Programs: User’s Manual. https://minlp.com/downloads/docs/baron
[34] Wang Y, Liang Z (2010) Global optimality conditions for cubic minimization problem with box or binary constraints. J. Global Optim. 47(4):583-595.Crossref, Google Scholar · Zbl 1228.90088 · doi:10.1007/s10898-009-9480-5
[35] Wassermann A (2002) Attacking the market split problem with lattice point enumeration. J. Combin. Optim. 6(1):5-16.Crossref, · Zbl 1056.90106 · doi:10.1023/A:1013355015853
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.