Originally posted by: ZhangShixuan

Hi, I've been stuck in a strange problem. I set up a mix-integer problem using convex combination to form a piecewise linear function. However, the cplex failed to optimize. Then I tried the most simplified version of my problem, which contains only 7 bool variables and some 20 nonnegative variables, in order to find out where the problem is. Unfortunately, it still did not work. The most wierd thing is that, I can already find a solution (not optimized though) simply by my observation. Is there any possibility that cplex failed these situations? Or how can I fix that?

Thanks a lot!

The lp version of my simplified formulation is shown below:

\ENCODING=ISO-8859-1
\Problem name: IloCplex

Minimize
 obj: Hc + x45
Subject To
 c1:  p_i - p_vi  = 0
 c2:  p_i - p_ci  = 0
 c3:  - q_vi - q_ci + q_i  = 0
 c4:  p_o - p_vo  = 0
 c5:  p_o - p_co  = 0
 c6:  - q_vo - q_co + q_o  = 0
 c7:  - q_ci + q_co + 0.335367898584747 Hc  = 0
 c8:  - p_ci + 5500000 x14 + 7000000 x16 + 5500000 x18 + 7000000 x20
      + 5500000 x22 + 7000000 x24 + 7000000 x26 + 5500000 x28 + p_i_aux  = 0
 c9:  - p_co + 7000000 x14 + 7000000 x16 + 5500000 x18 + 5500000 x20
      + 7000000 x22 + 7000000 x24 + 5500000 x26 + 5500000 x28 + p_o_aux  = 0
 c10: - q_ci + 2100000 x14 + 2100000 x16 + 1400000 x18 + 2100000 x20
      + 1400000 x22 + 1400000 x24 + 1400000 x26 + 2100000 x28  = 0
 c11: - Hc + 16556.5440060342 x14 - 15065.9625176274 x20 + 11037.6960040228 x22
      - 10043.9750117516 x26  = 0
 c12: x14 + x16 + x18 + x20 + x22 + x24 + x26 + x28 - s_c  = 0
 c13: - s_c + x33 + x35 + x37 + x39 + x41 + x43  = 0
 c14: x14 - x33 - x35 - x39 - x41 - x43 <= 0
 c15: x16 - x33 <= 0
 c16: x18 - x37 <= 0
 c17: x20 - x33 - x35 - x41 <= 0
 c18: x22 - x37 - x39 - x43 <= 0
 c19: x24 - x33 - x41 - x43 <= 0
 c20: x26 - x35 - x37 - x39 - x41 - x43 <= 0
 c21: x28 - x35 - x37 - x39 <= 0
 c22: p_i_aux + 7000000 s_c <= 7000000
 c23: p_o_aux + 7000000 s_c <= 7000000
 c24: q_vi - q_vo  = 0
 c25: q_vi + 2100000 s_c <= 2100000
 c26: q_vi + 1400000 s_c >= 1400000
 c27: - p_vi + p_vo - 1500000 s_c <= 0
 c28: p_vi - p_vo - 1500000 s_c <= 0
 c29: Hc - 100000 s_c >= 0
 c30: p_o >= 5510000
 c31: p_i  = 5500000
Bounds
 0 <= x14 <= 1
 0 <= x16 <= 1
 0 <= x18 <= 1
 0 <= x20 <= 1
 0 <= x22 <= 1
 0 <= x24 <= 1
 0 <= x26 <= 1
 0 <= x28 <= 1
 0 <= s_c <= 1
 0 <= x33 <= 1
 0 <= x35 <= 1
 0 <= x37 <= 1
 0 <= x39 <= 1
 0 <= x41 <= 1
 0 <= x43 <= 1
      x45 = 0
Binaries
 s_c  x33  x35  x37  x39  x41  x43
End

where the unnamed variables are actually the auxiliary ones in the convex combination method of forming the piecewise linear function. Thanks to any ideas or thoughts!!

Originally posted by: T_O

Despite the fact that the numerics of this problem looks very bad, it is in fact LP-infeasible. You claim you can "see" a solution. Could you provide this solution, so that we can tell you what is wrong with this solution?

Best regards,
Thomas

Originally posted by: ZhangShixuan

Thanks, Thomas. It is actually part of the pipeline model. The variables naming 'p's and 'q's are acutually the pressure and the flow rate of each modelled node. The variable 's_c' indicates the opening (1) or closing (0) of the compressor. When the compressor is turned off, the bypass valve is then opened. So the picture of the whole simplified model is that a certain pressure is given at the input of the compressor, and a minimum output pressure is required.

The 'Hc' refers to the power of the compressor, which is a nonlinear function of p_input, p_output and q_input. In order to use the mip of cplex, I used convex combination method to linearize the nonlinear function, ie. to use some fuction value of certain nodes to approximate any function value. And the aim is to minimize the power cost while satisfying the above pressure requirement.

I said I'd seen the solution, because I deliberately chose the input and output pressure on a specific node in the linearization. To be specific, if s_c = 1 (compressor on), then the requirements are surely satisfied. Furthermore, if I choose p_i (input) = 5500000, p_o(output) = 7000000, then x14 = x33 = 1 will be feasible ( though not optimized).

I'm sorry that I failed to express the whole model in a detailed and clear way, but I think the values are correct.

Thank you very much!

Originally posted by: T_O

Can you please give us an assignment for all variables that you think that is feasible. Just write everything down like:

s_c = 1
p_i = 5500000
p_o = 7000000
...

Please do not omit any variable.

Best regards,
Thomas

Originally posted by: ZhangShixuan

Thank you Thomas, I think the method of finding the conflicts is really helpful, so I am trying to learn the method myself without further bothering you. Thank you very much for your help!

You model looks blatantly infeasible. Running the conflict refiner I get this minimal conflict:

Minimize
 obj:
Subject To
 c1:  p_i - p_vi  = 0
 c4:  p_o - p_vo  = 0
 c11: - Hc + 16556.5440060342 x14 - 15065.9625176274 x20 + 11037.6960040228 x22
      - 10043.9750117516 x26  = 0
 c27: - p_vi + p_vo - 1500000 s_c <= 0
 c29: Hc - 100000 s_c >= 0
 c30: p_o >= 5510000
 c31: p_i  = 5500000
\Sum of equality rows in the conflict:
\ sum_eq: - Hc + 2 p_i - p_vi + p_o - p_vo + 16556.5440060342 x14
\         - 15065.9625176274 x20 + 11037.6960040228 x22 - 10043.9750117516 x26
\          = 5500000
Bounds
      Hc Free
      p_i Free
      p_vi Free
      p_o Free
      p_vo Free
 -Inf <= x14 <= 1
 -Inf <= x22 <= 1
 0 <= s_c <= 1
 All other variables are >= 0.
Binaries
 s_c

From c1 and c31 you get p_i=p_vi=5500000.

From c4 and c30 you get p_o = p_vo >= 5510000.

Then c27 gives 1500000 s_c >= p_vo - p_vi. Substituting p_vi=5500000 and p_vo>=5510000 this gives s_c >= 10000/1500000. Since s_c is a binary variable this implies s_c=1.

With s_c=1 constraint c29 now reads Hc >= 100000 and with this constraint c11 is infeasible.

With Hc >= 100000 constraint c11 reads

16556.5440060342 x14 - 15065.9625176274 x20 + 11037.6960040228 x22  - 10043.9750117516 x26 >= 100000

Since x14 in [-inf,1], x20 in [0, inf], x22 in [-inf,1], x26 in [0,inf], the largest value the left-hand side can attain is 16556.5440060342+11037.6960040228 which is clearly less than 100000.

In the solution you "saw", you claimed that s_c=1 would be feasible. However, as you can see above, this is not feasible as it requires Hc >= 100000 which in turn renders c11 infeasible.

Please take a look at the conflict refiner documentation. This explains how you can analyze infeasible problems to figure out why CPLEX thinks they are infeasible.

Originally posted by: ZhangShixuan

Thanks Daniel. What you said about my model is all correct. And the method you mentioned seems really helpful! I am learning that and thank you again!