A First and Basic Implementation

Calling the AOA algorithm

To call the AOA algorithm, the GMP library is used to generate a number of math program instances, and associated solver sessions, where SymbolicMP is the symbolic mathematical program containing the MINLP model.

! Generate the MINLP model.
GMINLP := GMP::Instance::Generate(SymbolicMP, FormatString("%e", SymbolicMP)) ;

! Create NLP subproblem.
GNLP := GMP::Instance::Copy( GMINLP, 'OA_NLP' ) ;
GMP::Instance::SetMathematicalProgrammingType( GNLP, 'RMINLP' ) ;
ssNLP := GMP::Instance::CreateSolverSession( GNLP ) ;

! Create Master MIP problem.
GMIP := GMP::Instance::CreateMasterMip( GMINLP, 'OA_MasterMIP' ) ;
ssMIP := GMP::Instance::CreateSolverSession( GMIP ) ;

BasicAlgorithm;

The basic algorithm outlined above is available in the GMP Outer Approximation module as the procedure DoOuterApproximation.

The basic algorithm

The basic algorithm is straightforward, and makes a call to five other procedures that execute the various algorithm steps. The naming convention is self-explanatory, and the following lines make up this first example of a main procedure. For the sake of brevity and clarity, the parts of the code used to create a status file and to customize the contents of the progress window have been left out. They can be found in the basic implementation of the AOA algorithm in the AOA module.

InitializeAlgorithm;
SolveRelaxedMINLP;

while ( not MINLPAlgorithmHasFinished ) do
    AddLinearizationsAndSolveMasterMIP;
    FixIntegerVariablesAndSolveNLP;
    TerminateOrPrepareForNextIteration;
endwhile;

Note that the scalar parameter MINLPAlgorithmHasFinished must be initially set to zero, and should only get a nonzero value when the algorithm is ready to terminate.

InitializeAlgorithm

The following procedure is used to set all algorithmic parameters and options, and to prepare the status file and progress window output.

IterationCount                := 0 ;
LinearizationCount            := 1 ;
EliminationCount              := 1 ;
IncumbentSolutionHasBeenFound := 0 ;
MINLPAlgorithmHasFinished     := 0 ;

if ( NLPUseInitialValues ) then
    GMP::Solution::RetrieveFromModel( GNLP, SolNumbInitialValues ) ;
endif;

if ( GMP::Instance::GetDirection( GMINLP ) = 'maximize' ) then
    MINLPOptimizationDirection := 1;
else
    MINLPOptimizationDirection := -1;
endif;

GMP::Solution::SetProgramStatus( GMINLP, SolNumb, 'ProgramNotSolved' ) ;
GMP::Solution::SetSolverStatus( GMINLP, SolNumb, 'Unknown' ) ;

! The marginals of the NLP solver are needed.
option always_store_marginals := 'On';

The algorithmic parameters are initially set such that the AOA algorithm will always select the original initial values (i.e. the values of the variables prior to starting the AOA algorithm) as the starting values for each NLP subproblem to be solved. This setting has found to work quite well in extensive tests performed using this algorithm.

MINLPTerminate

The following termination procedure is used in several of the procedures that are described later.

if ( IncumbentSolutionHasBeenFound ) then
    GMP::Solution::SetProgramStatus( GMINLP, SolNumb, 'LocallyOptimal' ) ;
    GMP::Solution::SetSolverStatus( GMINLP, SolNumb, 'NormalCompletion' ) ;
else
    GMP::Solution::SetProgramStatus( GMINLP, SolNumb, 'LocallyInfeasible' ) ;
    GMP::Solution::SetSolverStatus( GMINLP, SolNumb, 'NormalCompletion' ) ;
endif;

GMP::Solution::SendToModel( GMINLP, SolNumb ) ;
MINLPAlgorithmHasFinished := 1 ;

The parameter IncumbentSolutionHasBeenFound contains a value of one or zero depending on whether the AOA algorithm has received an incumbent solution to the original MINLP model. Such a solution may be found when solving the NLP subproblem, and this must then be communicated to the AOA algorithm. Note that you also need to set the program status and indicate when the MINLP algorithm has finished.

SolveRelaxedMINLP

The first model that is solved during the algorithm is the relaxed MINLP model. All integer variables are relaxed to continuous variables. The following procedure implements this first solution step of the outer approximation algorithm.

SolveNLPSubProblem( 1 );
ProgramStatus := GMP::Solution::GetProgramStatus( GNLP, SolNumb ) ;

if ( ProgramStatus in NLPOptimalityStatus ) then
    ! Save NLP solution as MINLP solution if an integer solution has been found.

    if ( GMP::Solution::IsInteger( GNLP, SolNumb ) ) then

        ! Set incumbent solution for MINLP.
        GMP::Solution::RetrieveFromModel( GMINLP, SolNumb ) ;
        IncumbentSolutionHasBeenFound := 1 ;

        if ( TerminateAfterFirstNLPIsInteger ) then
            ! Terminate if an integer solution has been found.

            MINLPTerminate;
        endif;
    endif;
else
    ! Terminate if no linearization point has been found.

    SolverStatus := GMP::Solution::GetSolverStatus( GNLP, SolNumb ) ;

    if not ( SolverStatus in NLPContinuationStatus ) then
        MINLPTerminate;
    endif;
endif ;

IterationCount += 1 ;
GMP::Solution::SetIterationCount( GMINLP, SolNumb, IterationCount ) ;

