# SuanShu, a Java numerical and statistical library

com.numericalmethod.suanshu.optimization.multivariate.constrained.integer.linear.cuttingplane

## Class SimplexCuttingPlaneMinimizer

• java.lang.Object
• com.numericalmethod.suanshu.optimization.multivariate.constrained.integer.linear.cuttingplane.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.
• 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."
• ### Nested Class Summary

Nested Classes
Modifier and Type Class and Description
static interface  SimplexCuttingPlaneMinimizer.CutterFactory
This factory constructs a new Cutter for each MILP problem.
• ### Constructor Summary

Constructors
Constructor and Description
SimplexCuttingPlaneMinimizer(LPSimplexSolver solver, SimplexCuttingPlaneMinimizer.CutterFactory cutterFactory)
Construct a cutting-plane minimizer to solve an MILP problem.
• ### Method Summary

All Methods
Modifier and Type Method and Description
MinimizationSolution<Vector> solve(ILPProblem problem)
Solve an optimization problem, e.g., OptimProblem.
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### Constructor Detail

• #### SimplexCuttingPlaneMinimizer

public SimplexCuttingPlaneMinimizer(LPSimplexSolver solver,
SimplexCuttingPlaneMinimizer.CutterFactory cutterFactory)
Construct a cutting-plane minimizer to solve an MILP problem.
Parameters:
solver - a simplex solver to solve an LP problem
cutterFactory - a factory that constructs a new Cutter for each problem
• ### Method Detail

• #### solve

public MinimizationSolution<Vector> solve(ILPProblem problem)
throws Exception
Description copied from interface: Optimizer
Solve an optimization problem, e.g., OptimProblem.
Specified by:
solve in interface Optimizer<ILPProblem,MinimizationSolution<Vector>>
Parameters:
problem - an optimization problem
Returns:
a solution to the optimization problem
Throws:
Exception - when there is an error solving the problem