[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## Re: [Help-glpk] PROBLEM HAS NO INTEGER FEASIBLE SOLUTION

**From**: |
Andrew Makhorin |

**Subject**: |
Re: [Help-glpk] PROBLEM HAS NO INTEGER FEASIBLE SOLUTION |

**Date**: |
Thu, 16 Aug 2012 18:27:19 +0400 |

>* can you help me?*
>* I inserted in my model the following constraints:*
>* *
>* s.t. k2 {(j,p,m) in V_TECNOLOGICI, (m,k) in FERMI }:*
>* inizio_fermo[m,k] >= start[j,p,m] - BigP * ( 1 - k1[j,p,m,k] );*
>* *
>* s.t. k3 {(j,p,m) in V_TECNOLOGICI, (m,k) in FERMI}:*
>* start[j,p,m] >= inizio_fermo[m,k] - BigP * k1[j,p,m,k];*
>* *
>* where*
>* *
>* var k1 {(j,p,m) in V_TECNOLOGICI , (m,k) in FERMI} binary;*
>* var start {V_TECNOLOGICI};*
>* param inizio_fermo{FERMI} integer;*
>* *
>* and I always obtain the "PROBLEM HAS NO INTEGER FEASIBLE SOLUTION"*
>* response.*
>* If I try to drop the above constrains the model runs, if I try to drop*
>* individually the other constraints, leaving the above ones, the model*
>* doesn't run *
>* I don't get it why!*
To find which constraints cause infeasibility you may try to introduce
auxiliary non-negative variables (that play the role of residuals) as
follows:
var y2 {(j,p,m) in V_TECNOLOGICI , (m,k) in FERMI}, >= 0;
var y3 {(j,p,m) in V_TECNOLOGICI , (m,k) in FERMI}, >= 0;
s.t. k2 {(j,p,m) in V_TECNOLOGICI, (m,k) in FERMI }:
inizio_fermo[m,k] + y2[j,p,m,k]
>= start[j,p,m] - BigP * ( 1 - k1[j,p,m,k] );
s.t. k3 {(j,p,m) in V_TECNOLOGICI, (m,k) in FERMI}:
start[j,p,m] + y3[j,p,m,k]
>= inizio_fermo[m,k] - BigP * k1[j,p,m,k];
and then minimize the sum:
minimize sum{(j,p,m) in V_TECNOLOGICI , (m,k) in FERMI}
(y2[j,p,m,k] + y3[j,p,m,k]);
If your mip is integer feasible, all y2's and y3's should be zero in the
optimal solution. Otherwise (as in your case), non-zero components of y2
and/or y3 will show you which constraint(s) cannot be satisfied. (Note
that the modified mip above is guaranteed to be integer feasible due to
y2 and y3.)