Abstract
Constraint programming offers modeling features and solution methods that are unavailable in mathematical programming but are often flexible and efficient for scheduling and other combinatorial problems. Yet mathematical programming is well suited to declarative modeling languages and is more efficient for some important problem classes. This raises this issue as to whether the two approaches can be combined in a declarative modeling framework. This paper proposes a general declarative modeling system in which the conditional structure of the constraints shows how to integrate any “checker” and any special-purpose “solver”. In particular this integrates constraint programming and optimization methods, because the checker can consist of constraint propagation methods, and the solver can be a linear or nonlinear programming routine.
Similar content being viewed by others
References
A. Aggoun and N. Beldiceanu, Extending CHIP in order to solve complex scheduling and placement problems, Math. Comput. Modelling 17(7) (1993) 57–73.
N. Beldiceanu and E. Contejean, Introducing global constraints in CHIP, Math. Comput. Modelling 20(12) (1994) 97–123.
A. Bockmayr and T. Kasper, A unifying framework for integer and finite domain constraint programming, INFORMS Journal on Computing 10, 287-300.
A. Brooke, D. Kendrick and A. Meeraus, GAMS-A User's Guide (Scientific Press, San Francisco, 1992).
A. Brooke and A. Meeraus, On the development of a general algebraic modeling system in a strategic planning environment, Mathematical Programming Study 20 (1982) 1–29.
Y. Caseau and F. Laburthe, Improved CLP scheduling with task intervals, in: Logic Programming-Proceedings of the 11th International Conference on Logic Programming, ed. P. Van Hentenryck, Massachusetts Institute of Technology (MIT Press, 1994) pp. 369-383.
Y. Caseau and F. Laburthe, Solving small TSPs with constraints, in: Proceedings of the 14th International Conference on Logic Programming, Cambridge (July 8-11, 1997), ed. L. Naish (MIT Press, 1997) pp. 316-330.
R. Fourer, Extending a general-purpose algebraic modeling language to combinatorial optimization: A logic programming approach, in: Advances in Computational and Stochastic Optimization, Logic Programming, and Heuristic Search (Kluwer Academic, Dordrecht, 1994).
R. Fourer, D.M. Gay and B.W. Kernighan, A modeling language for mathematical programming, Management Science 36 (1990) 519–554.
R. Fourer, D.M. Gay and B.W. Kernighan, AMPL: A Modeling Language for Mathematical Programming (Duxbury Press, Wadsworth, Belmont, CA, 1992).
H.-J. Kim and J.N. Hooker, Solving fixed-charge network flow problems with a hybrid optimization and constraint programming approach, to appear in Annals of Operations Research.
J.N. Hooker and M.A. Osorio, Mixed logical/linear programming, Discrete Applied Mathematics 96-97(1-3) (1999) 395–442.
K. Marriott and P.J. Stuckey, Programming with Constraints: An Introduction (MIT Press, 1998).
L. Michel and P. Van Hentenryck, Helios: A modeling language for global optimization and its implementation in Newton, Theoretical Computer Science 173(1) (1997) 3–48.
P.M. Pardalos and J.B. Rosen, Constrained Global Optimization: Algorithms and Applications, Lecture Notes in Computer Science 268 (Springer, 1987).
J.-C. Régin, A filtering algorithm for constraints of difference in CSPs, in: Proceedings of 12th National Conference on Artificial Intelligence (AAAI-94) (1994) pp. 362-367.
R. Rodošek, M. Wallace and M. Hajian, A new approach to integrating mixed integer programming and constraint logic programming, Baltzer Journals (1997).
P. Van Hentenryck, Constraint Satisfaction in Logic Programming, Logic Programming Series (MIT Press, Cambridge, MA, 1989).
P. Van Hentenryck, The OPL Optimization Programming Language (MIT Press, 1999).
P. Van Hentenryck and L. Michel, Newton: Constraint programming over nonlinear real constraints, Science of Computer Programming 30(1-2) (1998) 83–118.
P. Van Hentenryck, V. Saraswat and Y. Deville, Design, implementation, and evaluation of the constraint language cc(FD), in: Constraint Programming: Basics and Trends, ed. A. Podelski, Lecture Notes in Computer Science 910 (Springer, 1995).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Hooker, J., Kim, HJ. & Ottosson, G. A Declarative Modeling Framework that Integrates Solution Methods. Annals of Operations Research 104, 141–161 (2001). https://doi.org/10.1023/A:1013195004424
Issue Date:
DOI: https://doi.org/10.1023/A:1013195004424