Class SimplexCuttingPlaneMinimizer

  • All Implemented Interfaces:
    Minimizer<ILPProblem,​MinimizationSolution<Vector>>, ConstrainedMinimizer<ILPProblem,​MinimizationSolution<Vector>>, Optimizer<ILPProblem,​MinimizationSolution<Vector>>
    Direct Known Subclasses:
    GomoryMixedCutMinimizer, GomoryPureCutMinimizer

    public class SimplexCuttingPlaneMinimizer
    extends Object
    implements ConstrainedMinimizer<ILPProblem,​MinimizationSolution<Vector>>
    The use of cutting planes to solve Mixed Integer Linear Programming (MILP) problems was introduced by Ralph E Gomory. Cutting plane methods for MILP work by solving a non-integer linear program, the linear relaxation of the given integer program. The theory of Linear Programming dictates that under mild assumptions (if the linear program has an optimal solution, and if the feasible region does not contain a line), one can always find an extreme point or a corner point that is optimal. The obtained optimum is tested for being an integer solution. If it is not, there is guaranteed to exist a linear inequality that separates the optimum from the convex hull of the true feasible set. Finding such an inequality is the separation problem, and such an inequality is a cut. A cut can be added to the relaxed linear program. Then, the current non-integer solution is no longer feasible to the relaxation. This process is repeated until an optimal integer solution is found.
    See Also:
    • Wikipedia: Cutting-plane method
    • "Der-San Chen, Robert G. Batson, Yu Dang, "11.2.1 Dual Cutting Place Approach," Applied Integer Programming: Modeling and Solution."