## ams_version=1.0

Model Delay_Constrained_Routing {
    Comment: {
        "Delay constrained routing
        
        Problem type:
        Convex MINLP (small)
        
        Keywords:
        Outer Approximation, GMP-AOA, lazy constraint callback
        
        Description:
        The Delay-Constrained Routing Problem is a problem in telecommunications.
        Services are routed through a network, from source to destination, such
        that the delay of each service satisfies a certain guarantee. The objective
        is to minimize the total routing cost. This problem is solved using the
        AIMMS Outer Approximation (AOA) algorithm.
        
        References:
        Hijazi, H., P. Bonami, G. Cornuéjols, A. Ouorou, Mixed-integer nonlinear
        programs featuring \"on/off\" constraints, Computational Optimization and
        Applications 52(2) (2012), pp. 537-558."
    }
    Parameter NumberOfArcs {
        Range: integer;
        Definition: 331;
    }
    Parameter NumberOfCommodities {
        Range: integer;
        Definition: 200;
    }
    Parameter NumberOfPaths {
        Range: integer;
        Definition: 2;
    }
    Set Arcs {
        SubsetOf: Integers;
        Index: e;
        Definition: {
            { 1 .. NumberOfArcs }
        }
    }
    Set Commodities {
        SubsetOf: Integers;
        Index: k;
        Definition: {
            { 1 .. NumberOfCommodities }
        }
    }
    Set Paths {
        SubsetOf: Integers;
        Text: "Candidate paths";
        Index: i;
        Definition: {
            { 1 .. NumberOfPaths }
        }
    }
    Parameter PathLimitPerDemand {
        Range: integer;
        Definition: 1;
        Comment: "The maximum authorized number of activated paths per demand.";
    }
    Set Routes {
        IndexDomain: (k,i);
        SubsetOf: Arcs;
    }
    Parameter ArcCost {
        IndexDomain: e;
    }
    Parameter ArcCapacity {
        IndexDomain: e;
    }
    Parameter FlowUpperBound {
        IndexDomain: e;
    }
    Parameter Demand {
        IndexDomain: k;
    }
    Parameter Delay {
        IndexDomain: k;
    }
    Parameter NumberOfCandidatePaths {
        IndexDomain: k;
        Range: integer;
    }
    Variable Flow {
        IndexDomain: e;
        Range: nonnegative;
    }
    Variable DemandFraction {
        IndexDomain: (k,i) | i <= NumberOfCandidatePaths(k);
        Range: [0, 1];
    }
    Variable SelectedPath {
        IndexDomain: (k,i);
        Range: binary;
        Comment: "1, if path (i,k) is activated";
    }
    Variable TotalRoutingCost {
        Definition: sum( e, ArcCost(e)*Flow(e) );
    }
    Constraint DemandSatisfaction {
        IndexDomain: k;
        Definition: sum( i, DemandFraction(k,i) ) >= 1;
        Comment: "The fraction of routed demand must be greater than 1 to guarantee the satisfaction of all demands.";
    }
    Constraint FlowDefinition {
        IndexDomain: e;
        Definition: sum( (k,i) | e in Routes(k,i), Demand(k) * DemandFraction(k,i) ) <= Flow(e);
        Comment: "Flow(e) is defined as the sum of all flows passing through arc e.";
    }
    Constraint CapacityConstraint {
        IndexDomain: e;
        Definition: Flow(e) <= ArcCapacity(e);
        Comment: "The flow is bounded by the capacity installed on the link.";
    }
    Constraint DelayConstraint {
        IndexDomain: (k,i);
        Definition: {
            sum( e | e in Routes(k,i), (SelectedPath(k,i)^2/(SelectedPath(k,i) * ArcCapacity(e) - Flow(e) + (1-SelectedPath(k,i)) * (FlowUpperbound(e) + 0.0001))) )
            <=
            SelectedPath(k,i) * Delay(k)
        }
        Comment: "Convex formulation of \"on/off\" delay constraints. Constraint (9-c) in Hijazi et al. (2012).";
    }
    Constraint PathsLimitConstraint {
        IndexDomain: k;
        Definition: sum( i, SelectedPath(k,i) ) <= PathLimitPerDemand;
        Comment: "Fix the maximum number of active paths per commodity.";
    }
    Constraint PathIndicatorConstraint {
        IndexDomain: (k,i);
        Definition: DemandFraction(k,i) <= SelectedPath(k,i);
    }
    MathematicalProgram DCRP {
        Objective: TotalRoutingCost;
        Direction: minimize;
        Type: MINLP;
    }
    ElementParameter myGMP {
        Range: AllGeneratedMathematicalPrograms;
    }
    Procedure MainInitialization {
        Body: {
            read from file "data.inp";
        }
    }
    Procedure OuterApproximation {
        Body: {
            put GMPOuterApprox::outf;
            
            myGMP := GMP::Instance::Generate( DCRP ) ;
            
            GMPOuterApprox::CreateStatusFile := 1;
            
            ! Mark model as convex. For nonconvex problems parameter 'IsConvex' should be set to 0.
            GMPOuterApprox::IsConvex := 1;
            
            GMPOuterApprox::DoOuterApproximation( myGMP );
            
            putclose;
        }
        Comment: "Solve problem using classic Outer Approximation algorithm.";
    }
    Procedure ConvexOuterApproximation {
        Body: {
            put GMPOuterApprox::outf;
            
            myGMP := GMP::Instance::Generate( DCRP ) ;
            
            GMPOuterApprox::CreateStatusFile := 1;
            
            GMPOuterApprox::DoConvexOuterApproximation( myGMP );
            
            putclose;
        }
        Comment: {
            "Solve problem using modern Outer Approximation algorithm that uses the Lazy Constraints callback
            of CPLEX or GUROBI. The modern algorithm solves only one MIP problem."
        }
    }
    Procedure MainTermination {
        Body: {
            return 1;
        }
    }
    Module GMP_Outer_Approximation_Module {
        SourceFile: "%AIMMSMODULES%\\GMPOuterApproximation.ams";
        Comment: {
            "This module contains two outer approximation algorithms for solving Mixed Integer
            Nonlinear Problems (MINLP). The basic algorithm can be found in the section \'AOA
            Basic Algorithm\' and is based on the following two papers:
            
             M.A. Duran and I.E. Grossmann, An outer-approximation algorithm for a class of
             mixed-integer nonlinear programs, Mathematical Programming 36 (1986), pp. 307-339.
            
             J. Viswanathan and I.E. Grossmann, A combined penalty function and outer-approximation
             method for MINLP optimization, Computers and Chemical Engineering 14 (1990), pp. 769-778.
            
            The basic algorithm can be used for convex and non-convex problems with general integer
            variables.
            
            The section \'AOA Convex Algorithm\' contains a variant of the outer approximation algorithm
            that uses a single tree search. In this way the sequential solving of several MIP\'s is
            avoided. The algorithm is based on the paper:
            
             I. Quesada and I.E. Grossmann, An LP/NLP Based Branch and Bound Algorithm for Convex MINLP
             Optimization Problems, Computers and Chemical Engineering 16 (1992), pp. 937-947.
            
            This algorithm can only be used for convex problems (with general integer variables)."
        }
    }
}