Topic
  • 1 reply
  • Latest Post - ‏2010-11-23T13:15:50Z by SystemAdmin
SystemAdmin
SystemAdmin
1883 Posts

Pinned topic An infeasible is reported as a feasible in a bin-packing, OPL 5.5 - renewed post

‏1970-01-01T07:00:00Z |

[hssong said:]

I found very strange report with following instance: an infeasible solution is reported as a feasible solution. I solved repeatedly many times and I got the same result with this particular data. I got fine solutions for many different data.  I hope it to be checked by others.


int M = ...; //NbItems of Orders//
int B = ...; //NbHeaters//
int K = ...; //NbSchedules//

range Items = 1..M;
range Heaters = 1..B;
range Schedules = 1..K;

int Weight[Items] = ...;
int HTreat[Items] = ...;
int Amount[Items] = ...;
int Capacity[Heaters] = ...;

dvar int+ BinPacking[Items][Heaters][Schedules];
dvar int+ BinTime[Heaters][Schedules];
dvar boolean BinAssign[Items][Heaters][Schedules];
//dvar float+ F;
dvar int+ F;


minimize
F;

subject to {
    forall ( g in Items )
    ctAmount:
    sum ( h in Heaters, k in Schedules )
    BinPacking[g][h][k] == Amount[g];

    forall ( h in Heaters, k in Schedules )
    ctCapacity:
    sum ( g in Items )
    BinPacking[g][h][k] * Weight[g] <= Capacity[h];<br />
    forall ( g in Items, h in Heaters, k in Schedules )
    ctTime:
    BinAssign[g][h][k] * HTreat[g] <= BinTime[h][k];<br />
    forall ( h in Heaters )
    ctSpan:
    sum ( k in Schedules )
    BinTime[h][k] <= F;<br />
    forall ( g in Items, h in Heaters, k in Schedules )
    ctAssign:
    BinPacking[g][h][k] <= BinAssign [g][h][k] * 100;   <br />}

M = 5;
B = 5;
K = 10;
Weight = [ 10, 15, 7, 8, 12 ];
HTreat = [ 12, 15, 20, 24, 30 ];
Amount = [ 10, 11, 11, 12, 10 ];
Capacity = [ 50, 40, 40, 10, 10 ];
========================================================================
The case of an infeasible solution but found as feasible solution:
See the red numbers where must be BinPacking[1][][] == Amount[1] ==10, but actually BinPacking[1][][] == Amount[1] ==9 is found as feasible.

Feasible solution with objective = 81:
F = 81;
BinPacking = [color=red][[[0 0 0 0 0 0 0 0 0 0]
                 [0 0 0 4 0 0 0 0 0 1]
                 [1 0 0 0 0 1 0 1 0 0]
                 [0 0 0 0 0 0 0 0 0 0]
                 [0 0 0 0 1 0 0 0 0 0]][/color]           

[[0 0 0 0 0 0 0 0 0 0]
                 [0 0 0 0 0 0 0 0 0 2]
                 [2 1 0 0 0 2 0 2 0 2]
                 [0 0 0 0 0 0 0 0 0 0]
                 [0 0 0 0 0 0 0 0 0 0]]
             [[7 0 0 0 0 0 0 0 0 0]
                 [0 0 0 0 0 0 0 0 0 0]
                 [0 3 0 0 0 0 0 0 0 0]
                 [0 0 0 0 0 0 0 0 0 0]
                 [0 0 0 1 0 0 0 0 0 0]]
             [[0 0 0 0 0 0 0 0 0 0]
                 [0 0 0 0 0 0 0 5 2 0]
                 [0 0 0 0 0 0 0 0 0 0]
                 [1 0 1 0 0 0 1 0 0 0]
                 [0 0 0 0 0 1 0 0 0 1]]
             [[0 0 4 0 0 0 0 0 0 4]
                 [0 0 0 0 0 0 0 0 2 0]
                 [0 0 0 0 0 0 0 0 0 0]
                 [0 0 0 0 0 0 0 0 0 0]
                 [0 0 0 0 0 0 0 0 0 0]]];
Updated on 2009-05-03T09:32:36Z at 2009-05-03T09:32:36Z by SystemAdmin