Grants and Contracts per year
Grants and Contracts Details
Description
Mixedinteger (linear and nonlinear) optimization is a discipline of mathematical
optimization that is concerned with nitedimensional, nonconvex 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 mixedinteger 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 cutgenerating 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 multirow and multicut 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 singlerow cuttingplane systems like the traditional Gomory mixedinteger 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 multirow cuttingplane 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
neuralnetwork architecture. Under the new architecture input, we will prove new theorems for
determining extremality. Further, we will use derivativefree 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 kcuts to use in conjunction along with algorithms to
measure the diversity of a set of input functions. Assessing diversity at the cutgenerating 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
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

Collaborative Research: NextGeneration Cutting Planes: Compression, Automation, Diversity, and ComputerAssisted Mathematics
8/1/20 → 7/31/24
Project: Research project