Procedure GMP::Instance::AddIntegerEliminationRows(GMP, solution, elimNo)

GMP::Instance::AddIntegerEliminationRows

The procedure GMP::Instance::AddIntegerEliminationRows adds integer elimination rows to the generated mathematical program which will eliminate an integer solution.

GMP::Instance::AddIntegerEliminationRows(
     GMP,          ! (input) a generated mathematical program
     solution,     ! (input) a solution
     elimNo        ! (input) an elimination number
     )

Arguments

GMP

An element in AllGeneratedMathematicalPrograms.

solution

An integer scalar reference to a solution.

elimNo

An integer scalar reference to an elimination number.

Return Value

The procedure returns 1 on success, or 0 otherwise.

Note

  • If the GMP is not integer then this procedure will fail.

  • Rows and columns added before for elimNo will be deleted first.

  • If the GMP contains only binary variables then only one row will be added; if the GMP contains general integer variables then several rows and columns will be added.

  • The exact definitions of the rows and columns that are added are as follows. Let \(x_i\) be an integer column whose level value \(lev_i\) is between its lower bound \(lb_i\) and upper bound \(ub_i\), i.e., \(lb_i < lev_i < ub_i\). Then columns \(l_i \geq 0\) and \(u_i \geq 0\) are added together with a binary column \(z_i\). Also the following three constraints are added:

    (2)\[l_i + (lev_i - lb_i)z_i \leq (lev_i - lb_i)\]

    (3)\[u_i + (lev_i - ub_i) z_i \leq 0\]
    (4)\[x_i - u_i + l_i = lev_i\]

    Every call to GMP::Instance::AddIntegerEliminationRows also adds the following constraint:

    (5)\[\begin{aligned} \sum_{i\in S_{lo}} x_i - \sum_{i\in S_{up}} x_i + \sum_{i\in S_{in}} (l_i + u_i) \geq 1 + \sum_{i\in S_{lo}} lev_i - \sum_{i\in S_{up}} lev_i \end{aligned}\]

    where \(S_{lo}\) defines the set of integer columns whose level values equal their lower bounds, \(S_{up}\) the set of integer columns whose level values equal their upper bounds, and \(S_{in}\) the set of integer columns whose level values are between their bounds.

  • By using the suffixes .ExtendedConstraint and .ExtendedVariable it is possible to refer to the rows and columns respectively that are added by GMP::Instance::AddIntegerEliminationRows:

    • Variables v.ExtendedVariable('EliminationLowerBoundk',i), v.ExtendedVariable('EliminationUpperBoundk',i) and v.ExtendedVariable('Eliminationk',i) are added for each integer variable v(i) with the level value between its bounds. (These variables correspond to \(l_i\), \(u_i\) and \(z_i\) respectively.)

    • Constraints v.ExtendedConstraint('EliminationLowerBoundk',i), v.ExtendedConstraint('EliminationUpperBoundk',i) and v.ExtendedConstraint('Eliminationk',i) are added for each integer variable v(i) with the level value between its bounds. (These constraints correspond to ((2), ((3) and ((4) respectively.)

    • Constraint mp.ExtendedConstraint('Eliminationk'), where mp denotes the symbolic mathematical program, is added for every call to GMP::Instance::AddIntegerEliminationRows. (This constraint corresponds to ((5).)

    Here \(k\) denotes the value of the argument elimNo.

Example

The procedure GMP::Instance::AddIntegerEliminationRows can be used to find the five best integer solutions for some MIP model:

gmp_mip := GMP::Instance::Generate(MIP_Model);

cnt := 1;

while ( cnt <= 5 ) do
    GMP::Instance::Solve(gmp_mip);

    ! Eliminate previous found integer solution.
    GMP::Instance::AddIntegerEliminationRows(gmp_mip,1,cnt);

    cnt += 1;

    ! Copy solution at position 1 to solution at position cnt
    ! in solution repository.
    GMP::Solution::Copy(gmp_mip,1,cnt);
endwhile;

After executing this code, the five best integer solutions will be stored at positions 2 - 6 in the solution repository, with the best solution at position 2 and the 5th best at position 6.

See also

The routines GMP::Instance::DeleteIntegerEliminationRows and GMP::Solution::IsInteger. See Modifying an Extended Math Program Instance of the Language Reference for more details on extended suffixes.