Solver Subroutines

EKKBSLV - Solve a LP Problem Using an Interior-Point Method
EKKGEMV - Compute a Matrix Vector Product
EKKGES - Solve a Basic System of Equations
EKKINVT - Compute Primal and Dual Solutions Corresponding to a Given Basis
EKKLPDC - Perform Specialized Decomposition
EKKMPRE - Preprocess the MIP Branch-and-Bound Tree
EKKMSLV - Solve a Mixed-Integer Programming Problem
EKKNSLV - Solve a Network Flow Problem
EKKQSLV - Solve a Quadratic Programming Problem
EKKSSLV - Solve a LP Problem Using the Simplex Method

[ Top of Page | Bottom of Page | Index to Modules ]

EKKSSLV - Solve a Linear Programming Problem Using the Simplex Method

This subroutine solves a linear program using the simplex method. Refer to "Simplex (EKKSSLV)" for additional information on the simplex algorithm implemented in the Optimization Library.

Syntax

FORTRAN	CALL EKKSSLV(rtcod,dspace,alg,init)
PL/I	CALL EKKSSLV(rtcod,dspace,alg,init);
C	ekksslv(&rtcod,dspace,alg,init);

On Entry

dspace: is the user-provided work area.

Specified as: a one-dimensional real array of doublewords.

alg: is the algorithm to be used, where:

If alg=0,

an algorithm is chosen based on the

characteristics of your particular problem.
If alg=1,

the primal algorithm is used.
If alg=2,

the dual algorithm is used with Devex pricing.

Specified as: a fullword integer. Its value must be 0, 1, or 2.

init: is the type of procedure to be used, where:

If init=0,

processing continues using the basis in dspace and the

resulting pricing strategy from the last call to EKKSSLV.

(This may be desired if, for example, a previous call

to EKKSSLV has not resulted in an optimal solution.)

If init=1, Devex pricing is used.
If init=2, random pricing is used first for "fast" iterations, then Devex

pricing is used.
If init=3,

values from a previous step in the solution process are used

to start the simplex algorithm. (For example, this can be

used if you are calling EKKSSLV for the second time.)

See note 8.

Specified as: a fullword integer. Its value must be 0, 1, 2, or 3.

Note:

If alg=2, init cannot be set to 2 or 3.

On Return

rtcod: is the return code for the subroutine, where:

If rtcod = 0,

the subroutine completed successfully. Only informational

messages were issued.
If rtcod = rc,

rc is the return code associated with the first occurrence of

the highest severity message.

See "Return Codes" for an explanation of

return codes.

If rtcod = 0,

the subroutine completed successfully. Only

informational messages were issued.

If rtcod = rc,

rc is the return code associated with the first

occurrence of the highest severity message.

Returned as: a fullword integer.

dspace: is the user-provided work area.

Returned as: a one-dimensional real array of doublewords.

Notes

The default LP problem is assumed to be a minimization problem. You can set the real control variable Rmaxmin to -1.0 to solve your problem as a maximization problem.
In general, the following call is appropriate for the first time EKKSSLV is called for a model:

CALL EKKSSLV(RTCOD,DSPACE,1,2)

After a call to EKKPSSL, the solution will be primal and dual feasible, but there may not be an optimal basis. To get an optimal basis, the following call should be made:

 CALL EKKSSLV(RTCOD,DSPACE,1,3)

If EKKSSLV has indicated your model is infeasible, but the sum of the infeasibilities is small, try solving your model both with and without EKKPRSL. Models with numerical stability problems may yield different results with and without EKKPRSL. Your model may be infeasible after preprocessing with EKKPRSL, while it may be feasible without such preprocessing,or vice versa.

For example, if one of your constraints has the form x = 10000.0 * y + 1.0, EKKPRSL may eliminate x from the problem. If this is done, x must exactly equal 10000.0 * y + 1.0 (that is, x must be greater than or equal to 1.0 because y is greater than or equal to 0). Otherwise, EKKSSLV indicates that your model is infeasible. However, if EKKPRSL is not called, x will not be removed from the problem, and a solution such as y = -10 ^-8 , x = 0.9999 would be valid within tolerances.

If Rslambda is not set to 0.0, EKKSSLV will add Rslambda times the existing parametric adjustment vectors. EKKSSLV will attempt to find an optimum corresponding to the value of Rslambda.
You can take control after every iteration of the simplex routine with the user exit subroutine EKKITRU. See "Understanding Informational User Exit Subroutines" for more information.
For the majority of EKKSSLV problems, setting the integer control variable Idevexmode=1 (the default) or -2 gives the best results for the primal case, while setting Idevexmode=3 or -3 gives the best results for the dual case.
Regardless of the values of alg and init, EKKSSLV uses the row and column status regions to determine a starting basis, and to identify non-basic rows and columns. If init=3, an advanced basis is determined from the existing primal solution vector, as well as the row and column status vectors, and the row activities. There is no provision for using dual solution values in selecting an advanced starting basis.
Since EKKSSLV always uses the row and column status regions to determine a starting basis, and to identify non-basic rows and columns, there is no provision for a cold start as such. A call to EKKINIT will initialize the status regions so that slack variables are marked as basic, and structural variables are marked as non-basic or free. Thus, calling EKKINIT before EKKSSLV will, in effect, force a cold start.
If EKKSSLV runs out of main memory while working on an LP problem as a part of the solution of a MIP problem, then it will assign a value of 11 to the integer control variable Iprobstat. Obviously this can only happen when EKKSSLV has been called from within EKKMSLV. This may be a source of message number 7030, "OSL data was overwritten." The value of the control variable Iprobstat can be inspected while EKKMSLV is running by using the MIP user exit subroutine EKKEVNU, which is called from within EKKMSLV.

Examples

Refer to the following sample programs for examples of using EKKSSLV:

EKKBSLV - Solve a Linear Programming Problem Using an Interior-Point Method

This subroutine solves a linear programming problem using an interior-point method. Refer to "Interior-Point Barrier for additional information on the regularized interior-point algorithm.

Syntax

FORTRAN	CALL EKKBSLV(rtcod,dspace,alg,sslvswch)
PL/I	CALL EKKBSLV(rtcod,dspace,alg,sslvswch);
C	ekkbslv(&rtcod,dspace,alg,sslvswch);

On Entry

dspace: is the user-provided work area.

Specified as: a one-dimensional real array of doublewords.

alg: specifies the type of algorithm to be used, where:

If alg = 0, 1, 2, or 3,

the primal-dual barrier algorithm with a predictor-corrector

method is used.

If alg = -1,

the primal-dual barrier algorithm is applied to a regularized version of the problem.

Specified as: a fullword integer. Its value must be -1, 0, 1, 2, or 3.

sslvswch: is the control used to switch to the simplex method (to obtain a basic solution), where:

If sslvswch=0,

EKKBSLV never switches to the simplex method.
If sslvswch=1,

EKKBSLV switches to the simplex method if

numerical instabilities arise.
If sslvswch=2,

EKKBSLV always switches to the simplex method

when it completes, or if numerical instabilities

arise.
If sslvswch=3,

EKKBSLV switches to the simplex method

immediately if it is appropriate after

analyzing the matrix, at completion, or

if numerical instabilities arise.
If sslvswch=4,

EKKBSLV immediately creates a basis for the simplex method

and then switches to the simplex method. This is intended for

use after a previous call to EKKBSLV with sslvswch=0.

When sslvswch=4, the value of alg is ignored.

Specified as: a fullword integer. Its value must be 0, 1, 2, 3, or 4.

On Return

rtcod: is the return code for the subroutine, where:

If rtcod = 0,

the subroutine completed successfully. Only informational

messages were issued.
If rtcod = rc,

rc is the return code associated with the first occurrence of

the highest severity message.

See "Return Codes" for an explanation of

return codes.

If rtcod = 0,

the subroutine completed successfully. Only

informational messages were issued.

If rtcod = rc,

rc is the return code associated with the first

occurrence of the highest severity message.

Returned as: a fullword integer.

dspace: is the user-provided work area.

Returned as: a one-dimensional real array of doublewords.

Notes

It is recommended that you do not call EKKCRSH before calling EKKBSLV, since EKKBSLV does not start from an initial basic solution.
If you choose to switch over to the simplex algorithm, EKKSSLV is called with the following calling sequence:

CALL EKKSSLV (IRTCOD, DSPACE, 1, 2).

For most LP problems, you should first call EKKPRSL, and then call EKKBSLV with alg=0 and sslvswch=0. If you need only the optimal solution and optimal objective value, the call to EKKBSLV may be followed by a call to EKKPSSL. This will yield optimal, complementary, primal and dual solutions to the problem. If you need a basic feasible solution to the problem for input to EKKSENS, EKKMSLV or for another purpose, the call to EKKBSLV should have sslvswch<0. Since EKKPSSL does not do any refactorization or optimization, the call to EKKPSSL may need to be followed by a call to EKKSSLV to get an optimal basis.
The current copy of the matrix must be stored by columns or stored in vector block format. See EKKNWMT for information on vector block format.
By default, LP, QP, and MIP problems are considered to be minimization problems. To solve your problem as a maximization problem, you can set the real control variable Rmaxmin to -1.0
The obsolete primal barrier algorithm (alg=1 option) and primal-dual barrier algorithm without predictor-corrector (alg=2 option) are no longer supported. However, for backward compatibility, integer values of 0, 1, and 2 for the alg parameter will be accepted, but now these will result in invocation of the more efficient primal-dual barrier with predictor-corrector algorithm.
If Rslambda is not set to 0.0, EKKBSLV will add Rslambda times the existing parametric adjustment vectors. EKKBSLV will attempt to find an optimum corresponding to the value of Rslambda.
It is strongly recommended that if an LP is known to have dense columns, or to be close to primal or dual infeasibilty, that the "regularized" LP option (alg=-1) be used. To take advantage of the dense column handling ability, the integer parameter Idensecol must be lowered from its large default value to a value which will select out the dense columns in this particular model.

Example

Refer to "Sample FORTRAN Program EXBSLV" for an example of using EKKBSLV.

EKKLPDC - Perform Specialized Decomposition

This subroutine allows you to take advantage of specialized structures that exist in certain LP problems. EKKLPDC attempts to decompose the problem to either a staircase or a Dantzig-Wolfe structure, then solves the pieces of the decomposed problem and puts them back together again. If one of these special structures exists in a problem, you can achieve a significant improvement in performance by using EKKLPDC. If you use EKKLPDC, make sure it is called before EKKSSLV.

See "Linear Programming Decomposition (EKKLPDC)" for more information on how to use EKKLPDC.

Syntax

FORTRAN	CALL EKKLPDC(rtcod,dspace,type,strategy,nblocks)
PL/I	CALL EKKLPDC(rtcod,dspace,type,strategy,nblocks);
C	ekklpdc(&rtcod,dspace,type,strategy,nblocks);

On Entry

dspace: is the user-provided work area.

Specified as: a one-dimensional real array of doublewords.

type: is the type of structure or decomposition, where:

If type=1,

EKKLPDC looks for a staircase structure.
If type=2,

EKKLPDC does one pass of a Dantzig-Wolfe decomposition.
If type=3,

EKKLPDC performs a full Dantzig-Wolfe decomposition.
Specified as: a fullword integer.

strategy: is an indicator of the approach taken to solving the problem, where strategy depends on the value you specify for type.

For a staircase structure problem (type=1):

If strategy=0,: EKKLPDC checks to see whether the problem can be decomposed to a staircase structure. If it can, EKKLPDC marks the rows and columns and exits. If it cannot, it issues a message.
If strategy=1,: each subproblem is solved with the neighboring coupling columns free.
If strategy=2,: each subproblem is solved with the columns coupling it to the previous subproblem free, and the columns coupling it to the next subproblem fixed at lower bound.
If strategy=3,: EKKLPDC builds up the size of the (triangular) sub-problem.

For one pass of Dantzig-Wolfe decomposition (type=2):

If strategy=0,: EKKLPDC checks to see whether the problem can be decomposed to a Dantzig-Wolfe structure. If it can, EKKLPDC marks the rows and columns and exits. If it cannot, it issues a message.
If strategy=1,: EKKLPDC solves each decomposed subproblem independently, and forms dual feasible bases to the original problem. You would normally then solve the problem using EKKSSLV with the dual algorithm option.
If strategy=2,: EKKLPDC partitions the right-hand side for each subproblem.
If strategy=3,: EKKLPDC takes an approach similar to that used when strategy=2, except that it puts every second block together until no blocks remain to be added to the problem.

For multiple passes of Dantzig-Wolfe decomposition (type=3):

If strategy=0,: EKKLPDC checks to see whether the problem can be decomposed to a Dantzig-Wolfe structure. If it can, EKKLPDC marks the rows and columns and exits. If it cannot, it issues a message.
If strategy=1,: EKKLPDC performs full Dantzig-Wolfe decomposition; the master rows are ignored for the initial solution.
If strategy=2,: EKKLPDC partitions the RHS of the master problem and gives some portion of it to each subproblem.
If strategy=3,: EKKLPDC does full Dantzig-Wolfe decomposition, using the current solution in dspace as an initial solution. The current solution may be created by EKKSSLV, EKKNSLV, or EKKBSLV.

Specified as: a fullword integer.

nblocks: is the number of blocks used to define the model, where:

If nblocks<0,

the user has placed block numbers in the row status region.
If nblocks=0,

EKKLPDC determines the number of blocks.
If nblocks0,

EKKLPDC tries to use the number of blocks specified.

Specified as: a fullword integer.

On Return

rtcod: is the return code for the subroutine, where:

If rtcod = 0,

the subroutine completed successfully. Only informational

messages were issued.
If rtcod = rc,

rc is the return code associated with the first occurrence of

the highest severity message.

See "Return Codes" for an explanation of

return codes.

If rtcod = 0,

the subroutine completed successfully. Only

informational messages were issued.

If rtcod = rc,

rc is the return code associated with the first

occurrence of the highest severity message.

Returned as: a fullword integer.

dspace: is the user-provided work area.

Returned as: a one-dimensional real array of doublewords.

Notes

