TOMLAB OPTIMIZATION ENVIRONMENT: cutplane

cutplane

Purpose

For solving mixed integer linear programming problems (MIP).

Syntax

   Result = cutplane(Prob);

Description

Cutting plane algorithm for Mixed-Integer Programming (MIP) using LP relaxation (Formulated as min-IP)

Note that the TOMLAB routine cpTransf.m can be used to rewrite an LP problem on another form to this standard form.

Problem

Solving MIP on the LP standard form, with additional upper bounds on x:

 
         min    c' * x.  x in R^n, A x = b_U, x >= 0, x <= x_U
          x

  Any of the x could be set as integer valued

Input Parameters

 Fields in Prob:
   c:      The vector c in c'x. 
   A:      The linear constraint matrix 
   b_L:    Lower bounds on linear constraints. NOT USED. Assumed to be == b_U
   b_U:    The upper bounds for the linear constraints
   x_L:    Lower bounds on x. NOT USED. Assumed to be 0.
   x_U:    Upper bounds on x. If empty assumed to be Inf.

   x_0:    Starting point x (If EMPTY, lpSolve solves Phase I LP to find a
           feasible point.
 QP.B:     Active set B_0 at start. 
           1  = Include variable x(i) is in basic set.
           0  = Variable x(i) is set on its lower bound
           -1 = Variable x(i) is set on its upper bound. NOT USED
           If EMPTY, lpSolve finds active set.
 MIP.IntVars: If IntVars is a scalar, then variables 1,...,IntVars are 
           assumed to be integers. 
           If empty, all variables are assumed non-integer (LP problem)
           If length(IntVars) > 1 ==> length(IntVars) == length(c) should hold,
           Then IntVars(i) ==1 ==> x(i) integer. IntVars(i) ==0 ==> x(i) real.
           If length(IntVars) < n, IntVars is assumed to be a set of indices.

 Prob.Solver.Alg     Not used
 Prob.Solver.Method  Rule to select new variables:
           = 0 Minimum Reduced Cost, sort variables increasing. (DEFAULT)
           = 1 Bland's Anti-cycling Rule 
           = 2 Minimum Reduced Cost, Dantzig's rule 
 PriLev    Print level in cutplane
 SolverLP  Name of the solver used for initial LP subproblem. If empty,
           the default solver is used. See GetSolver.m and tomSolve.m
 SolverDLP Name of the solver used for dual LP subproblems. If empty,
           the default solver is used. See GetSolver.m and tomSolve.m

 ----------------------------------------------------------------------

 Fields used in Prob.optParam, in lpSolve and DualSolve
 PriLev    Printing level (in lpSolve and DualSolve):
           =0 No output; >0 Convergence results; 
           >1 Output every iteration  >2 Output each step in the simplex alg
 MaxIter   Maximal number of iterations. max(10*dim(x),100) is DEFAULT.
 wait      Wait flag, pause each iteration if set true
 eps_f     Tolerance used to test convergence on the reduced costs
 eps_Rank  Rank tolerance
 xTol      Tolerance to judge if x-values are close

Output Parameters

 Structure Result. Fields used:
   Iter     Number of iterations
   ExitFlag Exit flag 
            == 0  => OK
            == 1  => Maximal number of iterations reached. No bfs found. 
            == 4  => No feasible point found with Phase1 Simplex
            Otherwise  the same flags as the dual LP solver returns
   ExitTest Text string giving ExitFlag and Inform information
   Inform   If ExitFlag > 0, Inform=ExitFlag.
   x_k      Solution
   v_k      Lagrange parameters. Constraints + lower + upper bounds
   QP.B     B  Optimal set. B(i)==1, include variable x(i) in basic set.
            sum(B==1)==length(b)  holds. See QP.B as input.
   QP.y     Dual parameters y (also part of v_k)
   p_dx     Search steps in x
   alphaV   Step lengths for each search step
   f_k      Function value c'*x
   g_k      Gradient c
   Solver   cutplane
   SolverAlgorithm  Description of method used
   x_0      Starting point x_0
   xState   State variable: Free==0; On lower == 1; On upper == 2; Fixed == 3;

conSolve

DualSolve