The Network Solver
- Overview
- Getting Started
-
Syntax
-
DetailsInput Data for the Network SolverSolving over Subsets of Nodes and Links (Filters)Numeric LimitationsBiconnected Components and Articulation PointsCliqueConnected ComponentsCycleLinear Assignment (Matching)Minimum-Cost Network FlowMinimum CutMinimum Spanning TreeShortest PathTransitive ClosureTraveling Salesman ProblemMacro Variable _OROPTMODEL_
-
ExamplesArticulation Points in a Terrorist NetworkCycle Detection for Kidney Donor ExchangeLinear Assignment Problem for Minimizing Swim TimesLinear Assignment Problem, Sparse Format versus Dense FormatMinimum Spanning Tree for Computer Network TopologyTransitive Closure for Identification of Circular Dependencies in a Bug Tracking SystemTraveling Salesman Tour through US Capital Cities
- References
PROC OPTMODEL always creates and initializes a SAS macro variable called _OROPTMODEL_, which contains a character string.
After each PROC OPTMODEL run, you can examine this macro variable by specifying %put &_OROPTMODEL_; and check the execution of the most recently invoked solver from the value of the macro variable.
Each keyword and value pair in _OROPTMODEL_ also appears in two other places: the PROC OPTMODEL automatic arrays _OROPTMODEL_NUM_ and _OROPTMODEL_STR_ ; and the ODS tables ProblemSummary and SolutionSummary, which appear after a SOLVE statement, unless you set the PRINTLEVEL= option to NONE. You can use these variables to obtain details about the solution even if you do not specify an output destination in the OUT= option.
After the solver is called, the various keywords in the variable are interpreted as follows:
- STATUS
-
indicates the solver status at termination. It can take one of the following values:
- OK
-
The solver terminated normally.
- SYNTAX_ERROR
-
The use of syntax is incorrect.
- DATA_ERROR
-
The input data is inconsistent.
- OUT_OF_MEMORY
-
Insufficient memory was allocated to the procedure.
- IO_ERROR
-
A problem in reading or writing of data has occurred.
- SEMANTIC_ERROR
-
An evaluation error, such as an invalid operand type, has occurred.
- ERROR
-
The status cannot be classified into any of the preceding categories.
- SOLUTION_STATUS
-
indicates the solution status at termination. It can take one of the following values:
- ABORT_NOSOL
-
The solver was stopped by the user and did not find a solution.
- ABORT_SOL
-
The solver was stopped by the user but still found a solution.
- BAD_PROBLEM_TYPE
-
The problem type is not supported by the solver.
- CONDITIONAL_OPTIMAL
-
The optimality of the solution cannot be proven.
- ERROR
-
The algorithm encountered an error.
- FAIL_NOSOL
-
The solver stopped due to errors and did not find a solution.
- FAIL_SOL
-
The solver stopped due to errors but still found a solution.
- FAILED
-
The solver failed to converge, possibly due to numerical issues.
- HEURISTIC_NOSOL
-
The solver used only heuristics and did not find a solution.
- HEURISTIC_SOL
-
The solver used only heuristics and found a solution.
- INFEASIBLE
-
The problem is infeasible.
- INFEASIBLE_OR_UNBOUNDED
-
The problem is infeasible or unbounded.
- INTERRUPTED
-
The solver was interrupted by the system or the user before completing its work.
- ITERATION_LIMIT_REACHED
-
The solver reached the maximum number of iterations that is specified in the MAXITER= option.
- NODE_LIM_NOSOL
-
The solver reached the maximum number of nodes specified in the MAXNODES= option and did not find a solution.
- NODE_LIM_SOL
-
The solver reached the maximum number of nodes specified in the MAXNODES= option and found a solution.
- NULL_GRAPH
-
The graph was null (it had 0 nodes) after PROC OPTMODEL processed the SUBGRAPH= option.
- OK
-
The algorithm terminated normally.
- OPTIMAL
-
The solution is optimal.
- OPTIMAL_AGAP
-
The solution is optimal within the absolute gap that is specified in the ABSOBJGAP= option.
- OPTIMAL_COND
-
The solution is optimal, but some infeasibilities (primal, bound, or integer) exceed tolerances because of scaling.
- OPTIMAL_RGAP
-
The solution is optimal within the relative gap that is specified in the RELOBJGAP= option.
- OUTMEM_NOSOL
-
The solver ran out of memory and either did not find a solution or failed to output the solution due to insufficient memory.
- OUTMEM_SOL
-
The solver ran out of memory but still found a solution.
- SOLUTION_LIM
-
The solver reached the maximum number of solutions specified in the MAXCLIQUES=, MAXCYCLES=, or MAXSOLS= option.
- TARGET
-
The solution is not worse than the target that is specified in the TARGET= option.
- TIME_LIM_NOSOL
-
The solver reached the execution time limit specified in the MAXTIME= option and did not find a solution.
- TIME_LIM_SOL
-
The solver reached the execution time limit specified in the MAXTIME= option and found a solution.
- TIME_LIMIT_REACHED
-
The solver reached its execution time limit.
- UNBOUNDED
-
The problem is unbounded.
- PROBLEM_TYPE
-
indicates the type of problem solved. It can take one of the following values:
- BICONCOMP
- CLIQUE
- CONCOMP
- CYCLE
- LAP
- MCF
- MINCUT
- MST
- SHORTPATH
- TRANSCL
- TSP
- NONE
-
This value is used when you do not specify an algorithm to run.
- OBJECTIVE
-
indicates the objective value that is obtained by the solver at termination. For problem classes that do not have an explicit objective, such as cycle, the value of this keyword within the _OROPTMODEL_ macro variable is missing (.).
- RELATIVE_GAP
-
indicates the relative gap between the best integer objective (BestInteger) and the best bound on the objective function value (BestBound) upon termination of the MILP solver. The relative gap is equal to
![\[ \mid \mbox{BestInteger} - \mbox{BestBound}\mid / \left(\mbox{1E--10}~ + \mid \mbox{BestBound}\mid \right) \]](images/ormpug_networksolver0010.png)
- ABSOLUTE_GAP
-
indicates the absolute gap between the best integer objective (BestInteger) and the best bound on the objective function value (BestBound) upon termination of the MILP solver. The absolute gap is equal to
.
- PRIMAL_INFEASIBILITY
-
indicates the maximum (absolute) violation of the primal constraints by the solution.
- BOUND_INFEASIBILITY
-
indicates the maximum (absolute) violation by the solution of the lower or upper bounds (or both).
- INTEGER_INFEASIBILITY
-
indicates the maximum (absolute) violation of the integrality of integer variables returned by the MILP solver.
- BEST_BOUND
-
indicates the best bound on the objective function value at termination. A missing value indicates that the MILP solver was not able to obtain such a bound.
- NODES
-
indicates the number of nodes enumerated by the MILP solver by using the branch-and-bound algorithm.
- ITERATIONS
-
indicates the number of simplex iterations taken to solve the problem.
- PRESOLVE_TIME
-
indicates the time (in seconds) used in preprocessing.
- SOLUTION_TIME
-
indicates the time (in seconds) taken to solve the problem, including preprocessing time.
Note: The time reported in PRESOLVE_TIME and SOLUTION_TIME is either CPU time or real time. The type is determined by the TIMETYPE= option.
When SOLUTION_STATUS has a value of OPTIMAL, CONDITIONAL_OPTIMAL, ITERATION_LIMIT_REACHED, or TIME_LIMIT_REACHED, all terms of the _OROPTMODEL_ macro variable are present; for other values of SOLUTION_STATUS, some terms do not appear.
The following keywords within the _OROPTMODEL_ macro variable appear only with certain algorithms. The keywords convey information about the number of solutions each algorithm found: