help-glpk
[Top][All Lists]

## 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.)

```