×

Modeling with metaconstraints and semantic typing of variables. (English) Zbl 1338.90385

Summary: Recent research in hybrid optimization shows that a combination of technologies that exploits their complementary strengths can significantly speed up computation. The use of high-level metaconstraints in the problem formulation can achieve a substantial share of these computational gains by better communicating problem structure to the solver. During the solution process, however, metaconstraints give rise to reformulations or relaxations that introduce auxiliary variables, and some of the variables in one metaconstraint’s reformulation may be functionally the same as or related to variables in another metaconstraint’s reformulation. These relationships must be recognized to obtain a tight overall relaxation. We propose a modeling scheme based on semantic typing that systematically addresses this problem while providing simpler, self-documenting models. It organizes the model around predicates and declares variables by associating each with a predicate through a keyword that is analogous to a database query. We present a series of examples to illustrate this idea over a wide variety of applications.

MSC:

90C30 Nonlinear programming
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ajili F, Wallace M (2003) Hybrid problem solving in ECLiPSe. Milano M, ed. Constraint and Integer Programming: Toward a Unified Methodology (Springer, New York), 169-201. · Zbl 1078.90563
[2] Beale EML, Tomlin JA (1970) Special facilities in a general mathematical programming system for nonconvex problems using ordered sets of variables. Lawrence J, ed. Proc. 5th Internat. Conf. Oper. Res. (Tavistock Publications, London), 447-454.
[3] Beldiceanu N, Carlsson M, Rampon J-X (2011) Global constraint catalog. Working version of SICS Technical Report 2010-07. Accessed June 9, 2015, http://www.emn.fr/z-info/sdemasse/gccat/.
[4] Bhargava HK, Kimbrough SO (1993) Model management: An embedded languages approach. Decision Support Systems 10(3):277-299. CrossRef
[5] Bhargava HK, Kimbrough SO, Krishnan R (1991) Unique names violations, a problem for model integration or you say tomato, I say tomahto. ORSA J. Comput. 3(2):107-120. Link
[6] Bhargava HK, Krishnan R, Piela P (1998) On formal semantics and analysis of typed modeling languages: An analysis of ascend. INFORMS J. Comput. 10(2):189-208. Link · Zbl 1055.68547
[7] Bisschop J, Entriken R (1993) AIMMS: The Modeling System (Paragon Decision Technology, Haarlem, Netherlands).
[8] Bradley GH, Clemence RD (1988) Model integration with a typed executable modeling language. Proc. 21st Hawaii Internat. Conf. System Sci., Vol. III (IEEE Computer Society, Washington, DC), 403-410. CrossRef
[9] Bray T, Paoli J, Sperberg-McQueen C, Maler E, Yergeau F, eds. (2004) Extensible Markup Language (XML) 1.0 (W3C, Boston). Accessed November 2, 2013, http://www.w3.org/TR/REC-xml/.
[10] Carlier J, Pinson E (1990) A practical use of Jackson’s preemptive schedule for solving the job-shop problem. Ann. Oper. Res. 26(1-4):269-287. · Zbl 0709.90061
[11] Dantzig GB (1951) Application of the simplex method to a transportation problem. Koopmans TC, ed. Activity Analysis of Production and Allocation (Wiley, New York), 359-373.
[12] Euler L (1849) Recherches sur une espèce de carrés magiques, Vol. II. Fuss PH, Fuss N, eds. Commentationes Arithmeticae, Collectae (Academiae Scientiarum Imperialis Petropolitanae, St. Petersburg, Russia), 302-361.
[13] Fair Isaac Corporation (2009) Xpress Optimizer Reference Manual (FICO, San Jose, CA).
[14] Fourer R, Gay DM, Kernighan BW (2002) AMPL: A Modeling Language for Mathematical Programming, 2nd ed. (Duxbury Press, Pacific Grove, CA).
[15] Gecode Team (2006) Gecode: Generic constraint development environment. Accessed November 2, 2013, http://www.gecode.org.
[16] Genç-Kaya L, Hooker JN (2014) The Hamiltonian circuit polytope. Technical report, Carnegie Mellon University, Pittsburgh.
[17] Geoffrion AM (1992a) The SML language for structured modeling: Levels 1 and 2. Oper. Res. 40(1):38-57. Link · Zbl 0825.90665
[18] Geoffrion AM (1992b) The SML language for structured modeling: Levels 3 and 4. Oper. Res. 40(1):58-75. Link · Zbl 0825.90666
[19] Heerink K (2012) AIMMS: Tutorial for Professionals (Paragon Decision Technology). Accessed November 2, 2013, http://www.aimms.com/aimms/download/manuals/aimms_tutorial_professional.pdf.
[20] Heipcke S (2009) Hybrid MIP/CP solving with Xpress-Optimizer and Xpress-Kalis. White paper, FICO Xpress Optimization Suite, Fair Isaac Corporation, San Jose, CA.
[21] Hooker JN (2005) A search-infer-and-relax framework for integrating solution methods. Barták R, Milano M, eds. Proc. Conf. Integration AI OR Techniques Constraint Programming Combinatorial Optim. Problems (CP-AI-OR), Lecture Notes in Computer Science, Vol. 3709 (Springer-Verlag, Berlin), 314-327. CrossRef
[22] Hooker JN (2011) Hybrid modeling. Milano M, Van Hentenryck P, eds. Hybrid Optimization–The Ten Years of CPAIOR, Vol. 45. Springer Optimization and Its Applications (Springer, New York), 11-62. CrossRef · Zbl 1206.90177
[23] Hooker JN (2012) Integrated Methods for Optimization, 2nd ed. (Springer, New York). CrossRef
[24] IBM (2009a) IBM ILOG CP Optimizer V2.3 User’s Manual (IBM Corp., New York).
[25] IBM (2009b) IBM ILOG CPLEX Optimizer User’s Manual (IBM Corp., New York).
[26] Kennedy A (2010) Types for units-of-measure: Theory and practice. Horváth Z, Plasmeijer R, Zsók V, eds. Third Central Euro. Functional Programming School, Vol. 6299. Lecture Notes in Computer Science (Springer-Verlag, Berlin), 268-305. CrossRef
[27] Laurière J-L (1978) A language and a program for stating and solving combinatorial problems. Artificial Intelligence 1(10):29-127. CrossRef
[28] Lopes L, Fourer R (2009) Object oriented modeling of multistage stochastic linear programs. Chinneck JW, Kristjansson B, Saltzman MJ, eds. Operations Research and Cyber-Infrastructure, Operations Research/Computer Science Interfaces Series, Vol. 47.6 (Springer, New York), 21-41. CrossRef
[29] Marriott KG, Nethercote N, Rafeh R, Stuckey PJ, Garcia De La Banda MJ, Wallace M (2008) The design of the Zinc modelling language. Constraints 13(3):229-267. CrossRef · Zbl 1146.68352
[30] McCormick GP (1983) Nonlinear Programming: Theory, Algorithms, and Applications (Wiley Interscience, New York).
[31] Object Management Group, Inc. (2010) OMG Unified Modeling Language (UML) Superstructure Specification, version 2.3. Accessed November 2, 2013, http://www.uml.org.
[32] Ruland KS, Rodin EY (1998) Survey of facial results for the traveling salesman polytope. Math. Comput. Modelling 27(8):11-27. CrossRef · Zbl 0995.90083
[33] Sabharwal A (2005) SymChaff: A structure-aware satisfiability solver. Proc. 20th National Conf. Artificial Intelligence (AAAI) (AAAI Press, Palo Alto, CA), 467-474.
[34] Sabharwal A (2009) SymChaff: Exploiting symmetry in a structure-aware satisfiability solver. Constraints 14(4):478-505. CrossRef · Zbl 1186.68442
[35] Van Hentenryck P, Carillon J-P (1988) Generality versus specificity: An experience with AI and OR techniques. Proc. 7th National Conf. Artificial Intelligence (AAAI) (AAAI Press, Palo Alto, CA), 660-664.
[36] Van Hentenryck P, Michel L (2005) Constraint-Based Local Search (MIT Press, Cambridge, MA). · Zbl 1153.90582
[37] Van Hentenryck P, Lustig I, Michel L, Puget JF (1999) The OPL Optimization Programming Language (MIT Press, Cambridge, MA).
[38] Yunes T, Aron ID, Hooker JN (2010) An integrated solver for optimization problems. Oper. Res. 58(2):342-356. Link · 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.