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) );
endfor;
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,
ResourceConstraint(SelectedResource),
ActivityVariable(SelectedActivity),
OriginalCoefficient + Delta(n) );
GMP::Instance::Solve( myGMP );
ObjectiveValue(n) := GMP::Solution::GetObjective(myGMP, 1);
endfor;
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 );
repeat
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 );
endif;
GMP::Instance::Solve( relaxedGMP );
endrepeat;
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) );
endfor;
GMP::Instance::Solve( cuttingStockGMP );
for ( width ) do
GMP::Coefficient::Set( GMP : findPatternGMP,
row : PatternContribution,
column: CutsInPattern(width),
value : MeetCutDemand(width).ShadowPrice );
endfor;
GMP::Instance::Solve( findPatternGMP );
endwhile;
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);
GMP::Instance::Solve(linearizedGMP);
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) );
endfor;
GMP::Instance::Solve(linearizedGMP);
BoxWidth(j) *= ShrinkFactor;
endwhile;