Matrix Manipulation Procedures

Matrix manipulation

The matrix manipulation procedures in the GMP library allow you to implement efficient algorithms for generated mathematical program instances which require only slight modifications of the matrix associated with the mathematical program instance during successive runs. These procedures operate directly on the coefficient matrix underlying the mathematical program, and thus avoid the constraint-generation process normally initiated by the SOLVE statement after input data has been modified.

This section

Prior to discussing the individual matrix manipulation procedures, the following section will provide some motivation when and when not to use matrix manipulation.

When to Use Matrix Manipulation

When to use matrix manipulation

Even though AIMMS offers a library of matrix manipulation procedures, you should not use them blindly. As explained below, it is important to distinguish between manual and automatic input data changes inside an AIMMS application. Your decision whether or not to use the matrix manipulation procedures described in this section, should depend on this distinction.

Manual data input …

Consider an end-user of an AIMMS application who, after having looked at the results of a mathematical program, wants to make changes in the input data and then look again at the new solution of the mathematical program. The effect of the data changes on the input to the solver cannot be predicted in advance. Even a single data change could lead to multiple changes in the input to the solver, and could also cause a change in the number of constraints and variables inside the particular mathematical program.

…requires structure recognition

As a result, AIMMS has to determine whether or not the structure of the underlying mathematical program has changed. Only then can AIMMS decide whether the value of existing coefficients can be overwritten, or whether a new and structurally different data set has to be provided to the solver. This structure recognition step is time consuming, and cannot be avoided in the absence of any further information concerning the changes in input data.

Automatic data input …

Whenever input data are changed inside an AIMMS procedure, their effect on the input to the solver can usually be determined in advance. This effect may be nontrivial, in which case it is not worth the effort to establish the consequences. Rather, letting AIMMS perform the required structure recognition step through the regular SOLVE statement before passing new information to the solver seems to be a better remedy. There are several instances, however, in which the effect of data changes on the solver input data is easy to determine.

…may reflect particular structure

Consider, for instance, automatic data changes that have a one-to-one correspondence with values in the underlying mathematical program. In these instances, the incidence of variables in constraints is not modified, and only the replacement values of some coefficients need to be supplied to the particular solver. Other examples include automatic data changes that could create new values for particular variable-constraint combinations, or that could even cause new constraints or variables to be added to the input of the solver. In all these instances, the exact effects on the input of the solver can easily be determined in advance, and there is no need to let AIMMS perform of the computationally intensive structure recognition step of the SOLVE statement before passing new information to the solver.

Restrictions on usage

The above effects of data input modifications on the input to the solver are straightforward to implement with linear and quadratic mathematical programs, because the underlying data structures are matrices with rows, columns and nonzero elements. The input data structures for nonlinear mathematical programs are essentially nonlinear expressions. Modifications of the type discussed in the previous paragraph are not easily passed onto these nonlinear data structures. For this reason, the efficient updating of solver input has been confined to

  • linear and quadratic constraints, and

  • coefficients of nonlinear constraints with respect to variables that only occur linearly in that constraint.

Regeneration of nonlinear constraints

Whenever the input data of a nonlinear expression in a nonlinear constraint has changed, it is not possible anymore to change the nonlinear expression used by the solver directly to reflect the data change. You can still request AIMMS to regenerate the entire row, which will then use the updated inputs. You should note, however, that any modifications to the linear part of the regenerated constraint are lost after the constraint has been regenerated.

Scalar arguments only

All matrix procedures listed in this table-this table and most procedures listed in this table have scalar-valued arguments. The row argument should always be

  • a scalar reference to an existing constraint name in your model, or

  • a row number which is an integer in the range \(\{ 0 .. m-1 \}\) whereby \(m\) is the number of rows.

The column argument should always be

  • a scalar reference to an existing variable name in your model, or

  • a column number which is an integer in the range \(\{ 0 .. n-1 \}\) whereby \(n\) is the number of columns.

Modifying a group of columns or rows

For most matrix procedures listed in this table-this table, that can be used to modify a generated mathematical program, there also exists a multi variant which can be applied to a group of columns of rows, belonging to one variable or constraint respectively. These procedures are listed in More Efficient Modification Procedures.

Mathematical program instance required

Before you can apply any of the procedures of this table-this table, you must first create a mathematical program instance using any of the functions for this purpose discussed in Managing Generated Mathematical Program Instances. Either of these methods will set up the initial row-column matrix required by the matrix manipulation procedures. Also, any row or column referenced in the matrix manipulation procedures must either have been generated during the initial generation step, or must have been generated later on by a call to the procedures GMP::Row::Add, or GMP::Column::Add, respectively.

Coefficient Modification Procedures

Coefficient modification procedures

The procedures and functions of the GMP::Coefficient namespace are listed in this table and take care of the modification of coefficients in the matrix and objective of a generated mathematical program instance.

Table 34 : GMP::Coefficient routines

Get(GMP, row, column)

GetMinAndMax(GMP, rowSet, colSet, minCoef, maxCoef[, absSense])

Set(GMP, row, column, value)

GetQuadratic(GMP, column1, column2)

SetQuadratic(GMP, column1, column2, value)

Modifying coefficients

You can instruct AIMMS to modify any particular coefficient in a matrix by specifying the corresponding row and column (in AIMMS notation), together with the new value of that coefficient, as arguments of the procedure GMP::Coefficient::Set. This procedure can also be used when a value for the coefficient does not exist prior to calling the procedure.

Quadratic coefficients

For quadratic mathematical programs, you can modify the quadratic objective coefficients by applying the function GMP::Coefficient::SetQuadratic to the objective row. For every two columns \(x_1\) and \(x_2\) you can specify the modified coefficient \(c_{12}\) if \(c_{12}x_1x_2\) is to be part of the quadratic objective.

Quadratic Coefficient Modification Procedures

Quadratic coefficient modification procedures

The procedures and functions of the GMP::QuadraticCoefficient namespace are listed in this table and take care of the modification of coefficients of quadratic rows in the matrix other than the objective of a generated mathematical program instance.

Table 35 : GMP::QuadraticCoefficient routines

Get(GMP, row, column1, column2)

Set(GMP, row, column1, column2, value)

Modifying coefficients

You can instruct AIMMS to modify any particular quadratic coefficient in a matrix by specifying the corresponding row and columns (in AIMMS notation), together with the new value of that coefficient, as arguments of the procedure GMP::QuadraticCoefficient::Set. This procedure can also be used when a value for the quadratic coefficient does not exist prior to calling the procedure.

Row Modification Procedures

Row modification procedures

The procedures and functions of the GMP::Row namespace are listed in this table and take care of the modification of properties of existing rows and the creation of new rows.

Table 36 : GMP::Row routines

Add(GMP, row)

Delete(GMP, row)

Activate(GMP, row)

Deactivate(GMP, row)

Generate(GMP, row)

GetLeftHandSide(GMP, row)

SetLeftHandSide(GMP, row, value)

GetRightHandSide(GMP, row)

SetRightHandSide(GMP, row, value)

GetType(GMP, row) \(\to\) AllRowTypes

SetType(GMP, row, type)

GetStatus(GMP, row) \(\to\) AllRowColumnStatuses

GetIndicatorColumn(GMP, row)

DeleteIndicatorCondition(GMP, row)

GetIndicatorCondition(GMP, row)

SetIndicatorCondition(GMP, row, column, value)

GetConvex(GMP, row)

SetConvex(GMP, row, value)

GetRelaxationOnly(GMP, row)

SetRelaxationOnly(GMP, row, value)

SetPoolType(GMP, row, value[, mode])

Row types

The row type refers to one of the four possibilities:

  • '<=',

  • '=',

  • '>=', and

  • 'ranged'

You are free to change this type for each row. Deactivating and subsequently reactivating a row are instructions to the solver to ignore the row as part of the underlying mathematical program and then reconsider the row again as an active row.

Row generation

When you add a new row to a matrix using GMP::Row::Add, the newly added row will initially only have any zero coefficients, regardless of whether the corresponding AIMMS constraint had a definition or not. Through the procedure GMP::Row::Generate you can tell AIMMS to discard the current contents of a row in the matrix, and insert the coefficients as they follow from the definition of the corresponding constraint in your model.

Indicator conditions

When you are using the CPLEX, Gurobi or ODH-CPLEX solver, you can declaratively specify indicator constraints through the IndicatorConstraint property of a constraint declaration (see Indicator Constraints, Lazy Constraints and Cut Pools). You can also set and delete indicator constraints programmatically for a given GMP using the functions GMP::Row::SetIndicatorCondition and GMP::Row::DeleteIndicatorCondition

Lazy and cut pool constraints

When you are using the CPLEX, Gurobi or ODH-CPLEX solver, you can declaratively specify constraints to be part of a pool of lazy constraints or cuts through the IncludeInLazyConstraintPool and IncludeInCutPool properties of a constraint declaration respectively (see Indicator Constraints, Lazy Constraints and Cut Pools). You can also specify lazy and cut pool constraints programmatically for a given GMP using the function GMP::Row::SetPoolType.

Convex and relaxation-only constraints

Through the .Convex and .RelaxationOnly suffices of constraints you can set special constraint properties for the BARON global optimization solver (see also Constraint Suffices for Global Optimization). For a given GMP you can also set these constraint properties programmatically using the GMP::Row::SetConvex and GMP::Row::SetRelaxationOnly functions.

Column Modification Procedures

The procedures and functions of the GMP::Column namespace are listed in this table and take care of the modification of properties of existing columns and the creation of new columns.

Table 37 : GMP::Column routines

Add(GMP, column)

Delete(GMP, column)

Freeze(GMP, column, value)

Unfreeze(GMP, column)

GetLowerBound(GMP, column)

SetLowerBound(GMP, column, value)

GetUpperBound(GMP, column)

SetUpperBound(GMP, column, value)

GetType(GMP, column) \(\to\) AllColumnTypes

SetType(GMP, column, type)

GetStatus(GMP, column) \(\to\) AllRowColumnStatuses

SetDecomposition(GMP, column, value)

SetAsObjective(GMP, column)

SetAsMultiObjective(GMP, column, priority, weight)

Column types

The column type refers to one of the three possibilities:

  • 'integer',

  • 'continuous', and

  • 'semi-continuous'.

You are free to specify a different type for each column. For newly added columns, AIMMS will (initially) use the lower bound, upper bound and column type as specified in the declaration of the (symbolic) variable associated with the added column. Freezing a column and subsequently unfreezing it are instructions to the solver to fix the corresponding variable to its current value, and then free it again by letting it vary between its bounds.

Changing the objective column

If you want to implement the procedures for reaching primal or dual uniqueness as described in Dealing with Degeneracy and Non-Uniqueness, you can use the procedure

to change the objective function used by either the primal or dual mathematical program instance that you want to solve for a second time. Notice that the defining constraint for this variable should be

  • part of the original mathematical program formulation for which AIMMS has generated a mathematical program instance, or

  • added later on to the primal or dual generated mathematical program instance using the GMP::Row::Add procedure, where the row definition is generated by AIMMS through the GMP::Row::Generate procedure or constructed explicitly through several calls to the GMP::Coefficient::Set procedure.

More Efficient Modification Procedures

If you want to change the data of many columns or rows belonging to some variable or constraint then it is more efficient to use the multi variant of a modification procedure. The available multi procedures of the GMP namespace are listed in this table.

Table 38 : Multi procedures

Coefficient::SetMulti(GMP, binding, row, column, value)

Column::AddMulti(GMP, binding, column)

Column::DeleteMulti(GMP, binding, column)

Column::FreezeMulti(GMP, binding, column, value)

Column::UnfreezeMulti(GMP, binding, column)

Column::SetLowerBoundMulti(GMP, binding, column, value)

Column::SetUpperBoundMulti(GMP, binding, column, value)

