MIP User Exit Subroutines

The MIP User Exit Subroutines

This chapter describes the MIP user exit subroutines EKKBRNU, EKKCHNU, EKKCUTU, EKKEVNU, EKKHEUU, EKKNODU, and EKKSLVU, which you can use to affect the processing of a MIP problem. "Understanding Mixed-Integer User Exit Subroutines" has more information about how to use these subroutines. Sample subroutines appear in "Sample Mixed-Integer User Exit Subroutines".

EKKBRNU - Branch User Exit Subroutine

EKKBRNU is called from EKKMSLV, and it allows you to override a branching choice.

Note:

EKKBRNU can only be written in C or FORTRAN. EKKBRNU should not make any calls that could cause recursion errors.

Function prototype:

C	int ekkbrnu(double *dspace, int * mspace, int * reason, int * iarray, double * rarray, int * userrtcd);
FORTRAN	EKKBRNU(dspace,mspace,reason,iarray,rarray, userrtcd)

On Entry

dspace: is the user-provided work area.

mspace: is the integer version of the work area.

reason: is the situation when EKKBRNU is called, where:

iarray: is an array of special ordered set information, where:

rarray: is an array of values, where:

userrtcd: is the user return code from this user exit subroutine. This will be set to 1 on entry on the first call for each set (when reason=2) If you set this to 0 before returning to the calling routine, then EKKBRNU will be called for each variable in the set. If userrtcd is still nonzero, then EKKBRNU will only be called after the set. This will allow improved performance by not calling this subroutine needlessly.

On Return

dspace: is the user-provided work area.

mspace: is the integer version of the work area.

iarray: is an array of special ordered set information, where:

rarray: is an array of values, where:

userrtcd: is the user return code from this user exit subroutine. This will be set to 1 on entry on the first call for each set (when reason =2) If you set this to 0 before returning to the calling routine, then EKKBRNU will be called for each variable in the set. If userrtcd is still nonzero, then EKKBRNU will only be called after the set. This will allow improved performance by not calling this subroutine needlessly.

Example

Refer to "Understanding Mixed-Integer User Exit Subroutines" for an example of the use of EKKBRNU, and to "Mixed-Integer User Exit EKKBRNU" and "Mixed-Integer User Exit EKKBRNU2" for sample subroutines.

EKKCHNU - Choose Node User Exit Subroutine

EKKCHNU is called from EKKMSLV, and it allows you to modify the choice of nodes during branch-and-bound processing.

Note:

EKKCHNU can only be written in C or FORTRAN. EKKCHNU should not make any calls that could cause recursion errors.

Function prototype:

C	int ekkchnu(double *dspace, int * mspace, int * reason, int * iarray, double * rarray, int * userrtcd);
FORTRAN	EKKCHNU(dspace,mspace,reason,iarray,rarray, userrtcd)

On Entry

dspace: is the user-provided work area.

mspace: is the integer version of the work area.

reason: is the situation when EKKCHNU is called, where:

iarray: is an array of branch and bound search information, where:

rarray: is a array of values, where:

userrtcd: is the user return code from this user exit subroutine. When reason=1, userrtcd is set to 1 on entry on the first call. If you set this to 0 before returning to the calling routine, EKKCHNU will be called with reason=2 If userrtcd is still nonzero, then EKKCHNU will be called only at the end of the list. This will allow improved performance by not calling this subroutine needlessly.

On Return

dspace: is the user-provided work area.

mspace: is the integer version of the work area.

iarray: is an array with node information in its first element, if the value of reason is 3:

userrtcd: is the user return code from this user exit subroutine. When reason=1, userrtcd is set to 1 on entry on the first call. If you set this to 0 before returning to the MIP processing routine, then EKKCHNU will be called with reason=2 If userrtcd is still nonzero, then EKKCHNU will only be called at the end of the list. This will allow improved performance by not calling this subroutine needlessly.

Note

This subroutine allows you to change the choice of the node using any criteria you want (for example, some rule balancing the objective with the number of integer infeasibilities).

Example

Refer to "Understanding Mixed-Integer User Exit Subroutines" for an example of the use of EKKCHNU, and to "Mixed-Integer User Exit EKKCHNU" for a sample subroutine.

EKKCUTU - Cut Generation User Exit Subroutine

