Given a point x inside a polytope P and a direction d, the projection of x along d asks to find the maximum step length t such that x+td is feasible; we say x+td is a pierce point because it belongs to the boundary of P. We address this projection sub-problem with arbitrary interior points x of P and arbitrary directions d, to solve different kind of LPs with prohibitively-many constraints: robust optimization and Benders decomposition problems (where P is a primal) or Column Generation problems (where P is a dual). Generalizing the standard separation sub-problem of the widely-used Cutting Planes, the above projection sub-problem serves as the main building block for designing a new Projective Cutting Planes algorithm. Numerical experiments on four problems in different optimization settings confirm the potential of the proposed ideas.
Citation
Technical Report of CS laboratory CEDRIC-18-4309 of CNAM, Paris (2018/07/18)
Article
View Cutting Planes by Projecting Interior Points onto Polytope Facets