Daniel Porumbel

Cutting Planes by Projecting Interior Points onto Polytope Facets

  • Daniel Porumbel
    • Categories Branch and Cut Algorithms, Cutting Plane Approaches, Linear Programming Tags , ,

    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 … Read more

    Ray Projection for Optimizing Polytopes with Prohibitively Many Constraints in Set-Covering Column Generation

  • Daniel Porumbel
    • Categories Combinatorial Optimization, Polyhedra Tags ,

    A recurrent task in mathematical programming requires optimizing polytopes with prohibitively-many constraints, e.g., the primal polytope in cutting-plane methods or the dual polytope in Column Generation (CG). This paper is devoted to the ray projection technique for optimizing such polytopes: start from a feasible solution and advance on a given ray direction until intersecting a … Read more