Department of Computer, Control and Management Engineering

11:30 - A feasible rounding approach for mixed-integer optimization problems

Christoph Neumann

Institute of Operations Research, Karlsruhe Institute of Technology (KIT)

Email: [email protected]

We introduce granularity as a sufficient condition for the consistency of a mixed-integer optimization problem, and show how to exploit it for the computation of feasible points: for optimization problems which are granular, solving certain linear problems and rounding their optimal points always leads to feasible points of the original mixed-integer problem. Thus, the resulting feasible rounding approach is deterministic and even efficient, i.e., it computes feasible points in polynomial time.
The optimization problems appearing in the feasible rounding approaches have a structure that is similar to that of the continuous relaxation, and thus our approach has significant advantages over heuristics, as long as the problem is granular. For instance, the computational cost of our approach always corresponds to merely a single step of the feasibility pump. A computational study on optimization problems from the MIPLIB libraries demonstrates that granularity may be expected in various real world applications. Moreover, a comparison with Gurobi indicates that state of the art software does not always exploit granularity. Hence, our algorithms do not only possess a worst-case complexity advantage, but can also improve the CPU time needed to solve problems from practice.

Joint work with: Oliver Stein and Nathan Sudermann-Merx

12:15 - The Cone Condition and Nonsmoothness in Linear Generalized Nash Games

Oliver Stein

Institute of Operations Research, Karlsruhe Institute of Technology (KIT)

Email: [email protected]

The reformulation of a linear generalized Nash game as a single optimization problem by a Nikaido Isoda based gap function yields a piecewise linear problem. We introduce the so-called cone condition to characterize the differentiability points of this gap function. Other regularity conditions such as the linear independence constraint qualification or the strict Mangasarian-Fromovitz condition are only sufficient for smoothness, but can be verified more easily than the cone condition. Therefore, we present special cases where these conditions are not only sufficient, but also necessary for smoothness of the gap function. Our main tool in the analysis is a global extension of the gap function that allows us to overcome the common difficulty that its domain may not cover the whole space.

Joint work with: Nathan Sudermann-Merx

Bio sketch

Professor Dr. Oliver Stein is the executive director of the Institute of Operations Research (IOR) in the Karlsruhe Institute of Technology (KIT). Currently, he is Editor-in-chief of the international journal Mathematical Methods of Operations Research.
Prof. Dr. Stein is a renowned scholar whose research interests encompass many topics in Mathematical programming including Nonlinear optimization, Semi-infinite programming, Nash games, Parametric optimization and Mixed integer nonlinear programming. It is impossible here to even summarize the huge amount of influential works that he has authored during the last couple of decades.

M. Sc. Christoph Neumann is a Ph.D. student in Continuous Optimization, Institute of Operations Research (IOR), Karlsruhe Institute of Technology (KIT)