If the value of nblocks is nonnegative, EKKLPDC attempts to find a block structure in your problem. In some cases, the heuristic used by EKKLPDC to find structures may not find the best (most nearly uniform) distribution of rows among the blocks. Thus, it is often more efficient to set strategy=0 to do a diagnostic (no solving) run of your problem. You might run the problem once with type=1, and strategy=0 to look for a staircase structure, and once with type=2, strategy=0 to look for a Dantzig-Wolfe structure. If EKKLPDC associates most of the rows with one block, your problem may be more quickly solved with other presolve subroutines, such as EKKPRSL and EKKCRSH.
If you have information about the block numbers associated with the rows, you can load this information into the row status region and set nblocks=-1. EKKLPDC will use this data to decompose the problem more quickly. In the row status region, a value of 0 indicates a coupling row, a -1 indicates a noncoupling row that belongs to an undetermined block, and a positive integer denotes a block number for a noncoupling row. It is not necessary to assign block numbers to noncoupling rows, but it is highly desirable to identify the coupling rows.
The integer control variable Ilpdcflag can be used to set an upper limit on the number of blocks into which EKKLPDC will attempt to decompose the coefficient matrix. Setting the value of Ilpdcflag to a very large number will force EKKLPDC to make the most complete decomposition that it can. Setting the value of Ilpdcflag to zero will direct EKKLPDC to attempt to make a substantial decomposition of the coefficient matrix, but not necessarily to make the most complete decomposition that it could.
If Dantzig-Wolfe subproblems are found to have a network structure, they are solved with the network solver, EKKNSLV.
If you select the full Dantzig-Wolfe solution strategy (type=3), it is not recommended that this be used to solve your problem to optimality. The best approach is to set Imajorits so that EKKLPDC does a moderate number of iterations on the Dantzig-Wolfe decomposition, and then to use the simplex solver, EKKSSLV, to complete the solution.

Examples

Refer to the following sample programs for examples of using EKKLPDC:

EKKMSLV - Solve a Mixed-Integer Programming Problem

This subroutine solves a mixed-integer programming (MIP) problem. Refer to "Mixed-Integer Programming (EKKMPRE and EKKMSLV)" for additional information on the MIP algorithm.

Syntax

FORTRAN	CALL EKKMSLV(rtcod,dspace,type,munit,bunit)
PL/I	CALL EKKMSLV(rtcod,dspace,type,munit,bunit);
C	ekkmslv(&rtcod,dspace,type,munit,bunit);

On Entry

dspace: is the user-provided work area.

Specified as: a one-dimensional real array of doublewords.

type: is the algorithm to be used, where:

If type=1,

EKKMSLV starts processing from the beginning.
If type=2,

EKKMSLV is restarted.

Specified as: a fullword integer. Its value must be 1 or 2.

munit: is the unit number specifying where the matrix information is to be written.

Specified as: a fullword integer; 0 munit 99.

Notes:

If munit = 0, then the information is not saved in a file, but instead is placed in dspace. Performance should improve.
If you are using any variant of UNIX or any PC operating system, munit cannot be 1, 2, 5, or 6.
If you are using MVS, see "Processing Your Program" for information on the JCL needed to specify a unit.

bunit: is the unit number specifying where the basis information is to be written.

Specified as: a fullword integer; 0 bunit 99.

Notes:

If bunit = 0, then the information is not saved in a file, but instead is placed in dspace. Performance should improve.
If you are using any variant of UNIX or any PC operating system, bunit cannot be 1, 2, 5, or 6.
If you are using MVS, see "Processing Your Program" for information on the JCL needed to specify a unit.

On Return

rtcod: is the return code for the subroutine, where:

If rtcod = 0,

the subroutine completed successfully. Only informational

messages were issued.
If rtcod = rc,

rc is the return code associated with the first occurrence of

the highest severity message.

See "Return Codes" for an explanation of

return codes.

If rtcod = 0,

the subroutine completed successfully. Only

informational messages were issued.

If rtcod = rc,

rc is the return code associated with the first

occurrence of the highest severity message.

Returned as: a fullword integer.

dspace: is the user-provided work area.

Returned as: a one-dimensional real array of doublewords.

Notes

When you use EKKMSLV to solve a 0-1 MIP problem with a linear objective function, consider running EKKMPRE first; it may significantly improve performance.
For a MIP problem with a linear objective function, if EKKSSLV has not been called before EKKMSLV, then EKKMSLV will call EKKSSLV specifying the primal algorithm with Devex pricing. The relaxed subproblems are solved with EKKSSLV using the dual algorithm.
Saved information can be used to restart a problem. To do this, the basis and matrix files from the run to be restarted must be attached to bunit and munit respectively. The model from the run to be restarted should have been saved with EKKPTMD; it can now be restored with EKKGTMD.
The user exit subroutines EKKBRNU, EKKCHNU, EKKCUTU, EKKEVNU, EKKHEUU, and EKKNODU can be used to change the algorithm. For more information on these user exit subroutines, refer to "Understanding Mixed-Integer User Exit Subroutines".
Refer to the usage notes in EKKPRSL and EKKPSSL for information on their effect on EKKMSLV. See "Sample FORTRAN Program EXMPRSL" for an example of the use of EKKPRSL and EKKPSSL with EKKMSLV.
If EKKMSLV finds an optimal integer solution, all integer variables will be fixed on exit.
When using EKKMSLV to solve a modified version of a previously solved problem, the real control variable Rbbcutoff should usually be reset to a large value for minimization problems or a small value for maximization problems. This is necessary because the solution to the modified problem may be worse than that of the original problem. That is, the continuous solution may be worse than the best previous integer solution, causing EKKMSLV to stop prematurely. If you know a reasonable approximate value for an integer optimal, you can improve performance by setting Rbbcutoff close to, but still worse than the optimal.