Column::SetTypeMulti(GMP, binding, column, type)

Column::SetDecompositionMulti(GMP, binding, column, value)

Row::AddMulti(GMP, binding, row)

Row::DeleteMulti(GMP, binding, row)

Row::GenerateMulti(GMP, binding, row)

Row::ActivateMulti(GMP, binding, row)

Row::DeactivateMulti(GMP, binding, row)

Row::SetRightHandSideMulti(GMP, binding, row, value)

Row::SetTypeMulti(GMP, binding, row, type)

Row::SetPoolTypeMulti(GMP, binding, row, value, mode)

Binding argument

All procedures in this table contain an index binding argument. The index binding argument specifies which columns or rows will be modified. If the procedure contains a value argument then the size of this vector is defined by the index binding argument. Further information on index binding can be found in Index Binding.

Alternative procedures

An alternative approach to change or retrieve the data of multiple columns or rows is using the raw procedures, of the GMP namespace, mentioned in this table.

Table 39 : Raw procedures

Coefficient::GetRaw(GMP, rowSet, colSet, coef)

Coefficient::SetRaw(GMP, rowSet, colSet, coef, changeZero)

Column::DeleteRaw(GMP, colSet)

Column::FreezeRaw(GMP, colSet, value)

Column::UnfreezeRaw(GMP, colSet)

Column::GetLowerBoundRaw(GMP, colSet, lbs)

Column::SetLowerBoundRaw(GMP, colSet, value)

Column::GetUpperBoundRaw(GMP, colSet, ubs)

Column::SetUpperBoundRaw(GMP, colSet, value)

Column::SetTypeRaw(GMP, colSet, type)

Row::DeleteRaw(GMP, rowSet)

Row::ActivateRaw(GMP, rowSet)

Row::DeactivateRaw(GMP, rowSet)

Row::GetRightHandSideRaw(GMP, rowSet, rhs)

Row::SetRightHandSideRaw(GMP, rowSet, value)

Row::SetTypeRaw(GMP, rowSet, type)

These procedures use a set of column and/or row numbers as input. These sets of column and row numbers can be obtained by using the functions

respectively.

Modifying an Extended Math Program Instance

Extended math program instances

To use the matrix manipulation routines of the GMP library, you must be able to associate every row and column of the matrix of the math program instance you want to manipulate with a symbolic constraint or variable within your model. However, some routines in the GMP library generate rows and columns that cannot be directly associated with specific symbolic constraints and variables in your model. Examples of such routines are:

The rows and columns generated by these procedures can, however, be indirectly associated with symbolic constraints, variables or mathematical programs, as will be explained below.

Extended suffices

To support the use of the matrix manipulation routines in conjunction with rows and columns generated by AIMMS that can only be indirectly associated with symbolic identifers in the model, AIMMS provides the following suffices which allow you to do so:

These suffices are supported for Variables, Constraints and MathematicalPrograms. They behave like variables and constraints, which implies that it is possible to refer to the .ReducedCost and .ShadowPrice suffices of these extended suffices to get hold of their sensitivity information.

Suffix dimensions

Each of the suffices listed above has one additional dimension compared to the dimension of the original identifier, over the predefined set AllGMPExtensions. For example, assuming that ae is an index into the set AllGMPExtensions,

  • if z(i,j) is a variable or constrain, the .ExtendedVariable suffix will have indices z.ExtendedVariable(ae,i,j),

  • if mp is a mathematical program, the .ExtendedConstraint suffix will have indices mp.ExtendedConstraint(ae).

Each of the procedures listed above, will add elements to the set AllGMPExtensions as necessary. The names of the precise elements added to the set is explained below in more detail.

Suffices generated by CreateDual

The procedure GMP::Instance::CreateDual will add the following elements to the set AllGMPExtensions:

  • DualObjective, DualDefinition, DualUpperBound, DualLowerBound.

