Todays most successful approach for solving general mixed integer programs (MIPs) is to use a so called branch-and-cut algorithm that operates on the underlying LP-relaxation of the MIP. In this algorithm, the integrality conditions are initially ignored, such that the MIP is simplified to a linear program. Afterwards, the integrality is restored by using (a) cutting planes and (b) an implicit enumeration through branch-and-bound.

(a) Cutting Planes	(b) Branch-And-Bound	(c) Domain Propagation	(d) Conflict Analysis

Branch-and-bound (b) is also used in algorithms for solving Constraint Programs (CPs), to divide the problem instance successively into smaller subproblems. In contrast to MIP-solvers, CP-solvers usually do not incorporate LP-relaxations and cutting planes to limit the search space and to prevent the enumeration of all potential solutions. Instead, they rely on constraint and domain propagation (c) and conflict analysis (d). The former is an inference technique, which tightens the domains of the variables. The latter is used on infeasible subproblems to retrieve information about the reason of the infeasibility. This information can then be used to tighten further domains of variables at other subproblems in the search tree.

The integration of MIP and CP techniques combines the more flexible modeling capabilities of constraint programming and the highly efficient solution methods of mixed integer programming that are tailored to the specific structure of linear constraints. In particular, the treatment of numerically difficult constraints by constraint programming techniques instead of using their LP-relaxations directly can help to ensure the stability of the underlying linear programs.

The tools for modeling and solving general MIPs developed in this project can be applied by users

• as a stand alone product: to create models for their problem classes, convert these models together with input data into mixed integer programs, and solve the resulting MIPs, or
• as a programming framework: to set up and manipulate MIPs with calls to the APIs, and solve them, while being able to control the search process with respect to their specific needs.

• extension of language capabilities by providing automatic linearizations of non-linear constraints
• improvement of data structures to speed up compilation
• incorporation of new types of non-linear constraints

• improvement of numerical stability and speed
• improvement of interaction with MIP frameworks

• implementation of specialized constraint handlers for specific constraints involved in real world problems in order to exploit the knowledge about the specific substructures
• implementation of algorithms for solving mixed-integer non-linear programs, integration of non-linear relaxations by appropriate interfaces.
• further improvement in the development of primal heuristics and cutting plane algorithms
• incorporation of an exact solving mode in order to find provably optimal solutions. See DFG-Project Exact Integer Programming.
• integration of existing and development of new features to handle symmetries in integer programs. See Matheon-Project B12 Symmetries in Integer Programming.
• development of a flexible, user definable modeling language for constraint integer programs

• R. Wunderling. Paralleler und objektorientierter Simplex-Algorithmus. PhD Thesis, Technische Universität Berlin, 1996.
• A. Martin, R. Weismantel. Contributions to General Mixed Integer Knapsack Problems. Technical Report 97-38, Zuse Institute Berlin, 1997.
• A. Martin. Integer Programs with Block Structure. Technische Universität Berlin, 1998.
• A. Martin, R. Weismantel. The Intersection of Knapsack Polyhedra and Extensions. In: Integer Programming and Combinatorial Optimization, pp. 243–256, 1998.
• A. Martin, R. Weismantel. Conjunctive Cuts for Integer Programs. Technical Report 98-18, Zuse Institute Berlin, 1998.
• H. Marchand, A. Martin, R. Weismantel, L. A. Wolsey. Cutting Planes in Integer and Mixed Integer Programming. Technical Report 99-44, Zuse Institute Berlin, 1999.
• T. Koch. Zimpl User Guide. Technical Report 01-20, Zuse Institute Berlin, 2001.
• T. Koch. Rapid Mathematical Programming. PhD Thesis, Technische Universität Berlin, 2004. ZIB-Report 04-58.
• T. Achterberg. SCIP - a framework to integrate Constraint and Mixed Integer Programming. Technical Report 04-19, Zuse Institute Berlin, 2004.
• T. Achterberg, T. Koch, A. Martin. Branching rules revisited. Operations Research Letters, 33:42–54, 2005.
• T. Achterberg, T. Koch, A. Martin. MIPLIB 2003. Operations Research Letters, 34(4):1–12, 2006.
• T. Achterberg, M. Grötschel, A. Martin. Teaching MIP modeling and solving. ORMS Today, 33(6):14–15, 2006.
• T. Berthold. Primal Heuristics for Mixed Integer Programs. Master's Thesis, Technische Universität Berlin, 2006.
• K. Wolter. Implementation of Cutting Plane Separators for Mixed Integer Programs. Master's Thesis, Technische Universität Berlin, 2006.
• T. Achterberg. Conflict Analysis in Mixed Integer Programming. Discrete Optimization, 4(1):4–20, 2007. Special issue: Mixed Integer Programming.
• T. Achterberg, T. Berthold. Improving the Feasibility Pump. Discrete Optimization, 4(1):77–86, 2007. Special issue: Mixed Integer Programming.
• T. Achterberg. Constraint Integer Programming. PhD Thesis, Technische Universität Berlin, 2007.
• Timo Berthold. RENS - Relaxation Enforced Neighborhood Search. Technical Report 07-28, Zuse Institute Berlin, 2007.
• Timo Berthold. Heuristiken im Branch-and-Cut-Framework SCIP. OR News, :24–25, 2008.
• Timo Berthold. Heuristics of the Branch-Cut-and-Price-Framework SCIP. In: Operations Research Proceedings 2007, pp. 31–36, 2008.
• Timo Berthold, Stefan Heinz, Marc E. Pfetsch. Solving Pseudo-Boolean Problems with SCIP. Technical Report 08-12, Zuse Institute Berlin, 2008.
• Tobias Achterberg, Timo Berthold, Thorsten Koch, Kati Wolter. Constraint Integer Programming: A New Approach to Integrate CP and MIP. In: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 5th International Conference, CPAIOR 2008, volume 5015 of Lecture Notes in Computer Science, pp. 6–20, May 2008.
• Tobias Achterberg, Stefan Heinz, Thorsten Koch. Counting solutions of integer programs using unrestricted subtree detection. In: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 5th International Conference, CPAIOR 2008, volume 5015 of Lecture Notes in Computer Science, pp. 278-282, May 2008.
• Tobias Achterberg, Timo Berthold, Stefan Heinz, Thorsten Koch, Kati Wolter. Constraint Integer Programming: Techniques and Applications. Technical Report 08-43, ZIB, 2008. submitted..