type=2 is meant to be used when the solution of a MIP problem has been halted, the binary files have been closed and saved, and the solution of the problem is to be resumed with the same data. EKKMSLV will not perform correctly, if you modify the problem data and then attempt to start processing a modified MIP problem with type=2.
If you want to solve a mixed-integer programming problem with EKKMSLV, modify the original problem, and then solve the modified problem, do the following:

All the row and column bounds for the modified problem should be correctly reset before the solution of the problem begins. This is necessary because EKKMSLV fixes the bounds on integer variables. You can do this by saving all the bounds of the original problem before starting to solve the original problem the first time, and then restoring all these bounds before modifying the problem. This tactic ensures that you are modifying the original problem instead of a problem that has been modified by EKKMSLV in the first solution process, because the bounds after the first solution may not be the original bounds.
You should set the control variable Rbbcutoff to an appropriate initial value before the solution of the modified problem begins. Rbbcutoff is reset during processing to discard branches of the tree whose solutions are worse than this value. If the modified problem may have an optimal value that is worse than that of the original problem, reset Rbbcutoff to avoid eliminating the optimal solution. If no reasonable estimate of the objective value of the modified problem is known, se t Rbbcutoff to a large positive value to allow all feasible solutions. If the objective value of the modified problem is known to be better than some value x, set Rbbcutoff to Rmaxmin times x to improve branch-and-bound efficiency.

Which solver is called by EKKMSLV to analyze the linear or quadratic subproblems is determined by one of the (mutually exclusive) user exit subroutines EKKEVNU and EKKSLVU. The default solver is EKKSSLV, which is called from the sample version of EKKEVNU distributed with the library. To solve a MIP problem with a quadratic objective function, you must compile and link with your application program an appropriate version of EKKSLVU. See the descriptions of these user exits in "Understanding Mixed-Integer User Exit Subroutines" and "MIP User Exit Subroutines".

Examples

Refer to the following sample programs for examples of using EKKMSLV:

EKKMPRE - Preprocess the MIP Branch-and-Bound Tree to Take Advantage of Structures

Use this subroutine as a preprocessor to solve a 0-1 mixed-integer programming problem with a linear objective function. EKKMPRE makes use of several techniques to tune the problem-solving process to be used. These techniques are discussed in "Mixed-Integer Programming (EKKMPRE and EKKMSLV)".

Syntax

FORTRAN	CALL EKKMPRE(rtcod,dspace,type)
PL/I	CALL EKKMPRE(rtcod,dspace,type);
C	ekkmpre(&rtcod,dspace,type);

On Entry

dspace: is the user-provided work area.

Specified as: a one-dimensional real array of doublewords.

type: describes the type of preprocessing to be done and the way the problem matrix should be left on exit from the subroutine, where:

If type=1,

use supernodes on the branch-and-bound; on exit, keep a

copy of the new matrix with extra rows and tighter bounds.
If type=2,

do regular branch-and-bound (no supernodes); on exit, keep a

copy of the new matrix with extra rows and tighter bounds.
If type=3,

do regular branch-and-bound (no supernodes); on exit, restore

the matrix to its original form.
If type=4,

use supernodes on the branch-and-bound; on exit, overwrite

the old matrix with the new one, if possible (including new

constraint rows and tighter bounds).
If type=5,

do a regular branch-and-bound (no supernodes); on exit, overwrite

the old matrix with the new one, if possible (including

new constraint rows and tighter bounds).

Specified as: a fullword integer.

On Return

rtcod: is the return code for the subroutine, where:

If rtcod = 0,

the subroutine completed successfully. Only informational

messages were issued.
If rtcod = rc,

rc is the return code associated with the first occurrence of

the highest severity message.

See "Return Codes" for an explanation of

return codes.

If rtcod = 0,

the subroutine completed successfully. Only

informational messages were issued.

If rtcod = rc,

rc is the return code associated with the first

occurrence of the highest severity message.

Returned as: a fullword integer.

dspace: is the user-provided work area.

Returned as: a one-dimensional real array of doublewords.

Notes

EKKMPRE attempts to add additional rows. Therefore, you must allow space for extra rows if you use EKKMPRE. To do this, set the integer control variable Imaxrows after calling EKKDSCM but before calling EKKMPS, EKKLMDL, or EKKSMDL.
On some problems, particularly small ones, the time required for the extra work done by EKKMPRE may result in a longer solution time. Specifically, EKKMPRE can be thought of as having a processing time on the order of k ² to k ³, where k is the number of nonzero elements in the matrix, whereas EKKMSLV without EKKMPRE preprocessing and supernodes has a processing time on the order of 2 ⁿ, where n is the number of integer variables. If it appears that EKKMPRE will take more time than the normal branch and bound method, remove the call to EKKMPRE before the call to EKKMSLV.
After EKKMPRE has been called, the following information will be in dspace:

