D. Porumbel
The goal is to replace the separation sub-problem of the well-known
Cutting-Planes method with the projection sub-problem: given any strictly
interior point x inside a polytope P and an arbitrary direction d, perform a
projection along x->d and determine the first-hit point x+t^*d where P is
"pierced". Imagine one "shooting" from x towards d: the first-hit point x+t^*d
is the point where the bullet hits (a wall/facet of) P. This sub-problem is
difficult because P has a prohibitively large number of facets. Compared to
Cutting-Planes, the main advantage of Projective Cutting-Planes is that it has a
built-in functionality to generate a feasible inner solution x+t^*d at each
iteration. By selecting a sequence of points x and d, the feasible solutions
x+t^*d converge iteratively to an optimal solution opt(P).
The audience may choose between:
- a robust optimization problem
- a problem formulated using a Benders decomposition
- the graph coloring problem expressed using a Column Generation model, where P
is a dual.
This work is based on the paper [Daniel Porumbel, Projective Cutting-Planes,
SIAM Journal on Optimization, 30(1): 1007-1032, 2020] and on a paper in
revision.
Keywords: Cutting Planes, Separation subproblem, Projection subproblem
Scheduled
TC2 Integer Optimization
June 10, 2021 12:30 PM
2 - LV Kantorovich
