2
$\begingroup$

In a mathematical integer optimization problem, if the objective function is represented as $\sum x_k \cdot M_k$, where $M_k$ is a non-linear function whose value is known and just plugged in to the objective function, thus acting as constant coefficients, is the objective function linear, since there are no product of variables are involved? When I try to feed in such a problem to an ILP solver, it doesn't complain of being not linear. What would be the explanation?

$\endgroup$
  • 4
    $\begingroup$ $M_k$ is a nonlinear function of what? As long as it does not depend on any of the variables in the IP model, you're okay. $\endgroup$ – prubin Jun 2 at 17:46
  • $\begingroup$ What if $M_k$ is a function of the variables in the IP model but can be precomputed and used as a lookup? @prubin $\endgroup$ – ephemeral Jun 4 at 7:04
  • $\begingroup$ So it's actually $M_k(x)$. How d you work that into the MIP model? $\endgroup$ – prubin Jun 5 at 17:13
  • $\begingroup$ No, but I was wondering what would happen in such a scenario $\endgroup$ – ephemeral Jun 8 at 17:53
  • $\begingroup$ Your comment about $M_k$ "acting as constant coefficients" does not make any sense to me. If the solver thinks the model is linear, it's probably because what you fed it has constant values of $M_k$ and thus does not actually represent the real problem. $\endgroup$ – prubin Jun 9 at 17:18
4
$\begingroup$

Yes, $\sum_k M_k x_k$ is linear if each $M_k$ is constant and $x_k$ is a variable.

| improve this answer | |
$\endgroup$
3
$\begingroup$

As you say:

"If the value of $M_k$ value is known and just plugged in to the objective function, thus acting as constant coefficients"

Then you are summing variables multiplied by constant terms, which is linear.

So all is good.

| improve this answer | |
$\endgroup$
2
$\begingroup$

Assuming that $M$ depends on $x$, your function is non-linear. If not, it is linear and all is well.

If the dependency does exist, just because a linear solver doesn't support the proper input, that doesn't make the function linear, although sometimes people find that assumption good enough for some specific application.

The correct way to solve a problem like this is to use an MINLP solver that supports callbacks, such as Knitro, our own Octeract Engine (v 1.14 and above), and, if memory serves, BONMIN.

If (part of) the problem is treated as black box, then the solver will keep updating the values of your objective (through the callbacks) and its derivatives and use new constants for $M$ in every iteration, which will most likely result in a different answer.

This is vastly different than classic solver behaviour where the problem is defined in the beginning and can't be changed during the solving process.

| improve this answer | |
$\endgroup$
2
$\begingroup$

What does it mean for a function to be linear?

It is actually short for the function is linear in its variables. One way to define linearity is to say, that the derivative is constant. For example $F(x)=5x+3$ is linear in $x$ as $F'(x)=5$. Is it linear in $y$? Well you can write it as $F(y) = 0y+5x+3$, then $F'(y)=0$. Because we treat $x$ as a constant.

So how do you know with respect to which variables you have to take the derivative? Well, the solver (e.g. Cplex) get a list of variables from you. These are your variables. The other term might be computed, but as your solver sees it, are just numbers, no matter how you came up with them.

So think about $M'_k(x)$. Is it constant? I think, this will answer your question.

Good luck and keep on solving problems:)

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.