EKKCUTU allows you to generate "cuts", or additional constraint rows, to a problem matrix. It is called during EKKMPRE preprocessing, or during supernode processing in EKKMSLV.

Note:

EKKCUTU can be written in FORTRAN or C EKKCUTU should not make any calls that could cause recursion errors.

Function prototype:

C	int ekkcutu(double *dspace, int * mstatbin, int * mtobin, int * mcadd, int * mradd, double * deadd, int * nbin, int * nadd, int * naddmax, int * nrow, int * nrowmax);
FORTRAN	EKKCUTU(dspace,mstatbin,mtobin,mcadd,mradd, deadd, nbin, nadd, naddmax,nrow,nrowmax)

On Entry

dspace: is the user-provided work area.

mstatbin: is the current status of the 0-1 variables, where:

mtobin: is an array with an entry for each variable in the problem. The entry describes the type of variable, where:

mcadd: is the column indices of the cuts to be added.

mradd: is the row indices of the cuts to be added.

deadd: is the elements in the cuts to be added.

nbin: is the number of 0-1 variables contained in mstatbin.

nadd: is the current combined number of entries in mcadd, mradd, and deadd.

naddmax: is the maximum number of entries allowed in the matrix. It is the amount of space available in dspace for cuts at the time EKKCUTU was called.

nrow: is the current number of rows in the matrix (including the added cuts).

nrowmax: is the maximum number of rows allowed in the matrix at the time EKKCUTU was called.

On Return

mcadd: is the column indices of the cuts to be added.

mradd: is the row indices of the cuts to be added.

deadd: is the elements in the cuts to be added.

nadd: is the current combined number of entries in mcadd, mradd, and deadd.

nrow: is the current number of rows in the matrix (including the added cuts).

Notes

Cuts that are added before the first heuristic pass during EKKMPRE processing are permanent cuts. Other cuts will disappear after the heuristic pass or EKKMSLV supernode processing is completed.
See "Mixed-Integer Programming (EKKMPRE and EKKMSLV)" for an explanation of when EKKCUTU is called.
A cut may be discarded, if it becomes nonbinding.
The array mtobin is a mapping of all the variables. It indicates whether a variable is continuous, general integer, or 0-1 integer. If a variable is a 0-1 integer, its entry in mtobin is the FORTRAN index of the corresponding entry in mstatbin. mstatbin contains the status of all 0-1 variables - fixed to 0, fixed to 1, or free. For example, if variable 200 is the 30th 0-1 variable, and it has been fixed to 0, then the 200th entry of mtobin would be 30, and the 30th entry of mstatbin would be -1.
EKKCUTU should return a series of cuts when it concludes. This is done by entering the cuts into the arrays mcadd, mradd, deadd, and nadd The first element of mcadd is the first variable (column) of the problem matrix, and the Inumcols element of mcadd is the last, where Inumcols is an integer control variable. If the pth element of mcadd is set to -1, it denotes a lower bound on row p, and a value of -2 denotes an upper bound. For example, if on entry nadd is 1002 and nrow is 205, the entries in the arrays to add a single cut of x + 2y 2, the entries in the arrays might be:

  iadd   mcadd(iadd)   mradd(iadd)  deadd(iadd)
  1003        5           206           1 0
  1004      407           206           2 0
  1005       -2           206           2 0

The entries in mcadd indicate that x is variable 5, y is variable 407, and that the cut being added is an upper bound.

The entries in mradd indicate that this cut is constraint 206 (the first available place for a cut as indicated by nrow).

The entries in deadd indicate that the cut is 1x, 2y, and that the value of the right-hand side is 2.

On exit, nadd is changed to 1005, and nrow is changed to 206.

It is the user's responsibility to insure that EKKCUTU respects the maximum limits.
The following subroutines can be called from EKKCUTU: EKKMSET
EKKMSTR
EKKNAME
EKKPRTS
EKKSEL
EKKSMAP
EKKSTAT
You can also call EKKCGET, EKKCSET, EKKIGET, EKKISET, EKKRGET, and EKKRSET for specifying informational variables (such as Ilogfreq).

Example

Refer to "Understanding Mixed-Integer User Exit Subroutines" for an example of the use of EKKCUTU, and to "Mixed-Integer User Exit EKKCUTU" for a sample subroutine.

