Xpress for MATLAB LP, MIP, MILP KNAPSACK Test Problems

6 Test Routines in Tomlab Format

A set of test routines have been defined illustrating the combined use of TOMLAB and Xpress^MP The test routines are shown in Table 4. The knapsack test routine xpknapsTL is similar to xpknaps discussed in the previous subsection. It runs three knapsack test examples. It is possible to change the cut strategy and whether to use the knapsack heuristic in the callback routine xpcb_gl. The problems are setup using the TOMLAB Format.

Table 4: The test routines and utilities.

Function Description Section

xptomtest1 Tests of problems predefined in the TOMLAB IF format. LP, QP and MIP problems are solved calling the driver routine tomRun. C.4

xptomtest2 Tests of a simple MIP problem defined in the TOMLAB (TQ) format. The problem is solved as an LP and MIP problem, with or without slacks defined. tomRun. C.5

xpknapsTL The same tests as in xpknaps, but the TOMLAB format and system is used. C.7

The following example shows how to run a predefined problem, one of the problems in xpknapsTL, using the TOMLAB Init File (IF) format. Some fields that changes control variables are set to make Xpress^MP work slower. Then a simple predefined heuristic is run to try to improve the convergence. For this example it can get down the number of node visited from 135 to 35.

Prob = ProbInit('mip_prob',7); % Create Prob structure from predefined problem
Prob.MIP
ans =
    xpcontrol: []
      IntVars: [30x1 double]
    VarWeight: [30x1 double]
     KNAPSACK: 1
     callback: [14x1 double]
% Make Xpress-MP work slower by disabling presolve and cuts.
Prob.MIP.xpcontrol.CUTSTRATEGY = 0; % Use no cuts
Prob.MIP.xpcontrol.PRESOLVE = 0;    % Use no presolve
Prob.MIP.xpcontrol.MIPLOG = 3;      % Call the callback each node
Result = tomRun('xpress-mp',Prob,1); % Call Xpress-MP using Tomlab driver

===== * * * =============================================== * * *
TOMLAB SOL - Three weeks demonstration single user license
=================================================================
Problem: mip_prob -  7: Weingartner 1 - 2/28 0-1 knapsack  f_k -141278.000000000000000000
                                              User given f(x_*)-141278.000000000000000000

Solver: Xpress-MP.  EXIT=0.  INFORM=6.
Mex-interface to Xpress-MP LP/QP/MIP/MIQP solver
Global search complete - integer solution found

FuncEv  135 GradEv    0 Iter  135
CPU time: 0.250000 sec. Elapsed time: 0.250000 sec.

Prob.MIP.callback(9) = 1; % Enable Global Log callback
Result = tomRun('xpress-mp',Prob,1);
% Because Prob.MIP.KNAPSACK == 1, the predefined heuristic is tried

