Ai*x uri for i = 1 to m lcj
xj ucj for j = 1 to n For the Optimization Library, we define a linear programming problem in the following manner:
minimize c T x
subject to: lr Ai*x uri for i = 1 to m
lcj xj ucj for j = 1 to n
where:
EKKLMDL is a subroutine that can be used to put LP model data directly into Optimization Library data structures. The parameters supplied to EKKLMDL represent the parts of your linear model. The calling sequence parameters, and with their meanings, are:
Specified as: a one-dimensional real array of doublewords.
If type=1, a copy of the matrix is stored by indices. See "Storage-by-Indices" for information on storage-by-indices.
If type=2, a copy of the matrix is stored by columns. See "Storage-by-Columns" for information on storage-by-columns.
Specified as: a fullword integer. Its value must be 1 or 2.
Specified as: a fullword integer.
Specified as: a fullword integer.
Specified as: a fullword integer; if the matrix is stored by columns, then
in FORTRAN: nel = mcol(nc+1) - 1, and in C: nel = mcol(nc) - 1.
Specified as: a one-dimensional real array of doublewords with nc entries.
Specified as: a one-dimensional real array of doublewords with nr entries.
Specified as: a one-dimensional real array of doublewords with nr entries.
Specified as: a one-dimensional real array of doublewords with nc entries.
Specified as: a one-dimensional real array of doublewords with nc entries.
Specified as: a one-dimensional array of doublewords with nel entries. The best way to see how to pass model data directly to the library workspace using EKKLMDL is by showing an example.
The "toy" problem that we will solve is:
maximize x1 + 2x5 - x8
subject to:
2.5 3x1 + x2 + -2x4 -x5 -x8
2x2 +1.1x3 2.1
x3 +x6 = 4.0
1.8 2.8x4 -1.2x7 5.0
3.0 5.6x1 +x5 +1.9x8 15.0
where:
2.5 x1
0 x2 4.1
0 x3
0 x3
0 x4
0.5 x5 4.0
0 x6
0 x7
0 x8 4.3
The following lines of code specify the objective function coefficients to Optimization Library modules. We have used FORTRAN DATA statements, but the information could just as easily be read in from a file, or piped in from another program.
Note that all coefficients must be specified, including zero coefficients You also need to specify that the problem is a maximization problem. This is done by setting the real control variable Rmaxmin to -1.0.
INCLUDE (OSLR)
C
.
.
.
C
C
C Objective Function Coefficients
DATA DOBJ /1.0D0,3*0.0D0,2.0D0,2*0.0D0,-1.0D0/
C
.
.
.
C
C
C Set to maximization problem.
CALL EKKRGET(RTCOD,DSPACE,OSLR,OSLRLN)
IF (RTCOD.GT.0) CALL CHKRT('EKKRGET',RTCOD)
RMAXMIN=-1.0D0
CALL EKKRSET(RTCOD,DSPACE,OSLR,OSLRLN)
IF (RTCOD.GT.0) CALL CHKRT('EKKRSET',RTCOD)
The following lines of code specify the row and column bounds to Optimization Library modules. There must be upper and lower bounds on every row and column. If there are no bounds, then for the upper bound, specify infinity, and for the lower bound, specify negative infinity. The Optimization Library modules use 1031 as an operational value for infinity. However, you may use a larger number to indicate infinity, if you wish.
C C Lower Bounds on Row Activities DATA DRLO /2.5D0,-1.0D31,4.0D0,1.8D0,3.0D0/ C C Upper Bounds on Row Activities DATA DRUP /1.0D31,2.1D0,4.0D0,5.0D0,1.5D01/ C C Lower Bounds on Columns DATA DCLO /2.5D0,0.0D0,2*0.0D0,5.0D-1,3*0.0D0/ C C Upper Bounds on Columns DATA DCUP /1.0D31,4.1D0,2*1.0D31,4.0D0,2*1.0D31,4.3D0/ C
The following lines of code define your constraint matrix to Optimization Library modules. In this example we have used storage-by-columns for a problem with 8 columns. You may choose to use storage-by-indices, or storage-by-rows. See "Sparse Matrix" for more information about storage-by-columns, indices, or rows.
C C Matrix Elements DATA DELS /3.0D0,5.6D0,1.0D0,2.0D0,1.1D0,1.0D0,-2.0D0, & 2.8D0,-1.0D0,1.0D0,1.0D0,-1.2D0,-1.0D0,1.9D0/ C C Row Indices DATA MROW /1,5,1,2,2,3,1,4,1,5,3,4,1,5/ C C Column Starts DATA MCOL /1,3,5,7,9,11,12,13,15/ C
C***********************************************************************
C
C EXLMDL
C
C This program solves the following problem:
C
C Maximize x1 + 2x5 - x8
C
C Subject to:
C
C 2.5 <= 3x1 + x2 - 2x4 - x5 - x8
C 2x2 + 1.1x3 <= 2.1
C x3 + x6 = 4.0
C 1.8 <= 2.8x4 -1.2x7 <= 5.0
C 3.0 <= 5.6x1 + x5 + 1.9x8 <= 15.0
C
C and subject to:
C
C 2.5 <= x1
C 0 <= x2 <= 4.1
C 0 <= x3
C 0 <= x4
C 0.5 <= x5 <= 4.0
C 0 <= x6
C 0 <= x7
C 0 <= x8 <= 4.3
C
C NROW is the number of rows in the constraint matrix.
C NCOL is the number of columns in the constraint matrix.
C NEL is the number of elements in the constraint matrix.
C ITYPE is the storage format.
C IRL is the length of the arrays containing row information.
C ICL is the length of the arrays containing column information.
C ICL1 is ICL + 1.
C IEL is the length of the arrays containing element information.
C
C***********************************************************************
C
PROGRAM MAIN
C
C Bring in include files with control variable definitions.
IMPLICIT NONE
INCLUDE (OSLI)
INCLUDE (OSLR)
C
C Allocate dspace and other arrays.
INTEGER*4 MAXSPC,IRL,ICL,ICL1,IEL
PARAMETER (MAXSPC=15000,IRL=5,ICL=8,ICL1=9,IEL=14)
REAL*8 DSPACE(MAXSPC)
C
REAL*8 DRLO(IRL),DCLO(ICL),DOBJ(ICL),DELS(IEL),DRUP(IRL),DCUP(ICL)
INTEGER*4 NCOL,NROW,NEL,ITYPE,MCOL(ICL1),MROW(IEL),RTCOD
C
C Define the model.
DATA NROW,NCOL,NEL,ITYPE /5,8,14,2/
C
C Matrix elements.
DATA DELS/3.0D0,5.6D0,1.0D0,2.0D0,1.1D0,1.0D0,-2.0D0,
+ 2.8D0,-1.0D0,1.0D0,1.0D0,-1.2D0,-1.0D0,1.9D0/
C
C Row indices.
DATA MROW/1,5,1,2,2,3,1,4,1,5,3,4,1,5/
C
C Column starts.
DATA MCOL/1,3,5,7,9,11,12,13,15/
C
C Lower bounds on row activities.
DATA DRLO/2.5D0,-1.0D31,4.0D0,1.8D0,3.0D0/
C
C Upper bounds on row activities.
DATA DRUP/1.0D31,2.1D0,4.0D0,5.0D0,1.5D01/
C
C Lower bounds on columns.
DATA DCLO/2.5D0,0.0D0,2*0.0D0,5.0D-1,3*0.0D0/
C
C Upper bounds on columns.
DATA DCUP/1.0D31,4.1D0,2*1.0D31,4.0D0,2*1.0D31,4.3D0/
C
C Objective function coefficients.
DATA DOBJ/1.0D0,3*0.0D0,2.0D0,2*0.0D0,-1.0D0/
C
C
C Describe application and specify that there is 1 model.
CALL EKKDSCA(RTCOD,DSPACE,MAXSPC,1)
IF (RTCOD.GT.0) CALL CHKRT('EKKDSCA',RTCOD)
C
C Set to maximization problem.
CALL EKKRGET(RTCOD,DSPACE,OSLR,OSLRLN)
IF (RTCOD.GT.0) CALL CHKRT('EKKRGET',RTCOD)
RMAXMIN=-1.0D0
CALL EKKRSET(RTCOD,DSPACE,OSLR,OSLRLN)
IF (RTCOD.GT.0) CALL CHKRT('EKKRSET',RTCOD)
C
C Pass the model with matrix stored by columns.
CALL EKKLMDL(RTCOD,DSPACE,ITYPE,NROW,NCOL,NEL,DOBJ,DRLO,DRUP,
+ DCLO,DCUP,MROW,MCOL,DELS)
IF (RTCOD.GT.0) CALL CHKRT('EKKLMDL',RTCOD)
C
C Solve problem using simplex method.
CALL EKKSSLV(RTCOD,DSPACE,1,2)
IF (RTCOD.GT.0) CALL CHKRT('EKKSSLV',RTCOD)
C
C Print the solution.
CALL EKKPRTS(RTCOD,DSPACE)
IF (RTCOD.GT.0) CALL CHKRT('EKKPRTS',RTCOD)
C
STOP
END
C
C***********************************************************************
C This subroutine prints the character string RTNAME and the return
C code RTCOD and stops if RTCOD is large enough to indicate that an
C OSL error or severe error has occured.
C***********************************************************************
C
SUBROUTINE CHKRT(RTNAME,RTCOD)
CHARACTER*7 RTNAME
INTEGER*4 RTCOD
C
WRITE(6,9000) RTNAME,RTCOD
IF (RTCOD.GE.200) STOP 16
RETURN
9000 FORMAT (1X,'********** ',A7,' return code of ',I4,' **********')
END
This sample problem examines how to use basis data. Later, we will see that for MPS data there are two routines called EKKBASI and EKKBASO, but here we will do it with library data structures.
C***********************************************************************
C
C EXOSLBAS
C
C This program reads a problem from an MPS file, sets up a basis,
C solves the problem with the simplex method, and prints the solution.
C
C***********************************************************************
C
PROGRAM MAIN
C
C Bring in include files with control variable definitions.
IMPLICIT NONE
INCLUDE (OSLR)
INCLUDE (OSLI)
INCLUDE (OSLN)
C
C Allocate dspace.
INTEGER*4 MAXSPC,RTCOD
PARAMETER (MAXSPC=50000)
CHARACTER*8 CSPACE(MAXSPC)
INTEGER*4 MSPACE(2*MAXSPC)
REAL*8 DSPACE(MAXSPC)
EQUIVALENCE (DSPACE,MSPACE,CSPACE)
COMMON/BIG/DSPACE
C
C Describe application and specify that there is 1 model.
CALL EKKDSCA(RTCOD,DSPACE,MAXSPC,1)
IF (RTCOD.GT.0) CALL CHKRT('EKKDSCA',RTCOD)
C
C Read model data from MPS file on unit 98.
CALL EKKMPS(RTCOD,DSPACE,98,2,0)
IF (RTCOD.GT.0) CALL CHKRT('EKKMPS ',RTCOD)
C
C Create a row copy of the matrix.
CALL EKKCOPY(RTCOD,DSPACE,3)
IF (RTCOD.GT.0) CALL CHKRT('EKKCOPY',RTCOD)
C
C Get values of control variables.
CALL EKKIGET(RTCOD,DSPACE,OSLI,OSLILN)
IF (RTCOD.NE.0) CALL CHKRT('EKKIGET',RTCOD)
CALL EKKRGET(RTCOD,DSPACE,OSLR,OSLRLN)
IF (RTCOD.NE.0) CALL CHKRT('EKKRGET',RTCOD)
CALL EKKNGET(RTCOD,DSPACE,OSLN,OSLNLN)
IF (RTCOD.NE.0) CALL CHKRT('EKKNGET',RTCOD)
C
C Set up the basis.
CALL SETBAS(MSPACE(NROWRC),MSPACE(NCOLRC),CSPACE(NROWNAMES),
+ DSPACE(NOBJECTIVE),MSPACE(NROWSTAT),MSPACE(NCOLSTAT),
+ INUMROWS,RMAXMIN,IPRINTUNIT)
C
C Solve the problem using the basis.
CALL EKKSSLV(RTCOD,DSPACE,2,0)
IF (RTCOD.GT.0) CALL CHKRT('EKKSSLV',RTCOD)
C
C Print the solution.
CALL EKKPRTS(RTCOD,DSPACE)
IF (RTCOD.GT.0) CALL CHKRT('EKKPRTS',RTCOD)
C
STOP
END
C
C***********************************************************************
C This subroutine sets up a basis. For certain rows, the column with
C the smallest objective coefficient is marked as basic.
C
C In this example, the MPS file contains equality GUB rows.
C The names of these rows begin with GUB. By choosing variables
C with the smallest objective coefficient to be basic, a dual
C feasible basis can be obtained.
C
C Note: Generalized upper bound rows are sets of rows with no columns
C in common, and all element values 1.0. They may be L or G rows.
C***********************************************************************
C
SUBROUTINE SETBAS(MROW,MCOL,NAMES,DOBJ,MRSTAT,MCSTAT,NROW,
+ DWAY,IPRINTUNIT)
C
INTEGER*4 MROW(*),MCOL(*),MRSTAT(*),MCSTAT(*),IBASIC
REAL*8 DOBJ(*),DMM,DWAY
CHARACTER*8 NAMES(*)
C
C Basic variables have the 32 bit (most significant) set.
IBASIC=ISHFT(1,31)
C
DO IROW =1,NROW
IF (NAMES(IROW)(1:3) .EQ. 'GUB') THEN
C Initialize the smallest objective coefficient to infinity
DMM=1.0D31
DO IEL=MROW(IROW),MROW(IROW+1)-1
JCOL=MCOL(IEL)
C See if the current objective coefficient is the
C smallest so far
IF (DMM.GT.DWAY*DOBJ(JCOL)) THEN
KCOL=JCOL
DMM=DWAY*DOBJ(JCOL)
ENDIF
ENDDO
C Mark the column as basic
MCSTAT(KCOL)=IBASIC
MRSTAT(IROW)=0
WRITE(IPRINTUNIT,*) 'Column ',KCOL,' marked as basic.'
ENDIF
ENDDO
RETURN
END
C
C***********************************************************************
C This subroutine prints the character string RTNAME and the return
C code RTCOD and stops if RTCOD is large enough to indicate that an
C OSL error or severe error has occured.
C***********************************************************************
C
SUBROUTINE CHKRT(RTNAME,RTCOD)
CHARACTER*7 RTNAME
INTEGER*4 RTCOD
C
WRITE(6,9000) RTNAME,RTCOD
IF (RTCOD.GE.200) STOP 16
RETURN
9000 FORMAT (1X,'********** ',A7,' return code of ',I4,' **********')
END
EKKIMDL is used to pass integer information about mixed-integer problems to Optimization Library modules. You may use EKKMPS or EKKLMDL to load matrix coefficients and bound information for a mixed integer programming problem as if it were a linear programming problem, and then use EKKIMDL to identify integer variables, define special ordered sets, and possibly reset column bounds before proceeding with the problem solution using one or both of EKKMPRE and EKKMSLV. See "Defining MIP Problems and Special Ordered Sets with EKKIMDL", the notes that follow the description of EKKIMDL on page "EKKIMDL - Specify the Integer Parts of a Model", and the sample drivers EXIMDL, EXIMDL1, ..., EXIMDL5, in Appendix B, for more information on how to do this.
No special means of distinguishing 0-1 integer variables from general integer variables is provided. An integer variable whose lower bound is 0 and whose upper bound is 1 is ipso facto a 0-1 integer variable. EKKIMDL provides several ways to specify that selected, or all, variables be identified as integer variables, but whether they are 0-1 integer variables or not is determined by the values of their upper and lower bounds.
In one particular case EKKIMDL will reset the upper bound of an integer variable, as follows. If a variable is identified in the call to EKKIMDL as an integer variable, EKKIMDL will inspect it's upper and lower bounds, and if the lower bound is 0, and the upper bound is 1031 then EKKIMDL will reset the upper bound to 1, thus specifying that the variable is a 0-1 integer variable. If you want a general integer variable to have a large upper bound, then you should use 10 30 or some other large value besides 1031.
EKKPMDL can be used to load any or all of the parametric change vectors before calling the parametric solver EKKSPAR. These vectors are passed in as five change vectors: cdelta, lrdelta, urdelta, lcdelta, and ucdelta. These are applied as specified in "LP Parametrics (EKKSPAR)" to the objective function coefficients, row lower bounds, row upper bounds, column lower bounds, and column upper bounds, respectively.
A bit mask is also passed to specify which of the change vectors should be used (see "EKKPMDL - Specify a Parametric Model"). For example, if you are interested only in changing the column bounds, then the bit mask can be set to do so. (See "Control Variable Bit Masks" for information on bit masks.)
An example of using EKKPMDL to set up vectors and an appropriate mask specifying which should be used is contained in "Sample FORTRAN Program EXPARA2".
EKKNMDL is used to put information about network linear programming problems into the library workspace. See "Sample FORTRAN Program EXNMDL" for an example of how to do this.
EKKNMDL can create column or index copies of a network constraint matrix in addition to creating network data structures. If a column or index copy of the constraint matrix exists, changes to the network can be made by calling EKKROW or EKKCOL.
The following is a simple example similar to the LP example given above, with a quadratic term added to the objective function. (Note that EKKQSLV always does a minimization problem.)
The quadratic addition to the linear objective given above is:
( x12 + x22 + x32 + x42 + x52 + x62 + x72 + x82 ) / 2
EKKLMDL is used to load the linear terms as before, and then EKKQMDL is used to load the quadratic terms.
The quadratic matrix is set up by the following statements:
C C Quadratic Matrix Elements DATA DELSQ /8*1.0D0/ C C Quadratic Matrix Row Indices DATA MROWQ /1,2,3,4,5,6,7,8/ C C Quadratic Matrix Column Indices DATA MCOLQ /1,2,3,4,5,6,7,8/
The resulting sample program, EXQMDL, follows.
C***********************************************************************
C
C EXQMDL
C
C This program solves the following problem:
C
C Minimize x1 + 2x5 - x8 + (1/2)(x1**2 + x2**2 + x3**2 + x4**2
C + x5**2 + x6**2 + x7**2 + x8**2)
C Subject to:
C
C 2.5 <= 3x1 + x2 - 2x4 - x5 - x8
C 2x2 + 1.1x3 <= 2.1
C x3 + x6 = 4.0
C 1.8 <= 2.8x4 -1.2x7 <= 5.0
C 3.0 <= 5.6x1 + x5 + 1.9x8 <= 15.0
C
C And subject to:
C
C 2.5 <= x1
C 0 <= x2 <= 4.1
C 0 <= x3
C 0 <= x4
C 0.5 <= x5 <= 4.0
C 0 <= x6
C 0 <= x7
C 0 <= x8 <= 4.3
C
C NROW is the number of rows in the constraint matrix.
C NCOL is the number of columns in the constraint matrix.
C NEL is the number of elements in the constraint matrix.
C ITYPE is the storage format.
C IRL is the length of the arrays containing row information.
C ICL is the length of the arrays containing column information.
C ICL1 is ICL + 1.
C IEL is the length of the arrays containing element information.
C
C***********************************************************************
C
PROGRAM MAIN
C
C Allocate dspace and other arrays.
IMPLICIT NONE
INTEGER*4 MAXSPC,IRL,ICL,ICL1,IEL
PARAMETER (MAXSPC=20000,IRL=5,ICL=8,ICL1=9,IEL=14)
REAL*8 DSPACE(MAXSPC),DELSQ(8)
INTEGER*4 MROWQ(8),MCOLQ(8),NELQ,IQTYPE,RTCOD
REAL*8 DRLO(IRL),DCLO(ICL),DOBJ(ICL),DELS(IEL),DRUP(IRL),DCUP(ICL)
INTEGER*4 NCOL,NROW,NEL,ITYPE,MCOL(ICL1),MROW(IEL)
C
C Define the model.
DATA NROW,NCOL,NEL,ITYPE /5,8,14,2/
C
C Define the quadratic matrix.
DATA NELQ,IQTYPE /8,1/
C
C Matrix elements.
DATA DELS /3.0D0,5.6D0,1.0D0,2.0D0,1.1D0,1.0D0,-2.0D0,
+ 2.8D0,-1.0D0,1.0D0,1.0D0,-1.2D0,-1.0D0,1.9D0/
C
C Row indices.
DATA MROW /1,5,1,2,2,3,1,4,1,5,3,4,1,5/
C
C Column starts.
DATA MCOL /1,3,5,7,9,11,12,13,15/
C
C Lower bounds on row activities.
DATA DRLO /2.5D0,-1.0D31,4.0D0,1.8D0,3.0D0/
C
C Upper bounds on row activities.
DATA DRUP /1.0D31,2.1D0,4.0D0,5.0D0,1.5D01/
C
C Lower bounds on columns.
DATA DCLO /2.5D0,0.0D0,2*0.0D0,5.0D-1,3*0.0D0/
C
C Upper bounds on columns.
DATA DCUP /1.0D31,4.1D0,2*1.0D31,4.0D0,2*1.0D31,4.3D0/
C
C Objective function coefficients.
DATA DOBJ /1.0D0,3*0.0D0,2.0D0,2*0.0D0,-1.0D0/
C
C Quadratic matrix elements.
DATA DELSQ /8*1.0D0/
C
C Quadratic matrix row indices.
DATA MROWQ /1,2,3,4,5,6,7,8/
C
C Quadratic matrix column indices.
DATA MCOLQ /1,2,3,4,5,6,7,8/
C
C
C Describe application and specify that there is 1 model.
CALL EKKDSCA(RTCOD,DSPACE,MAXSPC,1)
IF (RTCOD.GT.0) CALL CHKRT('EKKDSCA',RTCOD)
C
C Describe the model. Minimum of 5 blocks are needed for QP.
CALL EKKDSCM(RTCOD,DSPACE,1,5)
IF (RTCOD.GT.0) CALL CHKRT('EKKDSCM',RTCOD)
C
C Pass linear model with matrix stored by columns.
CALL EKKLMDL(RTCOD,DSPACE,ITYPE,NROW,NCOL,NEL,DOBJ,DRLO,DRUP,
+ DCLO,DCUP,MROW,MCOL,DELS)
IF (RTCOD.GT.0) CALL CHKRT('EKKLMDL',RTCOD)
C
C Pass quadratic matrix stored by indices.
CALL EKKQMDL(RTCOD,DSPACE,IQTYPE,NELQ,MROWQ,MCOLQ,DELSQ)
IF (RTCOD.GT.0) CALL CHKRT('EKKQMDL',RTCOD)
C
C Solve the QP using the primal algorithm.
CALL EKKQSLV(RTCOD,DSPACE,1,1)
IF (RTCOD.GT.0) CALL CHKRT('EKKQSLV',RTCOD)
C
C Print the solution.
CALL EKKPRTS(RTCOD,DSPACE)
IF (RTCOD.GT.0) CALL CHKRT('EKKPRTS',RTCOD)
STOP
END
C
C***********************************************************************
C This subroutine prints the character string RTNAME and the return
C code RTCOD and stops if RTCOD is large enough to indicate that an
C OSL error or severe error has occured.
C***********************************************************************
C
SUBROUTINE CHKRT(RTNAME,RTCOD)
CHARACTER*7 RTNAME
INTEGER*4 RTCOD
C
WRITE(6,9000) RTNAME,RTCOD
IF (RTCOD.GE.200) STOP 16
RETURN
9000 FORMAT (1X,'********** ',A7,' return code of ',I4,' **********')
END
Sometimes it is convenient to be able to define an "empty" linear programming model to be populated later on. The subroutine EKKEMDL is provided for this purpose. (The model could be populated, for example, with EKKCOL and EKKROW.) The parameters in the calling sequence of EKKEMDL are: "rtcod," a return code, "dspace," a location in memory at which to begin storing model information, and "nrow," "ncol," and "nels" the numbers of rows, columns, and nonzero elements respectively to be provided for in the empty model. Note that since the value of "dspace" supplied corresponds to this particular model, it need not be the same as that supplied to other Library modules that may be working on some other model. See the description of EKKEMDL for more details.
[ Top of Page | Previous Page | Next Page | Table of Contents ]