Links between variables (implication lists)
A list of which variables have been fixed by EKKMPRE, and sufficient information to reconstruct a valid solution to the original problem
Either your original matrix, a tighter formulation of the matrix and bounds, or both, based on the value of the type argument of EKKMPRE.

EKKMPRE may not be used as a preprocessor for a mixed-integer programming problem with a quadratic objective function.

Examples

Refer to the following sample programs for examples of using EKKMPRE:

EKKNSLV - Solve a Network Flow Problem

This subroutine solves a linear programming problem that can be written as a network flow problem.

See "Network Programming (EKKNSLV)" for more information on how to use EKKNSLV.

Syntax

FORTRAN	CALL EKKNSLV(rtcod,dspace,alg,init)
PL/I	CALL EKKNSLV(rtcod,dspace,alg,init);
C	ekknslv(&rtcod,dspace,alg,init);

On Entry

dspace: is the user-provided work area.

Specified as: a one-dimensional real array of doublewords.

alg: is the algorithm to be used, where:

If alg=1,

the primal simplex algorithm is used.
If alg=2,

the dual simplex algorithm is used. The problem must be dual

feasible on entry to this subroutine.
Specified as: a fullword integer. Its value must be 1 or 2.

init: is the type of start-up processing being done, where:

If init=1,

the current solution in dspace is used to develop an advanced

basis. The network data is loaded into network data structures,

and any previously existing network problem is overwritten.
If init=2,

the status vector in dspace is used to develop an advanced

basis. The network data is loaded into network data structures,

and any previously existing problem is overwritten.
If init=3,

an artificial starting basis is used. The network data is loaded

into network data structures, and any previously existing problem

is overwritten.
If init=4,

processing continues from the existing network basis. No

changes in data are detected.
If init=5,

processing continues from the existing network basis. Any changes

in the data for the RHS, the flow bounds, or the cost data are

detected.
If init=6,

processing continues from the existing network basis. Any

changes in the cost data are detected.

Specified as: a fullword integer. Its value must be 1, 2, 3, 4, 5, or 6.

Notes:

If alg = 2, init cannot be set to 5 or 6.
If EKKNSLV is called after a call to EKKGTMD, the EKKNSLV parameter init should have a value of 1 or 2.

On Return

rtcod: is the return code for the subroutine, where:

If rtcod = 0,

the subroutine completed successfully. Only informational

messages were issued.
If rtcod = rc,

rc is the return code associated with the first occurrence of

the highest severity message.

See "Return Codes" for an explanation of

return codes.

If rtcod = 0,

the subroutine completed successfully. Only

informational messages were issued.

If rtcod = rc,

rc is the return code associated with the first

occurrence of the highest severity message.

Returned as: a fullword integer.

dspace: is the user-provided work area.

Returned as: a one-dimensional real array of doublewords.

Notes

For network flow problems, columns represent arcs and rows represent nodes.
If the lower bound for the exogenous flow of a node is positive, that node is a supply node. If the upper bound is negative, the node is a demand node.
In general, the following call is appropriate the first time EKKNSLV is called for a model:

 CALL EKKNSLV(RTCOD, DSPACE, 1, 3)