EKKEVNU - Evaluate a Node User Exit Subroutine

EKKEVNU is called from EKKSLVU, which in turn is called from EKKMSLV, to evaluate a node in branch-and-bound processing.

Note:

EKKEVNU can only be written in C or FORTRAN. EKKEVNU should not make any calls that could cause recursion errors.

Function prototype:

C	int ekkevnu(double *dspace, int * mspace, int * userrtcd);
FORTRAN	EKKEVNU(dspace,mspace,userrtcd)

On Entry

dspace: is the user-provided work area.

mspace: is the integer version of the work area.

userrtcd: is the user return code from this user exit subroutine.

On Return

dspace: is the user-provided work area.

mspace: is the integer version of the work area.

userrtcd: is the user return code from this user exit subroutine, where:

Notes

The EKKEVNU subroutine provided with the Library calls EKKSSLV with the dual option to evaluate the node. By providing your own EKKEVNU subroutine, you can modify the solution strategy to use primal, use another solve method, or stop the solver. Following is the default code for EKKEVNU supplied with the Library:

      SUBROUTINE EKKEVNU(DSPACE,MSPACE,JRTCOD)
      INCLUDE (OSLI)
      REAL*8    DSPACE(*)
      INTEGER*4 MSPACE(*)
      INTEGER*4 JRTCOD
      CALL EKKSSLV(JRTCOD,DSPACE,2,1)
      CALL EKKIGET(IRTCOD,DSPACE,OSLI,OSLILN)
C  Set the user return code to 1 if the optimal solution was not found 
      IF(IPROBSTAT NE 0) JRTCOD =  1
      RETURN
      END

You should not set EKKMSLV-related control variables from EKKEVNU.
You can call any of the library subroutines from EKKEVNU except the following:
EKKDSCA
EKKDSCM
EKKGTMD
EKKGTMI
EKKIMDL
EKKLMDL
EKKMPRE
EKKMPS
EKKMSLV
EKKPTMD
EKKPTMI
EKKQMDL
EKKQMPS
EKKSMDL

Example

Refer to "Understanding Mixed-Integer User Exit Subroutines" for an example of the use of EKKEVNU, and to "Mixed-Integer User Exit EKKEVNU" for a sample subroutine.

EKKHEUU - Heuristic Fixing User Exit Subroutine

EKKHEUU gives you control over the fixing of variables to their upper or lower bounds. It can be used to override the default choice of variables in EKKMPRE or EKKMSLV for supernode processing. This information can be used to analyze and prune nodes from the problem.

Note:

EKKHEUU can only be written in C or FORTRAN. EKKHEUU should not make any calls that could cause recursion errors.

Function prototype:

C	int ekkheuu(double *dspace, int * mstatbin, int * mtobin, int * mfix, int * nbin, int * nfix1, int * nfix2, int * jtype);
FORTRAN	EKKHEUU(dspace,mstatbin,mtobin,mfix,nbin, nfix1, nfix2,jtype)

On Entry

dspace: is the user-provided work area.

mstatbin: is the current status of the 0-1 variables, where:

mtobin: is an array with an entry for each variable in the problem. The entry describes the type of variable, where:

nbin: is the number of 0-1 variables contained in mstatbin.

nfix1: is the number of variables to be fixed to 0 or 1 on the current branch. nfix1 is set when EKKHEUU is called from either EKKMPRE preprocessing or EKKMSLV supernode processing.

nfix2: is the number of variables to be fixed to 0 or 1 on the postponed branch. nfix2 is set when EKKHEUU is called from EKKMSLV supernode processing.

jtype: identifies the type of processing currently being done, where:

On Return

dspace: is the user-provided work area.

mfix: is a list of 0-1 variables to be fixed to 0 or 1 This is the branch that EKKHEUU returns to the calling routine (EKKMSLV or EKKMPRE).

nfix1: is the number of variables to be fixed to 0 or 1 on the current branch. nfix1 is set when EKKHEUU is called from either EKKMPRE preprocessing or EKKMSLV supernode processing.

nfix2: is the number of variables to be fixed to 0 or 1 on the postponed branch. nfix2 is set when EKKHEUU is called from EKKMSLV supernode processing.

