Error on finding max value in MIP

[Agustino]

Hi, I stuck on finding max value each column by writing constraint in MIP. Unfortunately, the error was

Code: Select all

 Error 59 Endogenous prod smin smax require model type "dnlp"
 Error 256 equation eq2.. VAR prod smin smax

Suppose I have EM(f,t,i) as the positive variable, which is the result from previous constraints like this

Code: Select all

      i1 i2 i3 i4 i5
f1.t1  7  5  6  0  6
f1.t2  8  4  6  1  6
f1.t3  6  7  3  2  4
f2.t1  8  7  5  3  1
f2.t2  0  5  5  7  0
f2.t3  0  8  0  5  9

Code: Select all

eq2(f,i)..         last(i) =e= smax((t),EM(f,t,i));

So, I would like to fix the above coding and find the max value each column, and then collect in last(i) variable.
My target should be

last(1) = 8
last(2) = 8
last(3) = 6
last(4) = 7
last(5) = 9

Please help me to achieve this MIP model. Thank you.

[bussieck]

Hi, you need to reformulate this in a linear way. There is plenty of good literature out there that gives this type of reformulation tricks. I personally like the book Model Building in Mathematical Programming by HP Williams . Knowing the literature and understanding the basics helps you write good models. Nowadays, you can also shortcut and ask ChatGPT:

Can you help me reformulate a non-linear constraint of a mathematical optimization model using the max operator like x(i) = max(j, y(i,j)) into linear constraints with additional binary variables?

Sure, I can help with that. To reformulate a non-linear constraint using the max operator into linear constraints with additional binary variables, you can use a common technique called "big M" method.

Here's how you can do it:

Let's say you have a non-linear constraint of the form:

x(i) = max_{j} (y(i,j))

You can reformulate it using the following linear constraints:

1. Introduce a binary variable z(i,j) for each pair of indices i and j.
2. Add a constraint ensuring that z(i,j) = 1 if and only if y(i,j) is greater than or equal to all other values of y(i,.):

y(i,j) - y(i,k) <= M (1 - z(i,j)), for all j, k where j <> k

3. Add a constraint enforcing that z(i,j) = 1 if and only if x(i) = y(i,j):

x(i) - y(i,j) <= M (1 - z(i,j)), for all j

4. Add a constraint ensuring that x(i) is no less than any y(i,j):

x(i) - y(i,j) >= 0, for all j

In these constraints, M is a sufficiently large constant, which acts as a "big M" to ensure that the binary variables z(i,j) and the auxiliary variables do not violate the logic of the original non-linear constraint.

Keep in mind that the value of M should be chosen carefully to ensure that it is larger than the maximum possible value of y(i,j) in your problem. If it is too large, it may lead to numerical instability or suboptimal solutions.

This reformulation allows you to model the non-linear constraint using only linear constraints and binary variables.

ChatGPT even gives you some GAMS code

Code: Select all

Sets
    i /i1*iN/
    j /j1*jM/;

Parameters
    M /1000/;  // Adjust this value based on the problem

Variables
    x(i)  // Your decision variable
    y(i,j)  // Your original variable
    z(i,j) binary;  // Binary variable for reformulation

Binary Variables z;

Equations
    non_linear_constraint1(i,j)
    non_linear_constraint2(i,j)
    non_linear_constraint3(i);

non_linear_constraint1(i,j)..
    y(i,j) - y(i,k) - M * (1 - z(i,j)) =L= 0
    $(j <> k);

non_linear_constraint2(i,j)..
    x(i) - y(i,j) - M * (1 - z(i,j)) =L= 0;

non_linear_constraint3(i)..
    x(i) - y(i,j) =G= 0;

Model reformulated_constraint /all/;

which is not correct GAMS code but that's what you get from AI today and you have to use your knowledge and experience to interpret ChatGPT's answer (you should do that with the theoretical one too). In any case here is the correct GAMS code:

Code: Select all

$eolcom //
$set N 10
$set M 15
Sets
    i /i1*i%N%/
    j /j1*j%M%/;

Parameters
    M /1000/;  // Adjust this value based on the problem

Variables
    x(i)  // Your decision variable
    y(i,j)  // Your original variable
    z(i,j) binary;  // Binary variable for reformulation

Binary Variables z;

alias (j,k);
Equations
    non_linear_constraint1(i,j,k)
    non_linear_constraint2(i,j)
    non_linear_constraint3(i,j);
 
non_linear_constraint1(i,j,k)$(not sameas(j,k))..
    y(i,j) - y(i,k) - M * (1 - z(i,j)) =L= 0;

non_linear_constraint2(i,j)..
    x(i) - y(i,j) - M * (1 - z(i,j)) =L= 0;

non_linear_constraint3(i,j)..
    x(i) - y(i,j) =G= 0;

Model reformulated_constraint /all/;

With GAMS you can also just solve the problem as a DNLP and choose a solver that still gives you a global optimal solution. SCIP and LINDO both accepts DNLP with smax. If you have other discrete variables, turn the model into an MINLP.

Lots of choices... Good luck.
-Michael