[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Constraint Integer Programming: A New Approach to Integrate CP and MIP

  • Conference paper
Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2008)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5015))

Abstract

This article introduces constraint integer programming (CIP), which is a novel way to combine constraint programming (CP) and mixed integer programming (MIP) methodologies. CIP is a generalization of MIP that supports the notion of general constraints as in CP. This approach is supported by the CIP framework SCIP, which also integrates techniques from SAT solving. SCIP is available in source code and free for non-commercial use.

We demonstrate the usefulness of CIP on two tasks. First, we apply the constraint integer programming approach to pure mixed integer programs. Computational experiments show that SCIP is almost competitive to current state-of-the-art commercial MIP solvers. Second, we employ the CIP framework to solve chip design verification problems, which involve some highly non-linear constraint types that are very hard to handle by pure MIP solvers. The CIP approach is very effective here: it can apply the full sophisticated MIP machinery to the linear part of the problem, while dealing with the non-linear constraints by employing constraint programming techniques.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Achterberg, T.: Conflict analysis in mixed integer programming. Discrete Optimization 4(1), 4–20 (2007) (Special issue: Mixed Integer Programming)

    Article  MATH  MathSciNet  Google Scholar 

  2. Achterberg, T.: Constraint Integer Programming. PhD thesis, Technische Universität Berlin (2007), http://opus.kobv.de/tuberlin/volltexte/2007/1611/

  3. Achterberg, T., Koch, T., Martin, A.: Branching rules revisited. Operations Research Letters 33, 42–54 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  4. Achterberg, T., Koch, T., Martin, A.: MIPLIB 2003. Operations Research Letters 34(4), 1–12 (2006), http://miplib.zib.de

    Article  MathSciNet  Google Scholar 

  5. Althaus, E., Bockmayr, A., Elf, M., Jünger, M., Kasper, T., Mehlhorn, K.: SCIL – symbolic constraints in integer linear programming. In: Möhring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 75–87. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  6. Andreello, G., Caprara, A., Fischetti, M.: Embedding \(\{0,\frac{1}{2}\}\)-cuts in a branch-and-cut framework: A computational study. INFORMS Journal on Computing 19(2), 229–238 (2007)

    Article  MathSciNet  Google Scholar 

  7. Applegate, D.L., Bixby, R.E., Chvátal, V., Cook, W.J.: The Traveling Salesman Problem. Princeton University Press, Princeton (2006)

    MATH  Google Scholar 

  8. Apt, K.R.: Principles of Constraint Programming. Cambridge University Press, Cambridge (2003)

    Google Scholar 

  9. Aron, I.D., Hooker, J.N., Yunes, T.H.: SIMPL: A system for integrating optimization techniques. In: Régin, J.-C., Rueher, M. (eds.) CPAIOR 2004. LNCS, vol. 3011, pp. 21–36. Springer, Heidelberg (2004)

    Google Scholar 

  10. Balas, E.: Facets of the knapsack polytope. Mathematical Programming 8, 146–164 (1975)

    Article  MATH  MathSciNet  Google Scholar 

  11. Balas, E., Ceria, S., Cornuéjols, G.: Mixed 0-1 programming by lift-and-project in a branch-and-cut framework. Management Science 42, 1229–1246 (1996)

    MATH  Google Scholar 

  12. Berthold, T.: Primal heuristics for mixed integer programs. Master’s thesis, Technische Universität Berlin (2006)

    Google Scholar 

  13. Berthold, T.: Heuristics of the branch-cut-and-price-framework SCIP. ZIB-Report 07-30, Zuse Institute Berlin, Operations Research 2007 (to appear, 2007)

    Google Scholar 

  14. Bockmayr, A., Kasper, T.: Branch-and-infer: A unifying framework for integer and finite domain constraint programming. INFORMS Journal on Computing 10(3), 287–300 (1998)

    MATH  MathSciNet  Google Scholar 

  15. Bockmayr, A., Pisaruk, N.: Solving assembly line balancing problems by combining IP and CP. In: Sixth Annual Workshop of the ERCIM Working Group on Constraints (June 2001)

    Google Scholar 

  16. Brinkmann, R., Drechsler, R.: RTL-datapath verification using integer linear programming. In: Proceedings of the IEEE VLSI Design Conference, pp. 741–746 (2002)

    Google Scholar 

  17. Computational infrastructure for operations research, http://www.coin-or.org

  18. Eén, N., Sörensson, N.: An extensible SAT-solver. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919, pp. 502–518. Springer, Heidelberg (2004)

    Google Scholar 

  19. Forrest, J.J., Hirst, J.P.H., Tomlin, J.A.: Practical solution of large scale mixed integer programming problems with UMPIRE. Management Science 20(5), 736–773 (1974)

    MathSciNet  MATH  Google Scholar 

  20. Fügenschuh, A., Martin, A.: Computational integer programming and cutting planes. In: Aardal, K., Nemhauser, G.L., Weismantel, R. (eds.) Discrete Optimization. Handbooks in Operations Research and Management Science, ch. 2, vol. 12, pp. 69–122. Elsevier, Amsterdam (2005)

    Google Scholar 

  21. Gomory, R.E.: Solving linear programming problems in integers. In: Bellman, R., Hall, J.M. (eds.) Combinatorial Analysis, Symposia in Applied Mathematics X, pp. 211–215, Providence, RI, American Mathematical Society (1960)

    Google Scholar 

  22. Hooker, J.N., Osorio, M.A.: Mixed logical/linear programming. Discrete Applied Mathematics 96-97(1), 395–442 (1999)

    Article  MathSciNet  Google Scholar 

  23. ILOG CPLEX. Reference Manual, http://www.ilog.com/products/cplex

  24. International technology roadmap for semiconductors (2005), http://public.itrs.net

  25. Jain, V., Grossmann, I.E.: Algorithms for hybrid MILP/CP models for a class of optimization problems. INFORMS Journal on Computing 13(4), 258–276 (2001)

    Article  MathSciNet  Google Scholar 

  26. Johnson, E.L., Padberg, M.W.: Degree-two inequalities, clique facets, and biperfect graphs. Annals of Discrete Mathematics 16, 169–187 (1982)

    MATH  MathSciNet  Google Scholar 

  27. Klar, A.: Cutting planes in mixed integer programming. Master’s thesis, Technische Universität Berlin (2006)

    Google Scholar 

  28. Letchford, A.N., Lodi, A.: Strengthening Chvátal-Gomory cuts and Gomory fractional cuts. Operations Research Letters 30(2), 74–82 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  29. Marchand, H.: A polyhedral study of the mixed knapsack set and its use to solve mixed integer programs. PhD thesis, Faculté des Sciences Appliquées, Université catholique de Louvain (1998)

    Google Scholar 

  30. Marchand, H., Martin, A., Weismantel, R., Wolsey, L.A.: Cutting planes in integer and mixed integer programming. Discrete Applied Mathematics 123/124, 391–440 (2002)

    MathSciNet  Google Scholar 

  31. Marques-Silva, J.P., Sakallah, K.A.: GRASP: A search algorithm for propositional satisfiability. IEEE Transactions of Computers 48, 506–521 (1999)

    Article  MathSciNet  Google Scholar 

  32. Mittelmann, H.: Decision tree for optimization software: Benchmarks for optimization software, http://plato.asu.edu/bench.html

  33. Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. John Wiley & Sons, Chichester (1988)

    MATH  Google Scholar 

  34. Opencores, http://www.opencores.org

  35. Padberg, M.W., van Roy, T.J., Wolsey, L.A.: Valid inequalities for fixed charge problems. Operations Research 33(4), 842–861 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  36. Refalo, P.: Tight cooperation and its application in piecewise linear optimization. In: Jaffar, J. (ed.) CP 1999. LNCS, vol. 1713, pp. 375–389. Springer, Heidelberg (1999)

    Google Scholar 

  37. Rodosek, R., Wallace, M.G., Hajian, M.T.: A new approach to integrating mixed integer programming and constraint logic programming. Annals of Operations Research 86(1), 63–87 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  38. Savelsbergh, M.W.P.: Preprocessing and probing techniques for mixed integer programming problems. ORSA Journal on Computing 6, 445–454 (1994)

    MATH  MathSciNet  Google Scholar 

  39. Stallman, R.M., Sussman, G.J.: Forward reasoning and dependency directed backtracking in a system for computer-aided circuit analysis. Artificial Intelligence 9, 135–196 (1977)

    Article  MATH  Google Scholar 

  40. Timpe, C.: Solving planning and scheduling problems with combined integer and constraint programming. OR Spectrum 24(4), 431–448 (2002)

    Article  MATH  Google Scholar 

  41. Wolter, K.: Implementation of cutting plane separators for mixed integer programs. Master’s thesis, Technische Universität Berlin (2006)

    Google Scholar 

  42. Wunderling, R.: Paralleler und objektorientierter Simplex-Algorithmus. PhD thesis, Technische Universität Berlin (1996)

    Google Scholar 

  43. Zhang, L., Madigan, C.F., Moskewicz, M.W., Malik, S.: Efficient conflict driven learning in a boolean satisfiability solver. In: ICCAD, pp. 279–285 (2001)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. ILOG Deutschland, Ober-Eschbacher Str. 109, 61352, Bad Homburg, Germany

    Tobias Achterberg

  2. Zuse Institute Berlin, Takustr. 7, 14195, Berlin, Germany

    Timo Berthold, Thorsten Koch & Kati Wolter

Authors
  1. Tobias Achterberg
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Timo Berthold
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Thorsten Koch
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Kati Wolter
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Laurent Perron Michael A. Trick

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Achterberg, T., Berthold, T., Koch, T., Wolter, K. (2008). Constraint Integer Programming: A New Approach to Integrate CP and MIP. In: Perron, L., Trick, M.A. (eds) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. CPAIOR 2008. Lecture Notes in Computer Science, vol 5015. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-68155-7_4

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-68155-7_4

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-68154-0

  • Online ISBN: 978-3-540-68155-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation