CPLEX 12.8.0.0: integer infeasible. 1828 MIP simplex iterations, 316 branch-and-bound nodes, No basis.

[nabil...@gmail.com]

I've been using CPLEX 12.8 for modelling my thesis project and i've faced a problem that i cannot solve. 

CPLEX returns an error message of  "integer infeasible". I pasted my model and data file below.

If you could have the chance to help me, i'll be very glad.

----------------------------------------------------------------------------------------------------------------------------------------

param n;

param f;

param h;

set S := {1..n}; #set of suppliers

set N := {0} union S; #set of nodes

set K := {1..h}; #set of vehicles

set R := {1..f}; #set of pick-up frequencies

set M := {0} union R; #set of pick-up frequencies

set start := {{0} cross S};

set SS := {S cross S};

set end := {S cross {0}};

set arc := {start union SS union end};

param d {i in N, j in N} >= 0;

param t {i in N, j in N} >= 0;

param o {i in N} >= 0;

param e {i in S} >= 0;

param c {i in N} >= 0;

param r {i in S};

param T >= 0;

param Q >= 0;

param bigM >= 0;

var x {arc, K} binary;

var y {S, K, R} binary;

var b {S, M} >= 0;

var a {N, K} >= 0;

var p {S, R} >= 0;

var z {S, K, R} >= 0; #z[i,k,m] = y[i,k,m]*a[i,k]

var w {S, K, R} >= 0; #w[i,k,m] = y[i,k,m]*b[i,m-1]

var v {S, K, R} >= 0; #v[i,k,m] = p[i,m]*y[i,k,m]

#objective function

minimize total_distance: sum {(i,j) in arc, k in K: i<>j} d[i,j]*x[i,j,k];

#flow constraints

s.t. flo1 {j in S} :sum{i in N, k in K: i<>j} x[i,j,k] >= 1;

s.t. flo2 {i in S} :sum{j in N, k in K: i<>j} x[i,j,k] >= 1;

s.t. flo3 {j in S} :sum{i in N, k in K: i<>j} x[i,j,k] <= h;

s.t. flo4 {k in K} :sum{j in S} x[0,j,k] <= 1;

s.t. flo5 :sum{j in S, k in K} x[0,j,k] <= h;

s.t. flo6 {l in S, k in K} :sum{i in N: i<>l} x[i,l,k] = sum{j in N: l<>j} x[l,j,k];

s.t. flo7 {k in K} :sum{j in S} x[0,j,k] = sum{i in S} x[i,0,k];

#departure constraints

s.t. dep1a {k in K} :o[0] <= a[0,k];

s.t. dep1b {k in K} :a[0,k] <= c[0];

s.t. dep2a {i in S, k in K} :o[i] <= a[i,k];

s.t. dep2b {i in S, k in K} :a[i,k] <= c[i];

s.t. dep3 {i in N, j in N, k in K: i<>j} :a[j,k] >= a[i,k] + t[i,j] - bigM*(1-x[i,j,k]);

s.t. dep4 {k in K} :a[0,k] + sum{i in N, j in N: i<>j} x[i,j,k]*t[i,j] <= c[0];

s.t. dep5 {k in K} :a[0,k] >= o[0] - bigM*(1-sum{j in S} x[0,j,k]);

#arrival constraints

s.t. arr3 {i in S} :b[i,0] = o[i];

s.t. arr1 {i in S, k in K, m in R} :b[i,m] = z[i,k,m] + b[i,m-1] - w[i,k,m];

s.t. linearz1 {i in S, k in K, m in R} :z[i,k,m] >= a[i,k] - c[i]*(1-y[i,k,m]);

s.t. linearz2 {i in S, k in K, m in R} :z[i,k,m] <= a[i,k];

s.t. linearw1 {i in S, k in K, m in R} :w[i,k,m] >= b[i,m-1] - c[i]*(1-y[i,k,m]);

s.t. linearw2 {i in S, k in K, m in R} :w[i,k,m] <= b[i,m-1];

s.t. linearw3 {i in S, k in K, m in R} :w[i,k,m] <= c[i]*y[i,k,m];

s.t. arr2 {i in S, m in R} :p[i,m] = (b[i,m] - b[i,m-1])*r[i];

s.t. arr4 {i in S, m in R} :b[i,m] >= b[i,m-1];

s.t. arr5 {i in S} :sum{m in R} p[i,m] = (e[i] - o[i])*r[i];

s.t. arr6 {i in S, m in 2..f} :sum{k in K} y[i,k,m] <= sum{k in K} y[i,k,m-1];

#capacity constraint

s.t. cap1 {k in K} :sum{i in S, m in R} v[i,k,m] <= Q;

s.t. linearv1 {i in S, k in K, m in R} :v[i,k,m] >= p[i,m] - Q*(1-y[i,k,m]);

s.t. linearv2 {i in S, k in K, m in R} :v[i,k,m] <= p[i,m];

#spoilage time constraint

s.t. spo1 {k in K} :sum{i in N, j in N: i<>j} x[i,j,k]*t[i,j] - sum{j in S} x[0,j,k]*t[0,j] <= T;

----------------------------------------------------------------------------------------------------------------------------------------

param n := 4;

param f := 100;

param h := 2;

param bigM default 100000;

param Q default 200;

param T default 360;

#distance

param d: 0 1 2 3 4:=

0 0 8 2 10 5

1 8 0 9 4 13

2 2 9 0 12 7

3 10 4 12 0 14

4 5 13 7 14 0;

#travel time

param t: 0 1 2 3 4:=

0 0 8 2 10 5

1 8 0 9 4 13

2 2 9 0 12 7

3 10 4 12 0 14

4 5 13 7 14 0;

#begin (8am=0)

param o :=

0 0

1 60

2 60

3 60

4 60;

#end 

param e :=

1 540

2 540

3 540

4 540;

#close

param c :=

0 720

1 600

2 600

3 600

4 600;

#rate (bag/60mins)

param r :=

1 12

2 12

3 12

4 12;

----------------------------------------------------------------------------------------------------------------------------------------

I am new to this type of programming. Does anybody smarter than me see a problem with any of my constraints?

I appreciate any advice. Thanks a lot! 

- NMS

[AMPL Google Group]

You could use iis feature to identify infeasibility in your model. You can set option cplex_options 'iisfind 1'; and solve your optimization problem. You can refer to https://ampl.com/BOOK/CHAPTERS/17-solvers.pdf (pp:299) to understand more about iis. I tried to run your model using iis but it's taking a quite a while for solver to find the infeasible set. You could post the output of the iis if you couldn't identify infeasibility in your problem.

--
Paras Tiwari
am...@googlegroups.com

{#HS:581238438-7732#}

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.
To post to this group, send email to am...@googlegroups.com.
Visit this group at https://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.