Examples of Use

This section

In this section there are five examples to illustrate the use of the GMP library. Each example consists of two paragraphs. The first paragraph explains the basic problem and an algorithmic approach, while the second paragraph provides the corresponding implementation in AIMMS using the GMP procedures. Note that these algorithms could also have been implemented using AIMMS’ regular SOLVE statement, but at the cost of one or more structure recognition steps during every iteration.

Indexed Mathematical Program Instances

Indexed mathematical program instances

AIMMS does not support indexed mathematical program declarations, which would result in a different mathematical program for every index value when generated. Using the GMP library, however, it is straightforward to generate indexed mathematical program instances

Declarations in AIMMS

Consider the following declarations

Set Cities {
    Index        : c, j;
Set  SelectedCities {
    SubsetOf     : Cities;
    Index        : i;

together with a mathematical program declaration TransportModel defining a standard transportation problem determining transports from cities i to j. When SelectedCities equals Cities we would solve the mathematical program for all possible combinations of cities.

Procedure in AIMMS

Further assume that we have an element parameter IndexedTransportModel(c) into the set AllGeneratedMathematicalPrograms. The following procedure illustrates how indexed mathematical program instances for every city c which restricts the transports from c to all cities j.

for ( c ) do
    SelectedCities := {c};

    IndexedTransportModel(c) := GMP::Instance::Generate( TransportModel,
                         "TransportModel-" + FormatString("%e", c) );

Sensitivity Analysis

Parametric changes

Sensitivity analysis considers how the optimal solution, and the corresponding objective function value, change as a result of changes in input data. Using the GMP library, it is straightforward to write a procedure to determine these sensitivities for a discrete set of input values.

Procedure in AIMMS

The following procedure illustrates how parametric changes can be implemented using matrix manipulation functions. The resulting objective function values are stored in a separate identifier.

myGMP := GMP::Instance::Generate( MathProgramOfInterest );

for ( n ) do
   GMP::Coefficient::Set( myGMP,
                          OriginalCoefficient + Delta(n) );

   GMP::Instance::Solve( myGMP );

   ObjectiveValue(n) := GMP::Solution::GetObjective(myGMP, 1);

Finding a Feasible Solution for a Binary Program

Fixing one variable at a time

There have been instances in which the following simple but greedy heuristic was used successfully to solve a binary program. The algorithm considers linear programming solutions in sequence. During each iteration, the algorithm

  • selects the single variable that, of all the variables, is nearest but not equal to one of its bounds, and

  • fixes the value of this variable to that of the nearest bound.

As soon as such variables can no longer be found (and the last linear programming solution is optimal), a feasible integer solution to the binary program has been found.

Procedure in AIMMS

The following procedure illustrates how fixing one variable at a time can be implemented using matrix manipulation functions. The procedure terminates as soon as there is no solution, or all variables have been fixed.

relaxedGMP := GMP::Instance::Generate( RelaxedBinaryProgram );
GMP::Instance::Solve( relaxedGMP );

    LargestLessThanOne      := ArgMax( j | x(j) <= 1 - Tolerance, x(j) );
    SmallestGreaterThanZero := ArgMin( j | x(j) >= Tolerance,     x(j) );

    break when ( RelaxedBinaryProgram.ProgramStatus = 'Infeasible' or
                 not ( LargestLessThanOne or SmallestGreaterThanZero ) );

    if ( x(SmallestGreaterThanZero) < 1 - x(LargestLessThanOne) )
    then GMP::Column::Freeze( relaxedGMP, x(SmallestGreaterThanZero), 0 );
    else GMP::Column::Freeze( relaxedGMP, x(LargestLessThanOne), 1 );

    GMP::Instance::Solve( relaxedGMP );

Column Generation

Adding columns

Chapter 20 of the AIMMS book on Optimization Modeling describes a cutting stock problem. This problem is modeled as a linear program with an initial selection of cutting patterns. An auxiliary integer programming model is introduced to generate a new “best” pattern based on the current solution of the linear program and the corresponding shadow prices. Such a pattern is then added to the existing patterns in the linear program, and the next optimal solution is found. This process continues until no further improvement in the value of the objective function can be achieved.

Procedure in AIMMS

The following procedure illustrates how adding columns can be implemented using matrix manipulation functions. During each iteration of the overall process, two different mathematical programs are modified in turn.

cuttingStockGMP := GMP::Instance::Generate( CuttingStock );
GMP::Instance::Solve( cuttingStockGMP );

findPatternGMP := GMP::Instance::Generate( FindPattern );
GMP::Instance::Solve( findPatternGMP );

MaxPattern := 0;
while ( PatternContribution > 1 ) do
    MaxPattern += 1;
    AllPatterns += MaxPattern;
    LastPattern := last(AllPatterns);

    GMP::Column::Add( GMP: cuttingStockGMP, column: RollsUsed(LastPattern) );

    for ( width ) do
        GMP::Coefficient::Set( GMP   : cuttingStockGMP,
                               row   : MeetCutDemand(width),
                               column: RollsUsed(LastPattern),
                               value : CutsInPattern(width)  );
    GMP::Instance::Solve( cuttingStockGMP );

    for ( width ) do
        GMP::Coefficient::Set( GMP   : findPatternGMP,
                               row   : PatternContribution,
                               column: CutsInPattern(width),
                               value : MeetCutDemand(width).ShadowPrice );
    GMP::Instance::Solve( findPatternGMP );

Here MaxPattern is a parameter of type integer, AllPatterns a subset of Integers, and LastPattern an element parameter with range AllPatterns.

Sequential Linear Programming

Sequential linear programming

Linear constraints and a nonlinear objective function together form a special class of nonlinear programs. It is possible to solve a problem of this class by solving a sequence of linear programs. The main requirement is that the nonlinear objective function has first-order derivatives. The objective function can then be linearized around the solution of a previous linear program. By restricting the linearized function to an appropriate finite box, a new solution point is found. The sequence of linear programs terminates when the appropriate box has become sufficiently small. Upon termination, the optimal solution, as last found, is considered to be a local optimum of the underlying nonlinear program.

Procedure in AIMMS

The following procedure illustrates how sequential linear programming can be implemented using matrix manipulation functions. The procedure assumes the existence of finite upper and lower bounds on the variables, and the presence of a function ComputeGradient to compute the required first partial derivatives with respect to the variables in the objective function. To implement the function ComputeGradient one can, for instance, use the built-in GMP function GMP::Solution::GetFirstOrderDerivative (see also Managing the Solution Repository).

linearizedGMP := GMP::Instance::Generate(LinearizedProgram);

BoxWidth(j)  := 0.1 * (x.upper(j) - x.lower(j));
x(j)         := 0.5 * (x.upper(j) + x.lower(j));

while ( max( j, BoxWidth(j) ) > Tolerance ) do
   ObjCoeff(j) := ComputeGradient(x)(j);

   for (j) do
      GMP::Column::SetLowerBound ( linearizedGMP, x(j),
                                   max(x.lower(j), x(j) - 0.5*BoxWidth(j)) );
      GMP::Column::SetUpperBound ( linearizedGMP, x(j),
                                   min(x.upper(j), x(j) + 0.5*BoxWidth(j)) );
      GMP::Coefficient::Set( linearizedGMP, ObjectiveRow,
                             x(j), ObjCoeff(j)            );

   BoxWidth(j) *= ShrinkFactor;