--- Global Log. Node      1. Node depth   1. Best Bound -142019.000000.
Node 1: LP-obj -142019;  Heuristic value -139508 *** Updated cutoff to -139507
--- Global Log. Node      2. Node depth   2. Best Bound -142019.000000.
Node 2: LP-obj -141897;  Heuristic value -140768 *** Updated cutoff to -140767
--- Global Log. Node      3. Node depth   3. Best Bound -142019.000000.
Node 3: LP-obj -141873;  Heuristic value -138493
--- Global Log. Node      4. Node depth   4. Best Bound -142019.000000.
Node 4: LP-obj -141726;  Heuristic value -139618
--- Global Log. Node      5. Node depth   3. Best Bound -142019.000000.
Node 5: Not applying heuristic (status is Cutoff in dual)
--- Global Log. Node      6. Node depth   5. Best Bound -142019.000000.
Node 6: LP-obj -141707;  Heuristic value -138168
--- Global Log. Node      7. Node depth   6. Best Bound -142019.000000.
Node 7: LP-obj -141655;  Heuristic value -138068
--- Global Log. Node      8. Node depth   5. Best Bound -142019.000000.
Node 8: Not applying heuristic (status is Cutoff in dual)
--- Global Log. Node      9. Node depth   6. Best Bound -142019.000000.
Node 9: Not applying heuristic (status is Infeasible)
--- Global Log. Node     10. Node depth   6. Best Bound -142019.000000.
Node 10: Not applying heuristic (status is Cutoff in dual)
--- Global Log. Node     11. Node depth   2. Best Bound -142019.000000.
Node 11: LP-obj -141465;  Heuristic value -139508
--- Global Log. Node     12. Node depth   3. Best Bound -142019.000000.
Node 12: LP-obj -141062;  Heuristic value -139933
--- Global Log. Node     13. Node depth   3. Best Bound -142019.000000.
Node 13: Not applying heuristic (status is Infeasible)
--- Global Log. Node     14. Node depth   3. Best Bound -142019.000000.
Node 14: Not applying heuristic (status is Cutoff in dual)
--- Global Log. Node     15. Node depth   3. Best Bound -141896.953125.
Node 15: LP-obj -141721;  Heuristic value -141278 *** Updated cutoff to -141277
--- Global Log. Node     16. Node depth   4. Best Bound -141896.953125.
Node 16: LP-obj -141694;  Heuristic value -141168
--- Global Log. Node     17. Node depth   5. Best Bound -141896.953125.
Node 17: LP-obj -141640;  Heuristic value -141168
--- Global Log. Node     18. Node depth   6. Best Bound -141896.953125.
Node 18: LP-obj -141572;  Heuristic value -141278 *** Updated cutoff to -141277
--- Global Log. Node     19. Node depth   7. Best Bound -141896.953125.
Node 19: LP-obj -141360;  Heuristic value -141258
--- Global Log. Node     20. Node depth   7. Best Bound -141896.953125.
Node 20: LP-obj -141565;  Heuristic value -141278 *** Updated cutoff to -141277
--- Global Log. Node     21. Node depth   8. Best Bound -141896.953125.
Node 21: LP-obj -141349;  Heuristic value -141247
--- Global Log. Node     22. Node depth   8. Best Bound -141896.953125.
Node 22: LP-obj -141498;  Heuristic value -141278 *** Updated cutoff to -141277
--- Global Log. Node     23. Node depth   8. Best Bound -141896.953125.
Node 23: Not applying heuristic (status is Infeasible)
--- Global Log. Node     24. Node depth   8. Best Bound -141896.953125. Best MIP f(x) -141278.000000
Node 24: B&B integer solution found; objval -141278
--- Global Log. Node     25. Node depth   8. Best Bound -141726.000000. Best MIP f(x) -141278.000000
Node 25: B&B integer solution found; objval -141056
--- Global Log. Node     26. Node depth   4. Best Bound -141720.515625. Best MIP f(x) -141278.000000
Node 26: B&B integer solution found; objval -140695
--- Global Log. Node     27. Node depth   3. Best Bound -141693.593750. Best MIP f(x) -141278.000000
Node 27: B&B integer solution found; objval -141524
--- Global Log. Node     28. Node depth   4. Best Bound -141640.000000. Best MIP f(x) -141278.000000
Node 28: B&B integer solution found; objval -140974
--- Global Log. Node     29. Node depth   3. Best Bound -141465.140625. Best MIP f(x) -141278.000000
Node 29: LP-obj -141341;  Heuristic value -139398
--- Global Log. Node     30. Node depth   3. Best Bound -141465.140625. Best MIP f(x) -141278.000000
Node 30: Not applying heuristic (status is Cutoff in dual)
--- Global Log. Node     31. Node depth   3. Best Bound -141465.140625. Best MIP f(x) -141278.000000
Node 31: Not applying heuristic (status is Infeasible)
--- Global Log. Node     32. Node depth   3. Best Bound -141360.000000. Best MIP f(x) -141278.000000
Node 32: Not applying heuristic (status is Cutoff in dual)
--- Global Log. Node     33. Node depth   7. Best Bound -141360.000000. Best MIP f(x) -141278.000000
Node 33: Not applying heuristic (status is Infeasible)
--- Global Log. Node     34. Node depth   7. Best Bound -141349.000000. Best MIP f(x) -141278.000000
Node 34: Not applying heuristic (status is Cutoff in dual)
--- Global Log. Node     35. Node depth   8. Best Bound -141349.000000. Best MIP f(x) -141278.000000
Node 35: Not applying heuristic (status is Infeasible)

