TU CE GSC CE People at the Graduate School CE Alumni Tobias Fischer Research Project of Tobias Fischer

Optimization with Complementarity Constraints

Complementarity constraints require that at most one of two variables is nonzero. In discrete optimization, complementarity constraints have an important significance for the modeling of logical relations. With their help one can express that from a set of possible events not more than one is allowed to occur. The applications of such relations are abundant, e.g., in machine learning, communication systems, capital budgeting or scheduling. The aim of this project, is to investigate a branch-and-cut algorithm for complementarity constrained optimization problems, including presolving techniques, branching rules, primal heuristics and cutting planes. The implemented software has to deal with problem instances involving large data in a robust manner. Furthermore, it should recognize and exploit special structures of a given problem instance automatically. As a tool, we use the software SCIP [1] which provides a framework for solving discrete and combinatorial optimization problems. The purpose is to include further components to SCIP and to make them freely available for academic use.

[1] T. Achterberg. Constraint Integer Programming. PhD thesis, Technische Universität Berlin, 2007.

Marc Pfetsch, Anja Klein

Tobias Fischer

Dipl.-Math

Address: | Dolivostraße 15 |

D-64293 Darmstadt | |

Germany | |

Phone: | +49 6151 16 - 23496 |

Fax: | +49 6151 16 - 24404 |

Office: | S4|10-30 |

Email: | |