Optimization Online


Cutting Planes by Projecting Interior Points onto Polytope Facets

Daniel Porumbel(daniel.porumbel***at***cnam.fr)

Abstract: 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.

Keywords: Cutting Planes, Projection Sub-problem, Projective Cutting Planes

Category 1: Integer Programming (Cutting Plane Approaches )

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 3: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: Technical Report of CS laboratory CEDRIC-18-4309 of CNAM, Paris (2018/07/18)

Download: [PDF]

Entry Submitted: 07/30/2018
Entry Accepted: 07/30/2018
Entry Last Modified: 07/30/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society