UROP Project

Generic Decomposition Algorithms for Integer Programs

There is no alternative to integer programming when it comes to computing proven quality or even optimal solutions to large-scale hard combinatorial optimization problems. In practical applications, matrices often have special structures exploitable in decomposition algorithms, in particular in brance-and-price. This opened the way to the solution of mixed integer programs (MIPs) of enormous size and complexity, both from industry and within mathematics, computer science, and operations research. Yet, as the state-of-the-art, branch-and-price is implemented ad hoc for every new problem. Various frameworks are very helpful in this respect, still, this requires a solid expert knowledge. This project aims at making a significant contribution towards a generic implementation of decomposition algorithms. As a longterm vision, a MIP solver should be able to apply a decomposition algorithm without any user interaction. A precondition for such an automation is the answer to important algorithmic and theoretical questions, among them: * recognition of decomposable structures in matrices and/or MIPs * development of a theory (and appropriate algorithms) for evaluating the quality of a decomposition In this project we address these questions. From a mathematical point of view, there are interesting relations to polyhedral combinatorics, graph theory, and linear algebra. A generic implementation of our findings is planned to be provided to the research community. To this end we closely cooperate with developers of MIP solvers (such as SCIP) and modeling languages (such as GAMS).

Task

Research & development on current topics of the project. This may include the development, implementation, analysis, and testing of graph algorithms, integer programs, heuristics, or similar in the context of decomposing a matrix into substructures; proving computational complexity of optimization problems arising in the project etc. The topic is very broad, it is computer science and/or mathematics related, feel free to get in touch for further information.

Requirements

- Excellent programming skills, preferably in C, C++, Java - Familiarity with Linux - Background in integer programming or algorithms is very helpful