When the procedure SolveNLPSubProblem has terminated, the AOA algorithm has typically found a point for the linearization step. The exception being when the NLP solver does not produce a solution at all (either feasible or infeasible). In such a situation the outer approximating algorithm should be terminated. Note that in the special event that the solution is feasible and has integer values for the integer variables, a locally optimal solution has been found and the AOA algorithm is instructed accordingly. Otherwise, the next step of the outer approximation algorithm can be executed.

AddLinearizationsAndSolveMasterMIP

If a termination flag has not been set, the following procedure adds linearizations to the master MIP problem prior to solving it. If this model becomes infeasible, the outer approximation algorithm will be terminated.

return when ( MINLPAlgorithmHasFinished );

GMP::Linearization::Add( GMIP, GNLP, SolNumb, AllNonLinearConstraints,
                         DeviationsPermitted, PenaltyMultiplier,
                         LinearizationCount, JacobianTolerance ) ;

LinearizationCount += 1 ;

GMP::SolverSession::Execute( ssMIP ) ;

GMP::Solution::RetrieveFromSolverSession( ssMIP, SolNumb ) ;
GMP::Solution::SendToModel( GMIP, SolNumb ) ;

ProgramStatus := GMP::Solution::GetProgramStatus( GMIP, SolNumb ) ;

if not ( ProgramStatus in MIPOptimalityStatus ) then
    MINLPTerminate;
endif ;

The AIMMS parameters DeviationsPermitted and PenaltyMultiplier are part of the AOA module. By default, deviations are allowed and are penalized with the value 1000 in the objective function of the master MIP.

FixIntegerVariablesAndSolveNLP

The following procedure implements the next major step of the outer approximation algorithm. First, the NLP subproblem is solved after fixing all the integer variables in the MINLP model using the values found from solving the previous master MIP problem. Then, if the combination of integer values and feasible NLP solution values improves the current MINLP incumbent solution, a new incumbent solution is set. When the NLP subproblem does not produce a solution (either feasible or infeasible), the outer approximation algorithm will be terminated.

return when ( MINLPAlgorithmHasFinished );

SolveNLPSubProblem( 0 );
ProgramStatus := GMP::Solution::GetProgramStatus( GNLP, SolNumb ) ;

if ( ProgramStatus in NLPOptimalityStatus ) then
    ! Save NLP solution as MINLP solution if no incumbent solution
    ! has been found yet, or if the NLP solution is better than
    ! the current incumbent.

    if ( not IncumbentSolutionHasBeenFound ) then
        ! Set incumbent solution for MINLP.

        GMP::Solution::RetrieveFromModel( GMINLP, SolNumb ) ;
        IncumbentSolutionHasBeenFound := 1 ;
    else

        NLPobjectiveValue   := GMP::Solution::GetObjective( GNLP  , SolNumb ) ;
        MINLPIncumbentValue := GMP::Solution::GetObjective( GMINLP, SolNumb ) ;

        if ( MINLPSolutionImprovement( NLPobjectiveValue, MINLPIncumbentValue ) ) then
            ! Set incumbent solution for MINLP.

            GMP::Solution::RetrieveFromModel( GMINLP, SolNumb ) ;
            IncumbentSolutionHasBeenFound := 1 ;
        endif;
    endif ;
else
    ! Terminate if no linearization point has been found.

    SolverStatus := GMP::Solution::GetSolverStatus( GNLP, SolNumb ) ;

    if not ( SolverStatus in NLPContinuationStatus ) then
        MINLPTerminate;
    endif;
endif ;

The AOA algorithm maintains the MINLP problem, the master MIP problem, the NLP subproblem, and the incumbent solution of the MINLP. As a result, direct access to the corresponding objective function values is available.

SolveNLPSubProblem

The procedure SolveNLPSubProblem solves the NLP subproblem using various routines from the GMP library. The procedure has a single argument initialSolve which indicates whether this is the solve of the initial relaxed MINLP problem. In that case some steps in the procedure are not necessary.

if ( NLPUseInitialValues ) then
    GMP::Solution::SendToModel( GNLP, SolNumbInitialValues ) ;
elseif ( not initialSolve ) then
    GMP::Solution::SendToModel( GMIP, SolNumb ) ;
endif;

GMP::Solution::RetrieveFromModel( GNLP, SolNumb ) ;
GMP::Solution::SendToSolverSession( ssNLP, SolNumb ) ;

if ( not initialSolve ) then
    GMP::Instance::FixColumns( GNLP, GMIP, SolNumb, AllIntegerVariables ) ;
endif;

GMP::SolverSession::Execute( ssNLP ) ;

GMP::Solution::RetrieveFromSolverSession( ssNLP, SolNumb ) ;
GMP::Solution::SendToModel( GNLP, SolNumb ) ;

TerminateOrPrepareForNextIteration

The following procedure implements the final major step of the outer approximation algorithm. If a termination flag has not been set previously, and the maximum number of iterations has not yet been reached, then the previously found integer solution of the master MIP problem will be eliminated by adding the appropriate cuts. This will ensure that the next master MIP will have a new integer solution (or none at all).

return when ( MINLPAlgorithmHasFinished );

if ( IterationCount = IterationMax ) then
    MINLPTerminate;
else
    ! Prepare for next iteration

    IterationCount += 1 ;
    GMP::Solution::SetIterationCount( GMINLP, SolNumb, IterationCount ) ;
    GMP::Instance::AddIntegerEliminationRows( GMIP, SolNumb, EliminationCount ) ;
    EliminationCount += 1 ;
endif ;

Note that you are responsible for determining the appropriate iteration count for the overall outer approximation algorithm. As you are free to develop a solution algorithm in any way you desire, it is not always possible for the AOA algorithm to determine the correct setting of the MINLP iteration count.

A First and Basic Implementation

Docs

Product

Support