Decision Optimization

Decision Optimization

Delivers prescriptive analytics capabilities and decision intelligence to improve decision-making.

 View Only

  • 1.  Lazy Constraint Callback freezing

    Posted Mon November 05, 2018 10:52 AM

    Originally posted by: rsbeigi


    I was trying to add subtour elimination constraints through lazy constraint callback for a routing problem. I use CPLEX 12.8 on Ubuntu 18.04 with C++. Some problem instances are solved without any issues. However, I have come across an instance in which after around one hour CPLEX just freezes (at some point, everything just stops even printing commands without throwing an error). I tried my best to debug the code but it seems to be very strange. Here is the contents of my Lazy callback:

     

    ILOLAZYCONSTRAINTCALLBACK0(LazyCallback)
    {
        
        if (hasIncumbent())
        {
            cout << endl << endl << "UB=" << getIncumbentObjValue() << endl << endl ;
        }
    for( int s = 0 ; s < M ; s++ )
        {
            for ( int k = 0 ; k < K1[s] ; k++ )
            {
                cout << "\n\nVehicle: " << k+1 << "\n\n" ;
                vector <int> A, B ;
                vector <int> VISIT ;
                for(int i = 0 ; i < N ; i++ )
                {
                    if (getValue (V1[i][s][k]) > EPSILON)
                    {
                        VISIT.push_back(i) ;
                        cout << endl << "V1(" << i+1 << ")(" << k+1 << ")=" << getValue (V1[i][s][k]) ;
                    }
                }
                int v_size = VISIT.size() ;
                cout << endl << "|V|=" << v_size << endl ;
                if (v_size == 0) // if vehicle k is not used, vehicle k+1 will not be used
                {
                    break ;
                }
                if (v_size <= 3) // if vehicle k visits 3 nodes (or less), definitely no subtour exists.
                {
                    continue ;
                }
                Graph <double> G(v_size) ;
                vector <double> MAX_FLOW (v_size,0) ;
                for(int i = 0 ; i < v_size ; i++ )
                {
                    for(int j = 0 ; j < v_size ; j++ )
                    {
                        if (i != j)
                        {
                            double val = getValue (U1[ VISIT[i] ][ VISIT[j] ][s][k]) ;
                            if (val > EPSILON)
                            {
                                G.addEdge(i, j, val) ;
                                cout << endl << "U1(" << VISIT[i]+1 << ")(" << VISIT[j]+1 << ")(" << k+1 << ")=" << val ;
                            }
                        }
                    }
                }
                double min_max_flow = IloInfinity ;
                double val ;
                MAX_FLOW[0] = IloInfinity ;
                for(int i = 1 ; i < v_size ; i++ ) // Note that we start from i=1
                {
                    val = G.DinicMaxflow(0, i) ;
                    MAX_FLOW[i] = val ;
                    if (val < min_max_flow)
                    min_max_flow = val ;
                }
                if (1-min_max_flow < EPSILON) // no subtour found
                {
                    continue ;
                }
                cout << "\n\nMaxFlow:" ;
    for(int i = 0 ; i < v_size ; i++ )
                {
    cout << endl << VISIT[i]+1 << ' ' << MAX_FLOW[i] ;
                    if (MAX_FLOW[i] - min_max_flow < EPSILON)
                    {
                        B.push_back(i) ;
                    }
                    else
                    {
                        A.push_back(i) ;
                    }
                }
                ////////////////////////////////////////////////////
                cout << "\n\nA:" ;
    for(size_t i = 0 ; i < A.size() ; i++ )
    {
                    size_t a = VISIT[ A[i] ] ;
    cout << endl << a+1 << ' ' ;
    }
                ////////////////////////////////////////////////////
                cout << "\n\nB:" ;
    for(size_t i = 0 ; i < B.size() ; i++ )
    {
                    size_t a = VISIT[ B[i] ] ;
    cout << endl << a+1 << ' ' ;
    }
                ////////////////////////////////////////////////////
    IloExpr SUM  (env) ;
    for(size_t i = 0 ; i < A.size() ; i++ )
                {
                    for(size_t j = 0 ; j < A.size() ; j++ )
                    {
                        if (i!=j)
                        SUM += U1[ VISIT[A[i]] ][ VISIT[A[j]] ][s][k] ;
                    }
                }
    IloExpr SUM1 (env) ;
                for(size_t i = 0 ; i < B.size() ; i++ )
                {
                    SUM1 += V1[ VISIT[B[i]] ][s][k] ;
                }
                // IloConstraint lazy_const = SUM - A.size() + SUM1 <= 0 ;
                // LAZY_CONST.add( lazy_const ) ;
                cout << endl << lazy_const << endl ;
                add (lazy_const) ;
                SUM.end() ;
                SUM1.end() ;
            }
        ///////////////////////////////////////////////////////////////
        ///////////////////////////////////////////////////////////////
        ///////////////////////////////////////////////////////////////
        for ( int k = 0 ; k < K2[s] ; k++ )
            {
                cout << "\n\nVehicle: " << k+1 << "\n\n" ;
                vector <int> A, B ;
                vector <int> VISIT ;
                for(int i = 0 ; i < N ; i++ )
                {
                    if (getValue (V2[i][s][k]) > EPSILON)
                    {
                        VISIT.push_back(i) ;
                        cout << endl << "V2(" << i+1 << ")(" << k+1 << ")=" << getValue (V2[i][s][k]) ;
                    }
                }
                int v_size = VISIT.size() ;
                cout << endl << "|V|=" << v_size << endl ;
                if (v_size == 0) // if vehicle k is not used, vehicle k+1 will not be used
                {
                    break ;
                }
                if (v_size <= 3) // if vehicle k visits 3 nodes (or less), definitely no subtour exists.
                {
                    continue ;
                }
                Graph <double> G(v_size) ;
                vector <double> MAX_FLOW (v_size,0) ;
                for(int i = 0 ; i < v_size ; i++ )
                {
                    for(int j = 0 ; j < v_size ; j++ )
                    {
                        if (i != j)
                        {
                            cout << "\n\nNow now\n\n" ;
                            double val = getValue (U2[ VISIT[i] ][ VISIT[j] ][s][k]) ;
                            cout << "\n\nNow now2\n\n" ;
                            if (val > EPSILON)
                            {
                                cout << "i=" << i << " j=" << j << "val=" << val << endl ;
                                cout << "ii=" << VISIT[i]+1 << " jj=" << VISIT[j]+1 << "val=" << val << endl ;
                                G.addEdge(i, j, val) ;
                                cout << endl << "U2(" << VISIT[i]+1 << ")(" << VISIT[j]+1 << ")(" << k+1 << ")=" << val ;
                            }
                        }
                    }
                }
                cout << endl << "Now" << endl ;
                double min_max_flow = IloInfinity ;
                cout << endl << "Now2" << min_max_flow ;
                double val ;
                cout << endl << "Now3" << v_size ;
                MAX_FLOW[0] = IloInfinity ;
                cout << endl << "Now4" << endl ;
                for(int i = 0 ; i < MAX_FLOW.size() ; i++ )
                cout << endl << MAX_FLOW[i] ;
                for(int i = 1 ; i < v_size ; i++ ) // Note that we start from i=1
                {
                    cout << "\nHi " ;
                    val = G.DinicMaxflow(0, i) ;
                    cout << "There! " << val << endl ;
                    MAX_FLOW[i] = val ;
                    if (val < min_max_flow)
                    min_max_flow = val ;
                }
                cout << "\n\nMIN(Maxflow)=" << min_max_flow << endl ;
                if (1-min_max_flow < EPSILON) // no subtour found
                {
                    cout << "\nContinued! " << 1-min_max_flow << endl ;
                    continue ;
                }
                cout << "\n\nMaxFlow:" ;
    for(int i = 0 ; i < v_size ; i++ )
                {
    cout << endl << VISIT[i]+1 << ' ' << MAX_FLOW[i] ;
                    if (MAX_FLOW[i] - min_max_flow < EPSILON)
                    {
                        B.push_back(i) ;
                    }
                    else
                    {
                        A.push_back(i) ;
                    }
                }
                ////////////////////////////////////////////////////
                cout << "\n\nA:" ;
    for(size_t i = 0 ; i < A.size() ; i++ )
    {
                    size_t a = VISIT[ A[i] ] ;
    cout << endl << a+1 << ' ' ;
    }
                ////////////////////////////////////////////////////
                cout << "\n\nB:" ;
    for(size_t i = 0 ; i < B.size() ; i++ )
    {
                    size_t a = VISIT[ B[i] ] ;
    cout << endl << a+1 << ' ' ;
    }
                ////////////////////////////////////////////////////
    IloExpr SUM  (env) ;
    for(size_t i = 0 ; i < A.size() ; i++ )
                {
                    for(size_t j = 0 ; j < A.size() ; j++ )
                    {
                        if (i!=j)
                        SUM += U2[ VISIT[A[i]] ][ VISIT[A[j]] ][s][k] ;
                    }
                }
    IloExpr SUM1 (env) ;
                for(size_t i = 0 ; i < B.size() ; i++ )
                {
                    SUM1 += V2[ VISIT[B[i]] ][s][k] ;
                }
                // IloConstraint lazy_const = SUM - A.size() + SUM1 <= 0 ;
                LAZY_CONST.add( lazy_const ) ;
                cout << endl << lazy_const << endl ;
                add (lazy_const) ;
                SUM.end() ;
                SUM1.end() ;
            }
        }
    }

     

     

     

     

     

     

    And here is the output for the last callback (that freezes):

     

     

     

     

     

     

    UB=45116.52136

     

    Vehicle: 1


    V1(3)(1)=1.00000
    V1(12)(1)=1.00000
    V1(17)(1)=1.00000
    |V|=3


    Vehicle: 2


    V1(2)(2)=1.00000
    V1(16)(2)=1.00000
    |V|=2


    Vehicle: 3


    |V|=0


    Vehicle: 1


    V2(3)(1)=1.00000
    V2(8)(1)=1.00000
    V2(10)(1)=1.00000
    V2(12)(1)=1.00000
    V2(20)(1)=1.00000
    |V|=5


    Now now

     

    Now now2

     

    Now now

     

    Now now2

     

    Now now

     

    Now now2

    i=0 j=3val=1.00000
    ii=3 jj=12val=1.00000

    U2(3)(12)(1)=1.00000

    Now now

     

    Now now2

     

    Now now

     

    Now now2

     

    Now now

     

    Now now2

     

    Now now

     

    Now now2

     

    Now now

     

    Now now2

    i=1 j=4val=1.00000
    ii=8 jj=20val=1.00000

    U2(8)(20)(1)=1.00000

    Now now

     

    Now now2

     

    Now now

     

    Now now2

    i=2 j=1val=1.00000
    ii=10 jj=8val=1.00000

    U2(10)(8)(1)=1.00000

    Now now

     

    Now now2

     

    Now now

     

    Now now2

     

    Now now

     

    Now now2

     

    Now now

     

    Now now2

     

    Now now

     

    Now now2

    i=3 j=2val=1.00000
    ii=12 jj=10val=1.00000

    U2(12)(10)(1)=1.00000

    Now now

     

    Now now2

     

    Now now

     

    Now now2

    i=4 j=0val=1.00000
    ii=20 jj=3val=1.00000

    U2(20)(3)(1)=1.00000

    Now now

     

    Now now2

     

    Now now

     

    Now now2

     

    Now now

     

    Now now2


    Now

    Now2inf
    Now35
    Now4

    inf
    0.00000
    0.00000
    0.00000
    0.00000
    Hi There! 1.00000

    Hi There! 1.00000

    Hi There! 1.00000

    Hi There! 1.00000


    MIN(Maxflow)=1.00000

    Continued! 0.00000


    Vehicle: 2


    V2(3)(2)=1.00000
    V2(4)(2)=1.00000
    V2(6)(2)=1.00000
    V2(9)(2)=1.00000
    V2(11)(2)=1.00000
    V2(17)(2)=1.00000
    V2(19)(2)=1.00000
    |V|=7


    Now now

     

    Now now2

    i=0 j=1val=0.33333
    ii=3 jj=4val=0.33333

    U2(3)(4)(2)=0.33333

    Now now

     

    Now now2

    i=0 j=2val=0.33333
    ii=3 jj=6val=0.33333

    U2(3)(6)(2)=0.33333

    Now now

     

    Now now2

    i=0 j=3val=0.33333
    ii=3 jj=9val=0.33333

    U2(3)(9)(2)=0.33333

    Now now

     

    Now now2

     

    Now now

     

    Now now2

     

    Now now

     

    Now now2

     

    Now now

     

    Now now2

     

    Now now

     

    Now now2

    i=1 j=2val=0.66667
    ii=4 jj=6val=0.66667

    U2(4)(6)(2)=0.66667

    Now now

     

    Now now2

     

    Now now

     

    Now now2

    i=1 j=4val=0.33333
    ii=4 jj=11val=0.33333

    U2(4)(11)(2)=0.33333

    Now now

     

    Now now2

     

    Now now

     

    Now now2

     

    Now now

     

    Now now2

    i=2 j=0val=0.33333
    ii=6 jj=3val=0.33333

    U2(6)(3)(2)=0.33333

    Now now

     

    Now now2

     

    Now now

     

    Now now2

     

    Now now

     

    Now now2

    i=2 j=4val=0.33333
    ii=6 jj=11val=0.33333

    U2(6)(11)(2)=0.33333

    Now now

     

    Now now2

    i=2 j=5val=0.33333
    ii=6 jj=17val=0.33333

    U2(6)(17)(2)=0.33333

    Now now

     

    Now now2

     

    Now now

     

    Now now2

     

    Now now

     

    Now now2

     

    Now now

     

    Now now2

     

    Now now

     

    Now now2

     

    Now now

     

    Now now2

    i=3 j=5val=0.66667
    ii=9 jj=17val=0.66667

    U2(9)(17)(2)=0.66667

    Now now

     

    Now now2

    i=3 j=6val=0.33333
    ii=9 jj=19val=0.33333

    U2(9)(19)(2)=0.33333

    Now now

     

    Now now2

     

    Now now

     

    Now now2

    i=4 j=1val=0.33333
    ii=11 jj=4val=0.33333

    U2(11)(4)(2)=0.33333

    Now now

     

    Now now2

     

    Now now

     

    Now now2

     

    Now now

     

    Now now2

     

    Now now

     

    Now now2

    i=4 j=6val=0.66667
    ii=11 jj=19val=0.66667

    U2(11)(19)(2)=0.66667

    Now now

     

    Now now2

    i=5 j=0val=0.66667
    ii=17 jj=3val=0.66667

    U2(17)(3)(2)=0.66667

    Now now

     

    Now now2

     

    Now now

     

    Now now2

     

    Now now

     

    Now now2

    i=5 j=3val=0.33333
    ii=17 jj=9val=0.33333

    U2(17)(9)(2)=0.33333

    Now now

     

    Now now2

     

    Now now

     

    Now now2

     

    Now now

     

    Now now2

     

    Now now

     

    Now now2

    i=6 j=1val=0.33333
    ii=19 jj=4val=0.33333

    U2(19)(4)(2)=0.33333

    Now now

     

    Now now2

     

    Now now

     

    Now now2

    i=6 j=3val=0.33333
    ii=19 jj=9val=0.33333

    U2(19)(9)(2)=0.33333

    Now now

     

    Now now2

    i=6 j=4val=0.33333
    ii=19 jj=11val=0.33333

    U2(19)(11)(2)=0.33333

    Now now

     

    Now now2


    Now

    Now2inf
    Now37
    Now4

    inf
    0.00000
    0.00000
    0.00000
    0.00000
    0.00000

     

    It is very strange that the vector is of size 7 but 6 elements are given in the output. The program freezes at this point and nothing happens until I stop it myself. Any ideas?

     

     


    #CPLEXOptimizers
    #DecisionOptimization


  • 2.  Re: Lazy Constraint Callback freezing

    Posted Mon November 05, 2018 11:10 AM

    It is impossible to read through your lengthy code, in particular because it is badly formatted and not in monospace font. What would be a lot more helpful is a stacktrace.

    Anyway, there are two things that stick out as suspicious:

    1. Are you sure getIncumbentObjValue() is what you want? That gives the value of the current incumbent, not the potential new incumbent that is proposed to the callback. getObjValue() gives the value for the latter.
    2. What is 'env' in your code? It looks like this is a global variable? That would be a very bad thing to do. The IloEnv you should use in a callback is the one that is returned by the callback's getEnv() function.

    #CPLEXOptimizers
    #DecisionOptimization


Related Content