In addition, it will generate the following extended variables and constraints

  • For the mathematical program mp at hand

    • the variable mp.ExtendedVariable('DualDefinition'),

    • the constraint mp.ExtendedConstraint('DualObjective').

  • For every ranged constraint c(i)

    • the constraint c.ExtendedConstraint('DualLowerBound',i),

    • the constraint c.ExtendedConstraint('DualUpperBound' i).

  • For every bounded variable x(i) in \([l_i,u_i]\)

    • the constraint x.ExtendedConstraint('DualLowerBound',i)
      (if \(l_i\neq 0,-\infty\)),
    • the constraint x.ExtendedConstraint('DualUpperBound' i)
      (if \(u_i\neq 0, \infty\)).

Modifying the dual math program

Using the matrix manipulation procedures, you can modify the matrix or objective associated with a dual mathematical program instance created by calling the procedure GMP::Instance::CreateDual. Below you will find how you can access the rows and columns of a dual mathematical program instance created by AIMMS.

Row and column names

For each procedure in the GMP::Coefficient, GMP::Row and GMP::Column namespaces you must refer to a scalar constraint and/or variable reference from your symbolic model. For the dual formulation, you must

  • use the symbolic primal constraint name, to refer to the dual shadow price variable associated with that constraint in the dual mathematical program instance, and

  • use the symbolic primal variable name, to refer to the dual constraint associated with that variable in the dual mathematical program instance.

In other words, when modifying matrix coefficients, rows or columns the role of the symbolic constraints and variables is interchanged.

Implicitly added variables and constraints

You can refer to the implicitly added variables and constraints in the procedures of the GMP::Coefficient, GMP::Row and GMP::Column namespaces through the .ExtendedVariable and .ExtendedConstraint suffices described above. After solving the dual math program, AIMMS will store the dual solution in the suffices .ExtendedVariable.ReducedCost and .ExtendedConstraint.ShadowPrice, respectively.

Extended suffices for linearization

By calling the procedures GMP::Linearization::Add or GMP::Linearization::AddSingle, AIMMS will add the linearization for a single nonlinear constraint instance, or for all nonlinear constraints from a set of nonlinear constraints to a given math program instance. When doing so, AIMMS will add an element Linearization\(k\) (where \(k\) is a counter) to the set AllGMPExtensions, and will create for each nonlinear constraint c(i)

  • a constraint c.ExtendedConstraint('Linearization\(k\)',i), and

  • a variable c.ExtendedVariable('Linearization\(k\)',i) if deviations from the constraint are permitted (see also Creating and Managing Linearizations).

Elimination constraints and variables

By calling the procedure GMP::Instance::AddIntegerEliminationRows, AIMMS will add one or more constraints and variables to a math program instance, which will eliminate the current integer solution from the math program instance. When called, AIMMS will add elements of the form

  • Elimination\(k\),

  • EliminationLowerBound\(k\), and

  • EliminationUpperBound\(k\)

to the set AllGMPExtensions. In addition, AIMMS will add

  • a constraint mp.ExtendedConstraint('Elimination\(k\)') to exclude current solution for all binary variables from the math program mp at hand, and

  • for every integer variable c(i) with a level value between its bounds the variables and constraints

    • c.ExtendedVariable('Elimination\(k\)',i),

    • c.ExtendedVariable('EliminationLowerBound\(k\)',i),

    • c.ExtendedVariable('EliminationUpperBound\(k\)',i),

    • c.ExtendedConstraint('Elimination\(k\)',i),

    • c.ExtendedConstraint('EliminationLowerBound\(k\)',i), and

    • c.ExtendedConstraint('EliminationUpperBound\(k\)',i).

Constraints for limiting deviation

By calling the procedure GMP::Instance::AddLimitBinaryDeviationRow, AIMMS will add one constraint to a math program instance, which limits the number of binary variables of which the solution value is allowed to change. When called, AIMMS will add an element of the form

  • Deviation\(k\)

to the set AllGMPExtensions. In addition, AIMMS will add

  • a constraint mp.ExtendedConstraint('Deviation\(k\)') to limit the number of binary variables from the math program mp at hand of which the solution value is allowed to change.