Topic
IC4NOTICE: developerWorks Community will be offline May 29-30, 2015 while we upgrade to the latest version of IBM Connections. For more information, read our upgrade FAQ.
2 replies Latest Post - ‏2013-03-14T08:12:55Z by SystemAdmin
SystemAdmin
SystemAdmin
378 Posts
ACCEPTED ANSWER

Pinned topic Getting inferior solution in CP

‏2013-03-13T16:51:46Z |
Hi all,

I have small problem with attached model and data file.

In this model I always get result where my interval variables are always allocated to one seq variable. where as i have so many seq variable and if my model distribute i can get better result to my objective.

Here are my seq and interval variable

// interval of each route
{dvar interval tvisithttp://n in 1..numberofdocksr in RouteData optional(r.routeid!=4 && r.routeid!=0) in planstarttime..planendtime size r.loadtime+r.paperworktime; }

// sequence variable for each day warehouse use
{dvar sequence route http://t in 1..numberofdocks in all(r in RouteData)tvisit[t][r] types all(r in RouteData) r.routeid;}

Please see the attached files for more details and suggest reason for the inferior solution i am getting

Thanks
Arun Lila

###########################

Data file
// A tuple have information about warehouse

numberofdocks = 2;
planstarttime = 0;
planendtime = 1440;
waitingcost = 100;

// A tuple have all information about a route
RouteData = {
<0, 0, 0, 0>,
<7, 1, 227, 30>,
<24, 1, 138, 30>,
<20, 2, 174, 30>,
<4, 0, 0, 0>,
};

RouteCustData = {
<7, 0, 0, 0, 0, 0, 1440>,
<7, 1, 357, 30, 20, 720, 2880>,
<24, 0, 0, 0, 0, 0, 1440>,
<24, 3, 58, 30, 40, 0, 2100>,
<24, 4, 52, 30, 5, 540, 5760>,
<24, 2, 87, 30, 15, 900, 2880>,
<20, 0, 0, 0, 0, 0, 1440>,
<20, 7, 86, 30, 80, 0, 2640>,
<20, 6, 136, 30, 5, 0, 2520>,
<20, 5, 29, 30, 5, 0, 2040>,
};
RouteCustTimeWindowsData =
{
<7, 1, 1, 2160, 2880>,
<7, 1, 2, 720, 1440>,
<24, 3, 1, 1440, 2100>,
<24, 3, 2, 0, 660>,
<24, 4, 1, 4860, 5760>,
<24, 4, 2, 3420, 4320>,
<24, 4, 3, 1980, 2880>,
<24, 4, 4, 540, 1440>,
<24, 2, 1, 2340, 2880>,
<24, 2, 2, 900, 1440>,
<20, 7, 1, 0, 2640>,
<20, 6, 1, 1200, 2520>,
<20, 5, 1, 1380, 2040>,
};
Updated on 2013-03-14T08:12:55Z at 2013-03-14T08:12:55Z by SystemAdmin
  • SystemAdmin
    SystemAdmin
    378 Posts
    ACCEPTED ANSWER

    Re: Getting inferior solution in CP

    ‏2013-03-14T05:41:01Z  in response to SystemAdmin
    When I just fix the values of interval variable to

    startOf(tvisit[1]<7>)== 443;
    startOf(tvisit[2]<24>)== 263;

    my objective function values reduces to 34300 from 106700..

    I am not getting why he cp model automatically select the above values and give me the global optimal solution.

    Thanks
    Arun Lila
    • SystemAdmin
      SystemAdmin
      378 Posts
      ACCEPTED ANSWER

      Re: Getting inferior solution in CP

      ‏2013-03-14T08:12:55Z  in response to SystemAdmin
      Hello,
      I still did not look at the details of your model but when I run it on your data with COS 12.5, it seems to quickly find an optimal solution:

      
      ! ---------------------------------------------------------------------------- ! Minimization problem - 54 variables, 44 constraints, 1 phase ! Presolve      : 4 extractables eliminated ! TimeMode             = ElapsedTime ! TimeLimit            = 10 ! Initial process time : 0.01s (0.00s extraction + 0.01s propagation) !  . Log search space  : 371.9 (before), 371.9 (after) !  . Memory usage      : 584.6 kB (before), 650.2 kB (after) ! Using parallel search with 2 workers. ! ---------------------------------------------------------------------------- !          Best Branches  Non-fixed    W       Branch decision 1000         19    2       on day_span(1) 1001          6    1       on tvisit(1)(
      {7
      }) *         68800      509 0.10s         2            - 68800     2001          6    2       on cvixit(
      {20,0
      }) 68800     2002          1    1       on cvixit(
      {20,5
      }) *         62300     1855 0.12s         2            - 62300     3001          6    2       on tvisit(2)(
      {20
      }) 62300     3002         12    1       on cvixit(
      {24,3
      }) 62300     4000          7    1       on cvixit(
      {20,6
      }) 62300     5001          7    1       on cvixit(
      {24,4
      }) *         13800     3544 0.20s         2            - ! ---------------------------------------------------------------------------- ! Search terminated normally, 3 solutions found. ! Best objective         : 13800 (optimal - effective tol. is 1) ! Number of branches     : 8964 ! Number of fails        : 4284 ! Total memory usage     : 2.3 MB (2.0 MB CP Optimizer + 0.3 MB Concert) ! Time spent in solve    : 0.21s (0.21s engine + 0.00s extraction) ! Search speed (br. / s) : 40931.5 ! ----------------------------------------------------------------------------
      


      Am I missing something? Maybe you did not attach the right version of the model/data ?
      Philippe