Topic
• Latest Post - ‏2010-11-23T13:15:50Z by 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