projective cutting planes

Semidefinite programming by Projective Cutting-Planes

  • Daniel Porumbel
    • Categories Semi-definite Programming Tags ,

    \(\) Seeking tighter relaxations of combinatorial optimization problems, semidefinite programming is a generalization of linear programming that offers better bounds and is still polynomially solvable. Yet, in practice, a semidefinite program is still significantly harder to solve than a similar-size Linear Program (LP). It is well-known that a semidefinite program can be written as an … Read more

    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