On the Consistent Path Problem

References

• 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
• 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
• 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
• 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
• 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
• Bergman D, Ciré AA (2018) Discrete nonlinear optimization by state-space decompositions. Management Sci. 46(10):4700–4720.Link, Google Scholar
• Bergman D, Ciré AA, van Hoeve WJ (2014) MDD propagation for sequence constraints. J. Artificial Intelligence Res. 50(1):697–722.Google Scholar
• 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
• 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
• 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
• 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
• Canfield RA (2004) Multipoint cubic surrogate function for sequential approximate optimization. Structural Multidisciplinary Optim. 27(5):326–336.Google Scholar
• Cornuéjols G, Dawande M (1999) A class of hard small 0-1 programs. INFORMS J. Comput. 11(2):205–210.Link, Google Scholar
• 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
• Del Pia A, Khajavirad A (2017) A polyhedral study of binary polynomial programs. Math. Oper. Res. 42(2):389–410.Link, Google Scholar
• Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. (W. H. Freeman & Co., Princeton, NJ).Google Scholar
• Hadz̆ić T, Hooker JN (2006) Postoptimality analysis for integer programming using binary decision diagrams. Technical report, Carnegie Mellon University, Pittsburgh.Google Scholar
• 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
• 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
• 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
• Håstad J (2001) Some optimal inapproximability results. J. ACM 48(4):798–859.Crossref, Google Scholar
• Håstad J, Venkatesh S (2004) On the advantage over a random assignment. Random Structures Algorithms 25(2):117–149.Crossref, Google Scholar
• 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
• 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
• 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
• 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
• 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
• Lenstra AK, Lenstra HW, Lovász L (1982) Factoring polynomials with rational coefficients. Math. Ann. 261(4):515–534.Crossref, Google Scholar
• 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
• 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
• Nesterov Y (2008) Accelerating the cubic regularization of Newton’s method on convex problems. Math. Program. 112(1):159–181.Crossref, Google Scholar
• 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
• Sahinidis NV (2016) BARON 15.6.5: Global Optimization of Mixed-Integer Nonlinear Programs: User’s Manual. https://minlp.com/downloads/docs/baron%20manual.pdf.Google Scholar
• 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
• Wassermann A (2002) Attacking the market split problem with lattice point enumeration. J. Combin. Optim. 6(1):5–16.Crossref, Google Scholar