TOMLAB OPTIMIZATION ENVIRONMENT: mipSolve

mipSolve

Purpose

For solving mixed integer linear programming problems (MIP).

Description

Branch & Bound algorithm for Mixed-Integer Programming (MIP) using LP relaxation (Formulated as min-IP)

Problem

Solving MIP on the LP standard form with generalized lower and upper bounds:

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

Any of the x could be set as integer valued

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

Input Parameters

Fields in Prob:

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

   x_0:    Starting point x (If EMPTY, the LP solver solves a Phase I LP 
           to find a feasible point. Some LP solvers chooses own x_0).
 PriLevOpt Printing level (in lpSolve and DualSolve):
           =0 No output; >0 Convergence results; 
           >1 Output every iteration  >2 Output each step in the simplex alg
           For other LP solvers, see the documentation for the solver

 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.

 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
 SOL.optPar Parameters for the SOL solvers. If this field is set it is
           sent to the SOL solvers (if they are used as solvers)
           See help for minosTL.m, lpoptTL.m for how to set these parameters
 SOL.PrintFile Print file name for the SOL solvers. If this field is set it is
           sent to the SOL solvers (if they are used as solvers)

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

Special fields for MIP in Prob.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.

 VarWeight:Weight for each variable in the variable selection phase.
           A lower value gives higher priority. Setting
           Prob.MIP.VarWeight = c; for knapsack problems improve convergence.
 DualGap   mipSolve stops if the duality gap is less than DualGap
           DualGap = 1, stop at first integer solution
           e.g. DualGap = 0.01, stop if solution < 1% from optimal solution
 fIP       An upper bound on the IP value wanted. Makes it possible to
           cut branches and avoid node computations.
 xIP       The x-values giving the fIP value.
 KNAPSACK  True if a knapsack problem is to be solved, 
           then a knapsack heuristic is used.
 ----------------------------------------------------------------------

 Prob.Solver.Alg Node selection method
           = 0 Depth First (default)
           = 1 Breadth First
           = 2 Depth First. When integer solution found, use Breadth selection

 Prob.Solver.Method  Rule to select new variables in DualSolve/lpSolve:
           Note - this option is not used for other LP solvers.
           = 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 mipSolve

Fields used in Prob.optParam, in lpSolve and DualSolve
 IterPrint Print one line each iteration
 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 for function value tests
 eps_Rank  Rank tolerance

Output Parameters
Structure Result. Fields used:

lsei

nlpSolve