# Decision Optimization

View Only

## Optimal Solution Obtained is Infeasible!

• #### 1.  Optimal Solution Obtained is Infeasible!

Posted Tue April 21, 2020 04:55 PM

Originally posted by: Bahman

Hello Everyone,

I am solving a simple LP, where I have obtained the optimal solution. However, one the process of solving an stochastic model, I have to solve the model again with fixed vector of optimal first stage variables. Thus, I ran the code, obtained the optimal vector, fixed it as a data (float, rather than a dvar) then, solved it again. It shows conflicts and relaxations.

I wonder, how an optimal solution to a problem can be infeasible if we fix it as a given vector.

MWE

{int} C = asSet(1..4);
{int} T = asSet(1..5);

float r[C] = [0.0, 250, 510, 700];

{int} S = asSet(1..2);

float p[S] = [1/3, 2/3];
float intact[S] = [0.90, 0.90];

dvar float+ x[C][T][S];
dvar float+ y[C][T][S];

maximize sum(t in T, s in S, c in C) p[s] * r[c] * x[c][t][s];

forall(s in S, c in C)
ct0: x[c][1][s] <= y[c][1][s];

forall(s in S)
ct1: y[1][1][s] == 8000;

forall(s in S)
ct2: y[2][1][s] == 10000;

forall(s in S)
ct3: y[3][1][s] == 20000;

forall(s in S)
ct4: y[4][1][s] == 60000;

forall(s in S, c in C)
ct5: x[c][2][s] <= y[c][2][s];

forall(s in S)
ct6: y[1][2][s] == sum(c in C) x[c][1][s];

forall(s in S)
ct7: y[2][2][s] == intact[s] * (y[1][1][s] - x[1][1][s]) ;

forall(s in S)
ct8: y[3][2][s] == intact[s] * (y[2][1][s] - x[2][1][s]) ;

forall(s in S)
ct9: y[4][2][s] == intact[s] * (y[3][1][s] - x[3][1][s]) + intact[s] * (y[4][1][s] - x[4][1][s]) ;

forall(s in S, c in C)
ct10: x[c][3][s] <= y[c][3][s];

forall(s in S)
ct11: y[1][3][s] == sum(c in C) x[c][2][s];

forall(s in S)
ct12: y[2][3][s] == intact[s] * (y[1][2][s] - x[1][2][s]) ;

forall(s in S)
ct13: y[3][3][s] == intact[s] * (y[2][2][s] - x[2][2][s]) ;

forall(s in S)
ct14: y[4][3][s] == intact[s] * (y[3][2][s] - x[3][2][s]) + intact[s] * (y[4][2][s] - x[4][2][s]) ;

forall(s in S, c in C)
ct15: x[c][4][s] <= y[c][4][s];

forall(s in S)
ct16: y[1][4][s] == sum(c in C) x[c][3][s];

forall(s in S)
ct17: y[2][4][s] == intact[s] * (y[1][3][s] - x[1][3][s]) ;

forall(s in S)
ct18: y[3][4][s] == intact[s] * (y[2][3][s] - x[2][3][s]) ;

forall(s in S)
ct19: y[4][4][s] == intact[s] * (y[3][3][s] - x[3][3][s]) + intact[s] * (y[4][3][s] - x[4][3][s]) ;

forall(s in S, c in C)
ct20: x[c][5][s] == 0;

forall(s in S)
ct21: y[1][5][s] == sum(c in C) x[c][4][s];

forall(s in S)
ct22: y[2][5][s] == intact[s] * (y[1][4][s] - x[1][4][s]) ;

forall(s in S)
ct23: y[3][5][s] == intact[s] * (y[2][4][s] - x[2][4][s]) ;

forall(s in S)
ct25: y[4][5][s] >= intact[s] * (y[3][4][s] - x[3][4][s]) + intact[s] * (y[4][4][s] - x[4][4][s]) ;

forall(s in S)
ct26: y[4][5][s] == 40000;

}

After running the model, we obtain y* vector as follows:

