The Linear Programming Solver
- Overview
- Getting Started
-
Syntax
-
DetailsPresolvePricing Strategies for the Primal and Dual Simplex SolversThe Network Simplex AlgorithmThe Interior Point AlgorithmIteration Log for the Primal and Dual Simplex SolversIteration Log for the Network Simplex SolverIteration Log for the Interior Point SolverIteration Log for the Crossover AlgorithmConcurrent LPProblem StatisticsVariable and Constraint StatusIrreducible Infeasible SetMacro Variable _OROPTMODEL_
-
ExamplesDiet ProblemReoptimizing the Diet Problem Using BASIS=WARMSTARTTwo-Person Zero-Sum GameFinding an Irreducible Infeasible SetUsing the Network Simplex SolverMigration to OPTMODEL: Generalized NetworksMigration to OPTMODEL: Maximum FlowMigration to OPTMODEL: Production, Inventory, DistributionMigration to OPTMODEL: Shortest Path
- References
The primal and dual simplex solvers implement a two-phase simplex algorithm. Phase I finds a feasible solution, which phase II improves to an optimal solution.
When the LOGFREQ= option has a value of 1, the following information is printed in the iteration log:
- Algorithm
-
indicates which simplex method is running by printing the letter P (primal) or D (dual).
- Phase
-
indicates whether the solver is in phase I or phase II of the simplex method.
- Iteration
-
indicates the iteration number.
- Objective Value
-
indicates the current amount of infeasibility in phase I and the primal objective value of the current solution in phase II.
- Time
-
indicates the time elapsed (in seconds).
- Entering Variable
-
indicates the entering pivot variable. A slack variable that enters the basis is indicated by the corresponding row name followed by “(S)”. If the entering nonbasic variable has distinct, finite lower and upper bounds, then a “bound swap” can take place in the primal simplex method.
- Leaving Variable
-
indicates the leaving pivot variable. A slack variable that leaves the basis is indicated by the corresponding row name followed by “(S)”. The leaving variable is the same as the entering variable if a bound swap has taken place.
When you omit the LOGFREQ= option or specify a value larger than 1, only the algorithm, phase, iteration, objective value, and time information is printed in the iteration log.
The behavior of objective values in the iteration log depends on both the current phase and the chosen solver. In phase I, both simplex methods have artificial objective values that decrease to 0 when a feasible solution is found. For the dual simplex method, phase II maintains a dual feasible solution, so a minimization problem has increasing objective values in the iteration log. For the primal simplex method, phase II maintains a primal feasible solution, so a minimization problem has decreasing objective values in the iteration log.
During the solution process, some elements of the LP model might be perturbed to improve performance. In this case the objective values that are printed correspond to the perturbed problem. After reaching optimality for the perturbed problem, the LP solver solves the original problem by switching from the primal simplex method to the dual simplex method (or from the dual simplex method to the primal simplex method). Because the problem might be perturbed again, this process can result in several changes between the two algorithms.