Notes

See "Mixed-Integer Programming (EKKMPRE and EKKMSLV)" for an explanation of when EKKCUTU is called.
The array mtobin is a mapping of all the variables. It indicates whether a variable is continuous, general integer, or 0-1 integer. If a variable is a 0-1 integer, its entry in mtobin is the FORTRAN index of the corresponding entry in mstatbin. mstatbin contains the status of all 0-1 variables (fixed to 0, fixed to 1, or free) For example, if variable 200 is the 30th 0-1 variable, and it has been fixed to 0, then the 200th entry in mtobin would be 30, and the 30th entry in mstatbin would be -1.
EKKHEUU should return a valid branch in the array mfix when it concludes. Processing continues, setting 0-1 variables to their bounds using the first nfix1 entries in mfix The postponed branch (which is only used if jtype is 2) is given by the next nfix2 entries of mfix.
The following subroutines can be called from EKKHEUU: EKKMSET
EKKMSTR
EKKNAME
EKKPRTS
EKKSEL
EKKSMAP
EKKSTAT
You can also call EKKCGET, EKKCSET, EKKIGET, EKKISET, EKKRGET, and EKKRSET for specifying informational variables (such as Ilogfreq).

Example

Refer to "Understanding Mixed-Integer User Exit Subroutines" for an example of the use of EKKHEUU, and to "Mixed-Integer User Exit EKKXHEUU" for a sample subroutine.

EKKNODU - Node User Exit Subroutine

EKKNODU is called from EKKMSLV It allows you to save extra information about a node before creating a node, and to restore that information when the node is created.

Note:

EKKNODU can only be written in C or FORTRAN. EKKNODU should not make any calls that could cause recursion errors.

Function prototype:

C	int ekknodu(double *dspace, int * mspace, int * reason, int * iarray, double * darray, int * muser, int * nuser);
FORTRAN	EKKNODU(dspace,mspace,reason,iarray,darray, muser, nuser)

On Entry

dspace: is the main user-provided work area.

mspace: is the integer version of the work area.

reason: is the situation when EKKNODU is called, where:

iarray: is an array of branching information, where:

darray: is a single element array whose one element is the value of the continuous variable in the parent/reference value where the set was split.

muser: is the user-specified array to be saved or restored. It contains information that you wish to save and restore.

nuser: is the length of the muser array.

On Return

dspace: is the user-provided work area.

mspace: is the integer version of the work area.

Note: The following subroutines can be called from EKKNODU:

EKKMSET
EKKMSTR
EKKPRTS

You can also call EKKCGET, EKKCSET, EKKIGET, EKKISET, EKKRGET, and EKKRSET for specifying informational variables such as Ilogfreq.

Example

Refer to "Understanding Mixed-Integer User Exit Subroutines" for an example of the use of EKKNODU, and to "Mixed-Integer User Exit EKKNODU" for a sample subroutine.

EKKSLVU - Branch User Exit Subroutine

EKKSLVU is called from EKKMSLV, and it allows you to override the default solver routine.

Note:

EKKSLVU can only be written in C or FORTRAN. EKKSLVU should not make any calls that could cause recursion errors.

Function prototype:

C	int ekkslvu(double *dspace, int * mspace, double * dobjval, int * jrtcod, int * jtype);
FORTRAN	EKKSLVU(dspace,mspace,dobjval,jrtcod,jtype)

On Entry

dspace: is the user-provided work area.

mspace: is the integer version of the work area.

jtype: identifies the situation in which EKKSLVU is called, where:

On Return

dspace: is the user-provided work area.

mspace: is the integer version of the work area.

dobjval: is the value of the objective function for feasible nodes.

jrtcod: is the value of iprobstat after the solution of the node.

Notes

You may write code that uses either EKKSSLV or EKKQSLV to solve the nodes of the branch and bound tree.
The default version of EKKSLVU that is distributed with the library includes the only call to EKKEVNU. If a user supplied version of EKKSLVU is linked with a library application program, then EKKEVNU may not be referred to at all, and thus might be neither called nor even linked.

Example

Refer to "Understanding Mixed-Integer User Exit Subroutines" for an example of the use of EKKSLVU, and to "Sample User Exit Subroutine EXSLVU" for a sample subroutine.