float y[C][T][S] = [[[8000, 8000],
[90000, 90000],
[0, 0],
[0, 0],
[34288, 34288]],
[[10000, 10000],
[7200, 7200],
[81000, 81000],
[0, 0],
[0, 0]],
[[20000, 20000],
[0, 0],
[6480, 6480],
[72900, 72900],
[0, 0]],
[[60000, 60000],
[0, 0],
[0, 0],
[5832, 5832],
[40000, 40000]]];

Now, we comment out the dvar y[C][T][S], and solve the model using the y[C][T][S] data as above (optimal solution of the same model! Now conflicts pop up due to infeasibility.

I thought that replacing each constraints with == with one >= and another <=, may work, but it didn't.

I would really appreciate if you please share your idea on this.

Regards,
BMB

#CPLEXOptimizers
#DecisionOptimization

• #### 2.  Re: Optimal Solution Obtained is Infeasible!

Posted Thu April 23, 2020 02:47 AM

What version of CPLEX do you use and how does the conflict look like?

I could not reproduce this with version 12.10. I get the same initial result like you and after fixing that I get the same result again (as expected). I am attaching the .mod I used to make sure I did not screw up.

#CPLEXOptimizers
#DecisionOptimization

• #### 3.  Re: Optimal Solution Obtained is Infeasible!

Posted Thu April 23, 2020 03:05 AM

Originally posted by: Bahman

Hey Daniel,

My CPLEX version is 12.8

Does it matter?

I wonder how you could obtain a feasible solution. I see  several of conflicts and thus relaxations.

Would you please advise how to handle it? DO I need to uninstall CPLEX 12.8 and install 12.10?

Regards
BMB

#DecisionOptimization

• #### 4.  Re: Optimal Solution Obtained is Infeasible!

Posted Thu April 23, 2020 03:14 AM

I tried 12.8 here and it produces a feasible solution as well. Can you try the file I attached to my previous comment? Does CPLEX claim infeasible on this as well?

Could you attach your offending .mod file? Just to make sure I am looking at the exact same thing as you.

#CPLEXOptimizers
#DecisionOptimization

• #### 5.  Re: Optimal Solution Obtained is Infeasible!

Posted Thu April 23, 2020 03:34 AM

Originally posted by: Bahman

Dear Daniel,

I tried your file, it gave me the same answer, however, I need to say that:

1) constraint ct25, must be equality not inequality.

2) as part of the stochastic programming to find the Stochastic Value, I have to fix y as float instead of dvar, and solve the problem for           float intact[S] = [0.85, 0.95];

trying this, I got the following conflicts:

Regards,
BMB

#DecisionOptimization

• #### 6.  Re: Optimal Solution Obtained is Infeasible!

Posted Thu April 23, 2020 04:07 AM

How can you require equality for ct25?

If you look at the slack for these constraint in the initial solution then the slack is -40000 for both. So I don't think it is suprising that the solution is infeasible if you force the slack to be 0 by turning ">=" into "==".

In fact, if I just fix the solution and switch ">=" to "==" then I get this error message:

Infeasibility row 'ct25(1)':  0  = -40000.

So what am I missing here? Are the modified values for intact supposed to allow a new feasible solution?

#CPLEXOptimizers
#DecisionOptimization

• #### 7.  Re: Optimal Solution Obtained is Infeasible!

Posted Thu April 23, 2020 04:13 AM

Originally posted by: Bahman

Dear Daniel,

Thanks Daneil. I found the solution.  The following constraints were the source of infeasibilities.

ct1: y[1][1][s] == 8000;

forall(s in S)
ct2: y[2][1][s] == 10000;

forall(s in S)
ct3: y[3][1][s] == 20000;

forall(s in S)

ct4: y[4][1][s] == 60000;

Which were overriding the y'.s.

I fixed them, which was possible to do considering the nature of the first period in the stochastic model, then, the conflicts did not pop up again

Thanks

Regards,
BMB

#CPLEXOptimizers
#DecisionOptimization