Decision Optimization

 View Only
Expand all | Collapse all

different optimal solution of the same sample

  • 1.  different optimal solution of the same sample

    Posted Wed September 02, 2020 04:26 PM
    Hi all,

    I solved my model with the same data file twice, but I got different optimal solution. The gap of them are both 0. Does anyone know the reason? Thanks in advance.

    Firstly, I run my code with logical expression
    ct8://arrival:
    forall(k in orders, s in services:s.a in orders_arcs[k])
    (x[k][s]==1)=>(arrival_time[k][s.a.tonode]==s.dept_time+s.traveling_time);

    ct9://time_window:
    forall(k in orders, <i,j> in orders_arcs[k]:i not in k.dest,s in services:s.a==<i,j>)
    (x[k][s]==1)=>(arrival_time[k][i]+processing_time[k][i]<=s.dept_time);

    ct10://due_time:
    forall (k in orders, <i,j> in orders_arcs[k]:j in k.dest )
    arrival_time[k][j]<=k.due_time + k.release_time;

    and I got these:
    Then I use general expression:
    ct8:
    forall(k in orders, j in orders_nodes[k]:j not in k.origin)
    sum(s in services:s.a.tonode==j)x[k][s]*(s.dept_time+s.traveling_time)<=arrival_time[k][j];

    ct9:
    forall(k in orders, <i,j> in orders_arcs[k]:i not in k.dest,s in services:s.a==<i,j>)
    arrival_time[k][i]+processing_time[k][i]<=x[k][s]*s.dept_time+Infinity*(1-x[k][s]);

    ct10:
    forall (k in orders, j in orders_nodes[k])
    arrival_time[k][j]<=sum(s in services:s.a.tonode==j)
    (k.due_time + k.release_time)*x[k][s];

    However, the optimal solution changed and service plan also changed. 


    ------------------------------
    Dario Pisinger
    ------------------------------

    #DecisionOptimization


  • 2.  RE: different optimal solution of the same sample

    Posted Thu September 03, 2020 01:37 AM
    Did you check whether the optimal solution for formulation 1 is feasible for formulation 2 and vice versa? I suggest to first check that because your different formulations of your constraints may not be equivalent (I did not check whether they allow the exact same set of integer feasible solutions).

    Also, depending on how big the value of Infinity is in your big-M constraint, you may be suffering from roundoff errors here. To avoid this use a smaller value for infinity and/or set the integrality tolerance to 0.

    ------------------------------
    Daniel Junglas
    ------------------------------

    Original Message