To improve EKKNSLV performance, do not formulate transportation problems as transshipment problems, and do not make the bounds on the arc flows unnecessarily restrictive.
It is recommended that you do not run EKKPRSL, EKKPSSL, EKKSCAL, or EKKCRSH with EKKNSLV, because the processing done by these subroutines may seriously affect the integrity of the network structure.
Because network flow problems are a subset of linear programming problems, you can use any of the following to specify them: MPS format (EKKMPS), internal linear model format (EKKLMDL), internal network format (EKKNMDL), or spreadsheet format (EKKSMDL. Any additional blocks should be added using EKKDSCB or EKKRPTB.
EKKNSLV updates the vector x and the status vector before each call to EKKITRU. This allows you to reference the solution during a call to EKKITRU, but the transformation creates some overhead. Applications that do not require this information can be solved more efficiently by setting the control variable Iiterufreq to 9,999,999. This reduces the frequency with which EKKITRU is called, thus reducing the total overhead for EKKNSLV processing.
The dual algorithm requires that the costs (that is, objective function coefficients) must be nonnegative for free variables and for variables with finite lower bounds. This yields a feasible initial solution.
EKKNSLV sets the status and solution vectors in the same way as EKKSSLV. A solution from EKKNSLV is functionally equivalent to one from EKKSSLV.
The init=4 option is generally used to restart the algorithm after you have stopped EKKNSLV but made no modifications to the problem. If you have modified the bound or cost data since the last call to EKKNSLV, set init to 5 or 6 instead.

Examples

Refer to the following sample programs for examples of using EKKNSLV:

EKKQSLV - Solve a Quadratic Programming Problem

This subroutine solves a quadratic programming problem. Refer to "Quadratic Programming (EKKQSLV and EKKQPAR)" for more information on the quadratic programming algorithm.

Syntax

FORTRAN	CALL EKKQSLV(rtcod,dspace,alg,init)
PL/I	CALL EKKQSLV(rtcod,dspace,alg,init);
C	ekkqslv(&rtcod,dspace,alg,init);

On Entry

dspace: is the user-provided work area.

Specified as: a one-dimensional real array of doublewords.

alg: specifies the algorithm to be used, where:

If alg=1, the primal simplex-type algorithm is used.

If alg=-1, an interior predictor-corrrector algorithm is used to solve a regularized form of the problem.

Specified as: a fullword integer. Its value must be 1 or -1.

init: is the type of procedure to use (when alg=1 only), where:

If init=0, EKKQSLV continues processing, using the current basis.

If init=1, EKKQSLV starts processing from the beginning.

Specified as: a fullword integer, whose value must be 0 or 1. It is ignored unless the value of alg is 1.

On Return

rtcod: is the return code for the subroutine, where:

If rtcod = 0,

the subroutine completed successfully. Only informational

messages were issued.
If rtcod = rc,

rc is the return code associated with the first occurrence of

the highest severity message.

See "Return Codes" for an explanation of

return codes.

If rtcod = 0,

the subroutine completed successfully. Only

informational messages were issued.

If rtcod = rc,

rc is the return code associated with the first

occurrence of the highest severity message.

Returned as: a fullword integer.

dspace: is the user-provided work area.

Returned as: a one-dimensional real array of doublewords.

Notes

In general, the following call is appropriate:

CALL EKKQSLV(RTCOD,DSPACE,1,1)

If the quadratic matrix is not positive semidefinite, EKKQSLV issues a warning message and continues processing. However, the quadratic programming algorithm may find a local minimum instead of a global one, or it may fail altogether.
If init has been set to 0, and the current basis is not primal feasible, EKKQSLV will enter a quadratic decomposition routine.
If Rslambda is not set to 0.0, EKKQSLV will add Rslambda times the existing parametric adjustment vectors. EKKQSLV will attempt to find an optimum corresponding to the value of Rslambda.
You may want to have EKKQSLV solve your quadratic programming problem, then create a new quadratic matrix using EKKQMPS or EKKQMDL, and then proceed using the optimal basis from the first call to EKKQSLV. To do this, you must save and restore this basis by using EKKBASO and EKKBASI or by saving the status vectors and solution vectors using EKKNGET index control variables Nrowstat, Ncolstat, Nrowacts, and Ncolsol.

Examples

Refer to the following sample programs for examples of using EKKQSLV:

EKKGEMV - Compute a Matrix Vector Product

This subroutine computes ( y b y + a A x ) or ( y b y + a A^T x ). A is the current constraint matrix which has dimensions m by n, where m is the value of the integer control variable Inumrows, and n is the value of the integer control variable Inumcols.

Syntax

FORTRAN	CALL EKKGEMV(rtcod,dspace,type,alpha,x,beta,y)
PL/I	CALL EKKGEMV(rtcod,dspace,type,alpha,x,beta,y);
C	ekkgemv(&rtcod,dspace,type,alpha,x,beta,y);

On Entry

dspace: is the user-provided work area.

Specified as: a one-dimensional real array of doublewords.

type: is the type of matrix to solve, where:

If type=1,

the matrix is solved.
If type=2,

the transpose of the matrix is solved.

Specified as: a fullword integer.

alpha: is the multiplier for A or A^T

Specified as: a doubleword real.

x: is the input vector x

If type=1, then x is of length Inumcols.
If type=2, then x is of length Inumrows.

Specified as: a one-dimensional real array of doublewords.

beta: is the multiplier for y.

Specified as: a doubleword real.

y: is the input vector y.

If type=1, then y is of length Inumrows.
If type=2, then y is of length Inumcols.

Specified as: a one-dimensional real array of doublewords.

On Return

rtcod: is the return code for the subroutine, where:

If rtcod = 0,

the subroutine completed successfully. Only informational

messages were issued.
If rtcod = rc,

rc is the return code associated with the first occurrence of

the highest severity message.

See "Return Codes" for an explanation of

return codes.

If rtcod = 0,

the subroutine completed successfully. Only

informational messages were issued.

If rtcod = rc,

rc is the return code associated with the first

occurrence of the highest severity message.

Returned as: a fullword integer.

dspace: is the user-provided work area.

Returned as: a one-dimensional real array of doublewords.

y: is the output vector y.

If type=1, then y is of length Inumrows.
If type=2, then y is of length Inumcols.
Returned as: a one-dimensional real array of doublewords.

Note

EKKGEMV may not be used to compute a matrix-vector product using a node-arc incidence matrix of a network problem unless a column or index copy of the matrix exists.

Example

Refer to "Sample FORTRAN Program EXDANWOL" for an example of using EKKGEMV.

EKKGES - Solve a Basic System of Equations

This subroutine solves A_Bx = b or A_B^Tx = b, where b has length m, x has length m, and A_B is an m by m matrix, where m is the value of the integer control variable Inumrows. This subroutine is normally used in conjunction with EKKINVT.

Syntax

FORTRAN	CALL EKKGES(rtcod,dspace,type,bx)
PL/I	CALL EKKGES(rtcod,dspace,type,bx);
C	ekkges(&rtcod,dspace,type,bx);

On Entry

dspace: is the user-provided work area.

Specified as: a one-dimensional real array of doublewords.

type: is the type of matrix to solve, where:

If type=1, A_B x = b is used in the solve.
If type=2, A_B^T x = b is used in the solve.

Specified as: a fullword integer.

bx: is the right-hand side vector of the equation to be solved.

Specified as: a one-dimensional real array of doublewords, where its length equals Inumrows.

On Return

rtcod: is the return code for the subroutine, where:

If rtcod = 0,

the subroutine completed successfully. Only informational

messages were issued.
If rtcod = rc,

rc is the return code associated with the first occurrence of

the highest severity message.

See "Return Codes" for an explanation of

return codes.

If rtcod = 0,

the subroutine completed successfully. Only

informational messages were issued.

If rtcod = rc,

rc is the return code associated with the first

occurrence of the highest severity message.

Returned as: a fullword integer.

dspace: is the user-provided work area.

Returned as: a one-dimensional real array of doublewords.

bx: is the solution vector.

Returned as: a one-dimensional real array of doublewords, where its length equals Inumrows.

Notes

A_B is the subset of the model matrix comprising the columns currently in the basis in matrix order with the logicals first.
EKKGES may not be used to solve a basis of a network problem if no column or index copy of the matrix exists.

Example

Refer to "Sample FORTRAN Program EXGES" for an example of using EKKGES.

EKKINVT - Compute the Primal and Dual Solutions Corresponding to a Given Basis

This subroutine creates the primal and dual solutions corresponding to a given basis. This subroutine is used whenever a solution is required using a given basis. For example, this can be used after a call to EKKBASI.

This subroutine solves the system Ax = b by solving A_B x_B = b - A_N x_N, in effect inverting the matrix A_B. It factors A_B into the product of a lower triangular matrix, L, and an upper triangular matrix, U, so that A_B = LU. It then solves for x_B, where:

x_B has length m,

x_N has length n - m,

A_B has dimension m × m,

L has dimension m × m,

U has dimension m × m,

A_N has dimension m × (n - m),

m is the value of the integer control variable Inumrows, and

n is the value of the integer control variable Inumcols.

Syntax

FORTRAN	CALL EKKINVT(rtcod,dspace,keep,phase)
PL/I	CALL EKKINVT(rtcod,dspace,keep,phase);
C	ekkinvt(&rtcod,dspace,keep,phase);

On Entry

dspace: is the user-provided work area.

Specified as: a one-dimensional real array of doublewords.

keep: gives you the choice of keeping or erasing the previous factorization, where:

If keep=0,

the factorization is erased.
If keep=1,

the factorization is not erased.

Specified as: a fullword integer. Its value must be 0 or 1.

phase: is used only when the problem is infeasible to specify the phase, where:

If phase=1,

Phase 1 dual solution is indicated.

If phase=2,

Phase 2 dual solution is indicated.

See "Simplex (EKKSSLV)" for information on Phase 1 and 2.

Specified as: a fullword integer. Its value must be 1 or 2.

On Return

rtcod: is the return code for the subroutine, where:

If rtcod = 0,

the subroutine completed successfully. Only informational

messages were issued.
If rtcod = rc,

rc is the return code associated with the first occurrence of

the highest severity message.

See "Return Codes" for an explanation of

return codes.

If rtcod = 0,

the subroutine completed successfully. Only

informational messages were issued.

If rtcod = rc,

rc is the return code associated with the first

occurrence of the highest severity message.

Returned as: a fullword integer.

dspace: is the user-provided work area.

Returned as: a one-dimensional real array of doublewords.

Notes

You can access solutions generated by EKKINVT by looking at the values of the control variables Ncolsol and Nrowacts, which point to the solution in dspace.
If EKKGES is called after EKKINVT, make sure the keep parameter is set to 1, so that EKKGES can use the factorization computed by EKKINVT. If this is to be done, the call to EKKINVT should be preceded by a call to EKKPSHS and the call to EKKGES should be followed by a call to EKKPOPS.
EKKINVT cannot be used with a basis of a network problem if no column or index copy of the matrix exists.

Examples

Refer to the following sample programs for examples of using EKKINVT: