Managing Generated Mathematical Program Instances

Managing math program instances

The procedures and functions of the GMP::Instance namespace are listed in this table and take care of the creation and management of generated mathematical program instances. Mathematical program instances also provide access to the solution repository and solver sessions associated with the instance.

Table 33 : Procedures and functions in the GMP::Instance namespace

Generate(MP, name)\(\to\)AllGeneratedMathematicalPrograms

Copy(GMP, name)\(\to\)AllGeneratedMathematicalPrograms

Rename(GMP, name)

Delete(GMP)

GenerateRobustCounterpart(MP, UncertainParameters, UncertaintyConstraints[, Name])\(\to\)AllGeneratedMathematicalPrograms

GenerateStochasticProgram(MP, StochasticParameters, StochasticVariables, Scenarios, ScenarioProbability, ScenarioTreeMap, RootScenario[, GenerationMode][, Name])\(\to\)AllGeneratedMathematicalPrograms

CreateMasterMIP(GMP, name)\(\to\)AllGeneratedMathematicalPrograms

FixColumns(GMP1, GMP2, solNr, varSet)

AddIntegerEliminationRows(GMP, solNr, refNo)

DeleteIntegerEliminationRows(GMP, refNo)

AddLimitBinaryDeviationRow(GMP, solNr, varSet, deviation[, refNo])

DeleteLimitBinaryDeviationRow(GMP[, refNo])

CreateBlockMatrices(GMP, colSet, blockValue, prefix)\(\to\)AllGeneratedMathematicalPrograms

CreateDual(GMP, name)\(\to\)AllGeneratedMathematicalPrograms

CreateFeasibility(GMP[, name][, useMinMax])\(\to\)AllGeneratedMathematicalPrograms

CreatePresolved(GMP, name)\(\to\)AllGeneratedMathematicalPrograms

GetSymbolicMathematicalProgram(GMP)\(\to\)AllMathematicalPrograms

GetInfeasibleData(GMP, parSet, message[, method][, effort][, textFormat])

GetNumberOfRows(GMP)

GetNumberOfColumns(GMP)

GetNumberOfNonzeros(GMP)

GetDirection(GMP)\(\to\)AllMatrixManipulationDirections

SetDirection(GMP, dir)

GetOptionValue(GMP, OptionName)

SetOptionValue(GMP, OptionName, Value)

CreateProgressCategory(GMP[, Name])\(\to\)AllProgressCategories

GetMathematicalProgrammingType(GMP)\(\to\)AllMathematicalProgrammingTypes

SetMathematicalProgrammingType(GMP, type)

GetSolver(GMP)\(\to\)AllSolvers

SetSolver(GMP, solver)

SetCallbackAddCut(GMP, CB)

SetCallbackAddLazyConstraint(GMP, CB)

SetCallbackBranch(GMP, CB)

SetCallbackCandidate(GMP, CB)

SetCallbackIncumbent(GMP, CB)

SetCallbackStatusChange(GMP, CB)

SetCallbackHeuristic(GMP, CB)

SetCallbackIterations(GMP, CB, nrIters)

SetCallbackTime(GMP, CB)

SetIterationLimit(GMP, nrIters)

SetMemoryLimit(GMP, nrMB)

SetTimeLimit(GMP, nrSeconds)

SetCutoff(GMP, value)

Solve(GMP)

GetObjective(GMP)

GetObjective(GMP)

GetMemoryUsed(GMP)

MemoryStatistics(GMPSet, OutputFileName[, optional-arguments \(\dots\)])

GetColumnNumbers(GMP, varSet)\(\to\)Integers

GetRowNumbers(GMP, conSet)\(\to\)Integers

GetObjectiveColumnNumber(GMP)\(\to\)Integers

GetObjectiveRowNumber(GMP)\(\to\)Integers

DeleteMultiObjectives(GMP)

CreateSolverSession(GMP[, Name][, Solver])\(\to\)AllSolverSessions

DeleteSolverSession(solverSession)

FindApproximatelyFeasibleSolution(GMP, sol1, sol2, nrIter[, maxIter][, feasTol][, moveTol][, imprTol][, maxTime][, useSum][, augIter][, useBest])

Creation of mathematical program instances

New mathematical program instances can be created by calling

All mathematical program instances created through each of these calls, are uniquely represented by elements in the predefined set AllGeneratedMathematicalPrograms. For the functions in the GMP::Instance namespace creating GMPs you can explicitly specify the name of the associated set element to be created. When calling the SOLVE statement, AIMMS will generate an element with the same name as the MathematicalProgram at hand. When the name of the element to be created is already contained in the set AllGeneratedMathematicalPrograms, the mathematical program instance associated with the existing element will be completely replaced by the newly created mathematical program instance.

Special math programming types

Stochastic programming and the use of the function GenerateStochasticProgram is discussed in Solving Stochastic Models. Robust optimization and the use of the function GenerateRobustCounterpart is explained in Solving Robust Optimization Models. The functionality of the CreateDual function is explained in more detail in Dealing with Degeneracy and Non-Uniqueness. The function CreateMasterMIP is used by the AIMMS Outer Approximation solver, which is discussed in full detail in AIMMS Outer Approximation Algorithm for MINLP. Presolving of mathematical programs is discussed in The AIMMS Presolver.

Deleting and renaming instances

Through the procedures GMP::Instance::Delete and GMP::Instance::Rename you can delete and rename mathematical program instances and their associated elements in the set AllGeneratedMathematicalPrograms. If you rename a mathematical program instance to a name that already exists in the set AllGeneratedMathematicalPrograms, the associated mathematical program instance will be deleted prior to renaming.

CLEANDEPENDENTS statement

Note that also the CLEANDEPENDENTS statement may remove mathematical program instances from memory when it affects any constraint or variable referenced by that instance.

Retrieving and setting basic properties

Through the functions

you can retrieve the current value of some basic properties of a mathematical program instance. The number of rows, columns and nonzeros can be changed by manipulating the matrix of the mathematical program instance (see also Matrix Manipulation Procedures). You can use the functions

to modify the optimization direction and mathematical programming type. The type of a mathematical program must be a member of the set MathematicalProgrammingTypes (see also MathematicalProgram Declaration and Attributes) The direction associated with a mathematical program is either

  • 'maximize',

  • 'minimize', or

  • 'none'.

The direction 'none' is the instruction to the solver to find a feasible solution.

Installing callbacks

For each mathematical program instance, you can set up to six callback functions that will be called by any solver session associated with the mathematical program instance at hand. Through the following procedures you can install or uninstall a callback function for a mathematical program instance.

Each of these procedures expects an element of the set AllProcedures, or an empty element " to uninstall the callback.

Callback procedures

Callback procedures for each type of callback should be declared as follows:

AnExampleCallback(solverSession)

where the solverSession argument should be a scalar input element parameter into the set AllSolverSessions. Callback procedures should have a return value of

  • 0, if you want the solver session to stop, or

  • 1, if you want the solver session to continue.

As discussed before, each solver session can be uniquely associated with a single mathematical program instance. You can find this instance by calling the function GMP::SolverSession::GetInstance (see also Using Solver Sessions), and, within the callback procedure, use this instance to get access to its associated properties.

Example

The following example implements a callback procedure for the incumbent callback. The callback procedure finds the associated mathematical program instance, and stores all incumbents reported by the solver into the next solution of the solution repository.

Procedure IncumbentCallBack {
    Arguments  : solvSess;
    Body       : {
        theGMP := GMP::SolverSession::GetInstance( solvSess );
        GMP::Solution::RetrieveFromSolverSession( solvSess, solutionNumber(theGMP) );
        solutionNumber(theGMP) += 1;

        return 1;   ! continue solving
    }
}

Note that the callback procedure uses the GMP::Solution::RetrieveFromSolverSession function (discussed in Managing the Solution Repository) to retrieve the solution from the solver.

Solving mathematical program instances

In contrast to the SOLVE statement, the philosophy behind the GMP library is to break down the optimization functionality in AIMMS to a level which offers optimum support for implementing advanced algorithms around a MathematicalProgram in your model. One of the consequences of this philosophy is that the solution is never directly transferred between the symbolic variables and constraints and the solver, but is intermediately stored in a solution repository. Therefore, solving a MathematicalProgram using the GMP library breaks down into the following basic steps:

  1. generate a mathematical program instance for the MathematicalProgram,

  2. create a solver session for the mathematical program instance,

  3. transfer the initial point from the model to the solution repository,

  4. transfer the initial point from the solution repository to the solver session,

  5. let the solver session solve the problem,

  6. transfer the final solution from the solver session to the solution repository, and

  7. transfer the final solution from the solution repository to the model.

Solving the instance directly

For your convenience, however, the GMP library contains a procedure

which, given a generated mathematical program instance, takes care of all intermediate steps (i.e. steps 2-7) necessary to solve the mathematical program instance. In case you need access to the solution in the solution repository after calling the GMP::Instance::Solve call, you should notice that the GMP::Instance::Solve procedure (as well as the SOLVE statement) performs all of its solution transfer through the fixed solution number 1 in the solution repository.

Emulating the SOLVE statement

The following AIMMS code provides an emulation of the SOLVE statement in terms of GMP::Instance functions.

! Generate an instance of the mathematical program MPid and add
! the element 'MPid' to the set AllGeneratedMathematicalPrograms.
! This element is returned into the element parameter genGMP.
genGMP := GMP::Instance::Generate(MPid, FormatString("%e", MPid));

! Actually solve the problem using the solve procedure for an
! instance (which communicates through solution number 1).
GMP::Instance::Solve(genGMP);

Multistart support

The function FindApproximatelyFeasibleSolution is used by the AIMMS multistart algorithm (see The AIMMS Multistart Algorithm) to compute an approximately feasible solution for an NLP problem. The algorithm used by this function to find the approximately feasible solution is described in [Chi04].

Creating solver sessions

For each generated mathematical program instance, you can explicitly create and delete one or more solver sessions using the following functions:

Once created, you can use the solver session to solve the generated mathematical program

Prior to calling the GMP::SolverSession::Execute or GMP::SolverSession::AsynchronousExecute functions, you should call the function GMP::Solution::SendToSolverSession to initialize the solver session with a solution stored in the solution repository. Using an explicit solver session allows you, for instance, to solve an NLP problem with several initial solutions stored in the solution repository.

Multiple sessions allowed

AIMMS allows you to create multiple solver sessions per mathematical program instance, and solve them in parallel. You can solve multiple mathematical program instances in parallel, by calling the function GMP::SolverSession::AsynchronousExecute multiple times. The function starts a separate thread of execution to solve the math program instance asynchronously, and returns immediately. To solve multiple mathematical program instances in parallel, your computer should have multiple processors or a multi-core processor.

Deleting solver sessions

Once the function GMP::SolverSession::Execute or GMP::SolverSession::AsynchronousExecute has been called, the internal solver representation of the mathematical program instance will be created. The solver representation will only be deleted-and its associated resources freed-when the corresponding solver session has been deleted by calling the function GMP::Instance::DeleteSolverSession.

Implementing the procedure GMP::Instance:: Solve

The GMP:Instance::Solve procedure discussed previously can be emulated using solver sessions, as illustrated in the equivalent code below.

! Create a solver session for genMP, which will create an element
! in the set AllSolverSessions, and assign the newly created element
! to the element parameter session.
session := GMP::Instance::CreateSolverSession(genMP);

! Copy the initial solution from the variables in AIMMS to
! solution number 1 of the generated mathematical program.
GMP::Solution::RetrieveFromModel(genMP,1);

! Send the solution stored in solution 1 to the solver session
GMP::Solution::SendToSolverSession(session, 1);

! Call the solver session to actually solve the problem.
GMP::SolverSession::Execute(session);

! Copy the solution from the solver session into solution 1.
GMP::Solution::RetrieveFromSolverSession(session, 1);

! Store this solution in the AIMMS variables and constraints.
GMP::Solution::SendToModel(genMP, 1);

Setting default solver session limits

You can use the following procedures to set various default limits that apply to all solver sessions created through GMP::Instance::CreateSolverSession.

Setting GMP-specific options

For every GMP you can override the default project options using the function GMP::Instance::SetOptionValue. You can also set options for a specific solver session associated with a GMP through the function GMP::SolverSession::SetOptionValue. In turn, option values set for a specific solver session override the option values for the associated GMP.

Setting the default solver

Similarly, you can get and set the default solver that will be used by all solver sessions created through GMP::Instance::CreateSolverSession.

Outer approximation support

Through the functions

the GMP library offers support for solving mixed integer nonlinear (MINLP) problems using a white box outer approximation approach. The AIMMS Outer Approximation solver is discussed in full detail in AIMMS Outer Approximation Algorithm for MINLP.

Re-optimizing with limited impact on the solution

Imagine you have created a production plan based on optimizing some mathematical program and that something unexpected happened that (partly) ruined the plan. You now have to re-optimize the mathematical program, with some changes, but would like the solution of the new optimization to be close to the previous one. For that you can use the procedure

which adds a constraint that limits the number of binary decision variables of which the solution value is allowed to change. This constraint can be removed using the procedure

Dealing with Degeneracy and Non-Uniqueness

Background

When solving a mathematical program, some practical difficulties may arise when the optimal solution of the underlying model is either degenerate and/or not unique (i.e. there are multiple optimal solutions). These difficulties may concern both the primal and dual solution (i.e. the shadow prices).

Problems with degeneracy

In the case of degeneracy (see also Section 4.2 of the AIMMS Modeling Guide for an explanation), the solution status of one or more variables is “basic at bound”. In the presence of degeneracy, shadow prices are no longer unique, and their interpretation is therefore ambiguous. As a result, if the shadow prices have an economic interpretation in the application, the particular shadow prices found by the solver cannot be presented to the end-user in a meaningful and reliable fashion.

Problems with multiple solutions

In the case of multiple solutions, the situation is even worse. There are multiple optimal bases, and the associated shadow prices differ between these bases (just as with degeneracy). In addition, the solution presented to the end-user is no longer unique, which may raise questions by the end-user as to why a particular solution is presented.

Degeneracy and multiple solutions

Both degeneracy and multiple solutions can occur at the same time, having their combined effect on the non-uniqueness of both the primal and the dual solution (the optimal shadow prices). The following two paragraphs present possible solutions to deal with multiple primal and dual solutions.

Towards a unique primal solution

One way to deal with multiple solutions is to find a new and second objective function specifically designed to deal with eliminating the multiplicity of solutions. This might be accomplished, for instance, by adding new sets of variables and constraints to cap some aspect of the primal model, and the maximum cap could then be minimized. Or perhaps a straightforward modification of the original objective function could become the second auxiliary objective. It is important to note that this second objective function is optimized only after the first objective function is fixed at its previous optimal value and has been added as a constraint.

Implementing primal uniqueness

Using the functionality provided by the GMP library, constructing a second objective function for a mathematical program is a straightforward task:

  • generate and solve the original mathematical program,

  • use the matrix manipulations procedures discussed in Matrix Manipulation Procedures to create a new objective and fix the original one in the associated mathematical program instance,

  • resolve the modified mathematical program instance.

Towards a unique dual solution

In the presence of primal degeneracy and/or multiple primal solutions, it is impossible to influence the selection of shadow prices, as this decision is made by the solver. To give the control back to you as a model developer, the only sensible step is to go directly to the dual formulation, and work with the model expressed in terms of shadow prices. It is then possible to construct a second auxiliary objective function designed to produce economically meaningful shadow prices. Again, it is important to note that this second objective function is optimized only after the original objective function is fixed at the optimal objective function value of the primal model, and has been added as a constraint.

Creating a dual mathematical program instance

To support the procedure for reaching dual uniqueness, the GMP library contains the function

which creates the dual mathematical program instance associated with a given primal mathematical program instance.

Standard dual formulation

For a mathematical program of the form

\[\begin{split}\begin{align} & \text{minimize} & & \sum_i c_ix_i \\ & \text{subject to} & & \sum_i A_{ij}x_i \geq b_j & & \forall j \\ &&& x_i \geq 0 & & \forall i \\ \end{align}\end{split}\]

the dual mathematical program can be formulated as follows

\[\begin{split}\begin{align} & \text{maximize} & & \sum_j b_j\lambda_j \\ & \text{subject to} & & \sum_j A_{ij}\lambda_j \leq c_i & & \forall i \\ &&& \lambda_j \geq 0 & & \forall j \\ \end{align}\end{split}\]

where the \(\lambda_j\) represent the shadow prices of the constraints of the primal formulation.

Sign changes

If the primal formulation contains nonpositive or free variables, or contains \(\leq\) or equality constraints, a number of simple substitution will bring the formulation back into the standard form above, after which the above dual formulation can be used directly. The resulting changes to the dual formulation are as follows:

  • a nonpositive variable \(x_i\) corresponds to a dual \(\geq\) constraint,

  • a free variable \(x_i\) corresponds to a dual equality constraint,

  • a \(\leq\) constraint corresponds to a nonpositive dual variable \(\lambda_j\), and

  • an equality constraint corresponds to a free dual variable \(\lambda_j\).

Bounded variables and ranged constraints

However, such simple transformation are not possible anymore if the primal model contains:

  • bounded variables, i.e. \(l_i \leq x_i \leq u_i\), or

  • ranged constraints, i.e. \(d_i \leq \sum_i A_{ij}x_i \leq b_j\).

In these cases, additional constraints (implicitly) have to be added as follows to satisfy the above standard formulation:

  • \(x_i \geq l_i\) whenever \(l_i \neq 0,-\infty\),

  • \(x_i \leq u_i\) whenever \(u_i \neq 0, \infty\), and

  • \(\sum_i A_{ij}x_i \geq d_j\).

In the generated dual mathematical program, such implicit constraint additions in the primal formulation will lead to the explicit introduction of additional variables in the dual formulation. Such variable additions to the dual formulation are taken care of by AIMMS automatically, but will have consequences when you want to manipulate the matrix of the dual mathematical program instance, as discussed in Modifying an Extended Math Program Instance.

Implementing dual uniqueness

Using the function GMP::Instance::CreateDual, it is relatively straightforward to implement the procedure outlined above to reach dual uniqueness:

  • generate and solve the original mathematical program,

  • generate a dual mathematical program instance from the primal mathematical program instance,

  • use the matrix manipulations procedures discussed in Matrix Manipulation Procedures to create a new dual objective and fix the original dual objective in the newly created dual mathematical program instance,

  • solve the modified dual mathematical program instance.

Explainability

Determining data causing infeasibility

Note

THIS FEATURE IS NOT AVAILABLE (YET) IN ANY OFFICIAL AIMMS RELEASE.

A particular situation which requires explainability is when the mathematical optimization model is formulated correctly, but it becomes infeasible due to incorrect input data provided by the user. So, in this case the infeasibility is not inherent to the model formulation and it is not found as a modeling error during the model development phase, but rather during the model deployment phase due to some incorrect data instance which turns the model infeasible.

Business applications including optimization should also consider infeasibilities and include support for dealing with the infeasibility in this situation. More specifically, some valuable information about the cause of the infeasibility should be returned to the end user in a form which she/he can understand and use for correcting the input data in order to make the model feasible again.

This goal can be achieved by calling the function GMP::Instance::GetInfeasibleData. Under the assumption that an LP/MILP model is correctly formulated, this function performs in essence the following tasks:

  • Calculate IIS or solve Feasibility Problem

  • Remove constraints without changeable parameters

  • Use “reverse generation” to find changeable parameters used in constraints

After performing these steps, the function returns a message (as output argument) and fills the parameter suffix called .SuspicionLevel with one of the possible values: High, Normal, or Low. The output message may be displayed in a suitable way into the graphical user interface in order to inform the user in a concise manner about the most likely cause of the infeasibility.

In turn, the values of the .SuspicionLevel parameter suffixes may be used to assign identifier annotations to the parameters of interest. Such annotations may be subsequently used in order to highlight the suspicious values of those parameters in the graphical user interface and visually notify the user about potentially incorrect data values. For example, when such values are rendered in a table, the cells of the suspicious values may be coloured in light pink, pink, or red, based on the suspicion levels Low, Normal, or High, respectively.

After adjusting the most critical values highlighted in the graphical user interface to more realistic numbers, the user may re-solve the model and observe the effect. If the model turns feasible, then the issue has been resolved/explained. If the model still stays infeasible, then a new call to the function GMP::Instance::GetInfeasibleData may reveal additional information about potentially incorrect data and the process may be repeated in a similar way until the model becomes feasible again. It could happen that a few iterations are required in order to fully explain the cause of the infeasibility and to resolve the issue with the incorrect user data completely.