Utilizing disjunctive structures in optimization: new algorithms and methods

The proposed project focuses on developing fundamental theory, efficient algorithms/techniques, and software for solving mixed-integer optimization problems by utilizing disjunctive problem structures.

Such structures arise from disjunctive constraints that force the solution to satisfy either one set of constraints or another set of constraints, i.e., the feasible set is given by the union of a finite number of sets.

Together with logical dependencies among variables, disjunctive constraints form what we refer to as a disjunctive structure.

Such structures appear across a large variety of applications in operations research, but also in machine learning and artificial intelligence.

Large-scale problems with disjunctive structures are notoriously difficult to solve numerically, which follows from the lack of computationally efficient and strong convex relaxations.

The project focuses on how to utilize disjunctive structures to obtain stronger relaxations and new parallelizable algorithms to solve computationally and numerically difficult optimization problems.

We will develop novel lifted and non-lifted formulations for problems with disjunctive structures, and efficient cutting plane algorithms that utilize specific structures and enable efficient parallelization.

Besides general problem classes we also consider two specific types of problems, so-called chance-constrained and multi-objective mixed-integer problems, with non-trivial disjunctive structures.