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

Class SimplexCuttingPlane

java.lang.Object

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

All Implemented Interfaces:

ConstrainedMinimizer<ILPProblem,MinimizationSolution<Vector>>, Minimizer<ILPProblem,MinimizationSolution<Vector>>, Optimizer<ILPProblem,MinimizationSolution<Vector>>, java.io.Serializable

Direct Known Subclasses:

GomoryMixedCut, GomoryPureCut

public class SimplexCuttingPlane
extends java.lang.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."

, Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	SimplexCuttingPlane.CutterFactory This factory constructs a new Cutter for each MILP problem.

Constructor Summary

Constructors

Constructor and Description
SimplexCuttingPlane(LPSimplexSolver solver, SimplexCuttingPlane.CutterFactory cutterFactory) Construct a cutting-plane minimizer to solve an MILP problem.

Method Summary

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

SimplexCuttingPlane

public SimplexCuttingPlane(LPSimplexSolver solver,
                           SimplexCuttingPlane.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 java.lang.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:

java.lang.Exception - when there is an error solving the problem