Class SimplexCuttingPlaneMinimizer
- java.lang.Object
-
- dev.nm.solver.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.- 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."
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static interface
SimplexCuttingPlaneMinimizer.CutterFactory
This factory constructs a newCutter
for each MILP problem.
-
Constructor Summary
Constructors Constructor Description SimplexCuttingPlaneMinimizer(LPSimplexSolver solver, SimplexCuttingPlaneMinimizer.CutterFactory cutterFactory)
Construct a cutting-plane minimizer to solve an MILP problem.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description MinimizationSolution<Vector>
solve(ILPProblem problem)
Solve an optimization problem, e.g.,OptimProblem
.
-
-
-
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 problemcutterFactory
- a factory that constructs a newCutter
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 interfaceOptimizer<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
-
-