Grants and Contracts per year

## Grants and Contracts Details

### Description

Mixed-integer (linear and nonlinear) optimization is a discipline of mathematical
optimization that is concerned with nite-dimensional, non-convex optimization problems that in-
clude discrete decision variables such as those that model \yes/no" decisions. Problems of this type
arise in all areas of industry, in the guise of operations research. Algorithms for mixed-integer opti-
mization build upon convex optimization technology by relaxation, approximation, convexication,
and decomposition techniques. The trend to ever increasing problem sizes due to the availability of
Big Data has created new challenges that need to be addressed by a next generation of algorithms.
In this project, we focus on convexication, in particular the eective and ecient generation of
cutting planes.
In the linear case, we build upon a powerful abstraction of the convexication process, the notion
of cut-generating functions (cgf), which can explain the major cutting plane procedures in use in
today's solvers. In this abstraction, computing a cutting plane is considered ecient, because each
of its coecients is obtained by just evaluating the cgf on problem data; rather than by running an
algorithm. Prompted by recent research that has led to more and more complicated cgfs, and by
the goal of developing multi-row and multi-cut cutting plane systems, we open up this abstraction.
We investigate and develop classes of cgf that can be eciently represented and evaluated and
eciently selected for greatest eectiveness on a given problem.
For single-row cutting-plane systems like the traditional Gomory mixed-integer cut, ecient
evaluation can be achieved by restricting to a family of piecewise linear cgf with a small number
of breakpoints. We propose to compute the space of all extreme continuous piecewise linear cgf of
the Gomory{Johnson model with at most 20 breakpoints and at most 4 dierent slopes. This is a
space consisting of semialgebraic cells, parametrizing subadditive piecewise linear functions, glued
at the boundary where degeneration occurs. The computation of each cell requires the proof of a
theorem; we develop automated theorem proving technology for this, based on metaprogramming
and semialgebraic computations. By theoretical and computational techniques, we investigate the
local and global structure of this space; on this foundation we then develop optimization algorithms
for the ecient selection of eective cgfs for a given problem.
For novel multi-row cutting-plane systems, it is crucial to be able to compress a cgf so that
it can be represented in a small amount of space. We will study ways of representing cgfs in a
neural-network architecture. Under the new architecture input, we will prove new theorems for
determining extremality. Further, we will use derivative-free mixed integer optimization to create
optimally compact descriptions of these functions and verify their improved evaluation eciency
computationally.
Equally important as strength of cutting planes is the diversity of cutting planes. Within
a solver, many cutting planes will be applied and determining which cutting planes to use in
conjunction can have enormous impact on their eectiveness. We propose to study diversity of cut-
generating functions in the context of our model through the means of several dierent metrics. This
will include theorems regarding the strongest k-cuts to use in conjunction along with algorithms to
measure the diversity of a set of input functions. Assessing diversity at the cut-generating function
level will allow eectively diverse cuts to be utilized without added overhead of detecting diversity
online.

Status | Active |
---|---|

Effective start/end date | 8/1/20 → 7/31/24 |

### Funding

- National Science Foundation: $179,768.00

## Fingerprint

Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.

## Projects

- 1 Active