Research Topic

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.

References

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

 

 

Supervisors

Marc Pfetsch, Anja Klein

Contact

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:

tfischer (at) mathem...

 Print |  Impressum |  Sitemap |  Search |  Contact |  Privacy Policy
zum Seitenanfangzum Seitenanfang