===== * * * =============================================== * * *
TOMLAB SOL - Three weeks demonstration single user license
=================================================================
Problem: mip_prob -  7: Weingartner 1 - 2/28 0-1 knapsack  f_k -141278.000000000000000000
                                              User given f(x_*)-141278.000000000000000000

Solver: Xpress-MP.  EXIT=0.  INFORM=6.
Mex-interface to Xpress-MP LP/QP/MIP/MIQP solver
Global search complete - integer solution found

FuncEv   35 GradEv    0 Iter   35
CPU time: 3.156000 sec. Elapsed time: 3.156000 sec.

The following example shows how to define and solve a problem using the TOMLAB Format (TQ). The matrices and vectors for the problem is defined in a mat file. Fields that changes the Xpress^MP control variables are set to show how to influence the work of the solver. In this case the changes slow down its performance.

clear all
load bilp1.mat
whos
  Name          Size         Bytes  Class

  A            27x1956      422496  double array
  b_L          27x1            216  double array
  b_U          27x1            216  double array
  c          1956x1          15648  double array
  noivars    1956x1                15648  double
  x_L        1956x1          15648  double array
  x_U        1956x1          15648  double array

Grand total is 58735 elements using 469880 bytes

Prob = mipAssign(c, A, b_L, b_U, x_L, x_U,[],'bilp1',[],[],noivars);
Result = tomRun('xpress-mp',Prob,1);

===== * * * =============================================== * * *
TOMLAB SOL - Three weeks demonstration single user license
=================================================================
Problem: No Init File    -  1: bilp1            f_k       0.000000000000000000
                                       sum(|constr|)      0.000000000000025960

Solver: Xpress-MP.  EXIT=0.  INFORM=6.
Mex-interface to Xpress-MP LP/QP/MIP/MIQP solver
Global search complete - integer solution found

FuncEv   67 GradEv    0 Iter   67
CPU time: 4.359000 sec. Elapsed time: 4.375000 sec.

=== * * * ================================================== * * *

Prob.MIP
ans =
      IntVars: 1956
    VarWeight: []
     KNAPSACK: []
          fIP: []
          xIP: []
           PI: []
           SC: []
           SI: []
         sos1: []
         sos2: []

% Make Xpress-MP work slower by disabling presolve and cuts.
Prob.MIP.xpcontrol.CUTSTRATEGY = 0;
Prob.MIP.xpcontrol.MIPPRESOLVE = 0;
Prob.MIP.xpcontrol.PRESOLVE = 0;
Result = tomRun('xpress-mp',Prob,2);

===== * * * =============================================== * * *
TOMLAB SOL - Three weeks demonstration single user license
=================================================================
Problem: No Init File    -  1: bilp1            f_k       0.000000000000000000
                                       sum(|constr|)      0.000000000000020365

Solver: Xpress-MP.  EXIT=0.  INFORM=6.
Mex-interface to Xpress-MP LP/QP/MIP/MIQP solver
Global search complete - integer solution found

FuncEv  105 GradEv    0 Iter  105
CPU time: 0.578000 sec. Elapsed time: 0.578000 sec.

=== * * * ================================================== * * *

Prob.MIP.xpcontrol.MIPPRESOLVE = 7; % Try another MIPPRESOLVE value
Result = tomRun('xpress-mp', Prob, 1);

===== * * * =============================================== * * *
TOMLAB SOL - Three weeks demonstration single user license
=================================================================
Problem: No Init File    -  1: bilp1            f_k       0.000000000000000000
                                       sum(|constr|)      0.000000000000011373

Solver: Xpress-MP.  EXIT=0.  INFORM=6.
Mex-interface to Xpress-MP LP/QP/MIP/MIQP solver
Global search complete - integer solution found

FuncEv   82 GradEv    0 Iter   82
CPU time: 3.250000 sec. Elapsed time: 3.250000 sec.

« Previous « Start » Next »