Progress Reports: Interpreting the Node Log
PREVIOUS
NEXT
| ILOG CPLEX 11.0 User's Manual > Discrete Optimization > Solving Mixed Integer Programming Problems (MIP) > Progress Reports: Interpreting the Node Log |
Progress Reports: Interpreting the Node Log |
INDEX
PREVIOUS
NEXT
|
As explained earlier, when ILOG CPLEX optimizes mixed integer programs, it builds a tree with the linear relaxation of the original MIP at the root and subproblems to optimize at the nodes of the tree. ILOG CPLEX reports its progress in optimizing the original problem in a node log file as it traverses this tree.
You control how information in the log file is recorded and displayed, through two ILOG CPLEX parameters. The MIPDisplay parameter controls the general nature of the output that goes to the node log. Table 14.13 summarizes its possible values and their effects.
The MIPInterval parameter controls how frequently node log lines are printed. Its default is 100 and can be set to any positive integer value. A line is recorded in the node log for every node with an integer solution if the MIPDisplay parameter is set to 1 (one) or higher, and also for any node whose number is a multiple of the MIPInterval value if the MIPDisplay is set to 2 or higher.
Here is an example of a log file from the Interactive Optimizer, where the MIPInterval parameter has been set to 10:
In that example, ILOG CPLEX found the optimal objective function value of 5.0 after exploring 13 nodes and performing 41 (dual simplex) iterations, and ILOG CPLEX found an optimal integer solution at node 4. The MIP interval parameter was set at 10, so every tenth node was logged, in addition to the node where an integer solution was found.
As you can see in that example, ILOG CPLEX logs an asterisk (*) in the left-most column for any node where it finds an integer-feasible solution or new incumbent. In the next column, it logs the node number. It next logs the number of nodes left to explore.
In the next column, Objective, ILOG CPLEX either records the objective value at the node or a reason to fathom the node. (A node is fathomed if the solution of a subproblem at the node is infeasible; or if the value of objective function at the node is worse than the cutoff value for branch & cut; or if the node supplies an integer solution.) This column is left blank for lines where the first column contains an asterisk (*) indicating a node where ILOG CPLEX found an integer-feasible solution or new incumbent.
In the column labeled IInf, ILOG CPLEX records the number of integer-infeasible variables and special ordered sets. If no solution has been found, the column titled Best Integer is blank; otherwise, it records the best integer solution found so far.
The column labeled Cuts/Best Node records the best objective function value achievable. If the word Cuts appears in this column, it means various cuts were generated; if a particular name of a cut appears, then only that kind of cut was generated.
The column labeled ItCnt records the cumulative iteration count of the algorithm solving the subproblems. Until a solution has been found, the column labeled Gap is blank. If a solution has been found, the relative gap value is printed: when it is less than 999.99, the value is printed; otherwise, hyphens are printed. The gap is computed as:
(best integer - best node ) * objsen / (abs (best integer) + 1e-10)
Consequently, the printed gap value may not always move smoothly. In particular, there may be sharp improvements whenever a new best integer solution is found. Moreover, if the populate procedure is invoked, the printed gap value may become negative after the optimal solution has been found and proven optimal.
ILOG CPLEX also logs its addition of cuts to a model. Here is an example of a node log file from a problem where ILOG CPLEX added several cover cuts.
ILOG CPLEX also logs the number of clique inequalities in the clique table at the beginning of optimization. Cuts generated at intermediate nodes are not logged individually unless they happen to be generated at a node logged for other reasons. ILOG CPLEX logs the number of applied cuts of all classes at the end.
ILOG CPLEX also indicates, in the node log file, each instance of a successful application of the node heuristic. The following example shows a node log file for a problem where the heuristic found a solution at node 0. The + denotes an incumbent generated by the heuristic.
Periodically, if the MIP display parameter is 2 or greater, ILOG CPLEX records the cumulative time spent since the beginning of the current MIP optimization and the amount of memory used by branch & cut. (Periodically means that time and memory information appear either every 20 nodes or ten times the MIP display parameter, whichever is greater.)
The Interactive Optimizer prints an additional summary line in the log if optimization stops before it is complete. This summary line shows the best MIP bound, that is, the best objective value among all the remaining node subproblems. The following example shows you lines from a node log file where an integer solution has not yet been found, and the best remaining objective value is 2973.9912281.
MIP-Node limit, no integer solution. Current MIP best bound = 2.9739912281e+03 (gap is infinite) Solution time = 0.01 sec. Iterations = 68 Nodes = 7 (7) |
Stating a MIP Problem presents a typical MIP problem. Here is the node log file for that problem with the default setting of the MIP display parameter:
These additional items appear only in the node log file (not on screen) in conventional branch & cut:
Variable records the name of the variable where ILOG CPLEX branched to create this node. If the branch was due to a special ordered set, the name listed here will be the right-most variable in the left subset.
B indicates the branching direction:
D means the variables was restricted to a lower value;
U means the variable was restricted to a higher value;
L means the left subset of the special ordered set was restricted to 0 (zero);
R means the right subset of the special ordered set was restricted to 0 (zero);
A means that constraints were added or more than one variable was restricted;
N means that cuts added to the node LP resulted in an integer feasible solution; no branching was required;
NodeID specifies the node identifier.
Parent specifies the NodeID of the parent.
Depth indicates the depth of this node in the branch & cut tree.
Those additional items are not applicable in dynamic search.
| Copyright © 1987-2007 ILOG S.A. All rights reserved. Legal terms. | PREVIOUS NEXT |