7
$\begingroup$

I'm trying to solve an optimization problem including following constraint, and I need to linearize it in a maximization nonlinear programming model. Please help me to reformulate it with mixed integer programming. A part of my model is here: $$\min\ Z=-q_1p_1 \\ q_1=\min\{b,ap_1\}$$
Note that $q_1$ and $p_1$ are non-negative variables and the others are parameters. I know that $$q_1\le b,\, q_1\le ap_1 $$ are helpful. But I'm trying to find another way to linearize it.

$\endgroup$
12
  • 4
    $\begingroup$ First of all, welcome to OR.SE. Can you provide more info on what you mean by "maximization nonlinear programming model"? And about the constraint: do you mean you have a constraint in a form of $x = min(b - q_1 - q_2, a)$? If so, then $x\le b - q_1 - q_2$ and $x \le a$ are your constraints. $\endgroup$
    – EhsanK
    Aug 4, 2019 at 21:04
  • 1
    $\begingroup$ I agree that we need more information. The suggestion of EhsanK is a good one, but may not always work. For example, if it is beneficial to choose $x$ small, then $x$ may end up to be less than the minimum, instead of equal. $\endgroup$ Aug 4, 2019 at 21:25
  • 2
    $\begingroup$ This question considers a max in a constraint, but the same approach might be able to be used here, using the fact that $\min\{x,y\} = x + y - \max\{x,y\}$ for all $x,y$. $\endgroup$ Aug 5, 2019 at 0:40
  • 3
    $\begingroup$ After all this, you still haven't told us what your constraint is. min(0 by itself doesn't constitute a c constraint. Presumably, the constraint is one of, min $\ge$ something, min $\le$ something, or min = something. $\endgroup$ Aug 5, 2019 at 9:10
  • 2
    $\begingroup$ @Vida As Mark said none of your explanations was really revealing the nature of your model. If possible, please edit your question and explicitly write down 1) Your objective function, 2) your constraints(at least their general forms). $\endgroup$ Aug 5, 2019 at 11:39

1 Answer 1

14
$\begingroup$

Here is an answer that uses the same approach as in this answer, but converted from $\max\{\cdot,\cdot\}$ to $\min\{\cdot,\cdot\}$. I'll write the constraint in a more general form:

$$X = \min\{x_1,x_2\}$$

This method works if $x_1$ and $x_2$ are constants or decision variables (or one of each). (In your question, $X = q_1$, $x_1 = b$ and $x_2 = ap_1$.)

We want a set of constraints that enforces $X = \min\{x_1,x_2\}$. Define a new binary decision variable $y$, which will equal 1 if $x_1 < x_2$, will equal 0 if $x_1 > x_2$, and could equal either if $x_1 = x_2$. Let $M$ be a constant such that $x_1,x_2 \le M$ in any "reasonable" solution to the problem.

The following constraints enforce the definition of $y$: $$\begin{align} x_2 - x_1 & \le My \\ x_1 - x_2 & \le M(1-y) \end{align}$$ Then, the following constraints enforce $X = \min\{x_1,x_2\}$: $$\begin{align} X & \le x_1 \\ X & \le x_2 \\ X & \ge x_1 - M(1-y) \\ X & \ge x_2 - My. \end{align}$$ The first two constraints say $X \le \min\{x_1,x_2\}$. Combined with these constraints, the last two constraints say that $X = x_1$ if $x_1 < x_2$ (so $y=1$) and $X = x_2$ if $x_2 < x_1$ (so $y=0$).

$\endgroup$
6
  • $\begingroup$ @LarrySynyder610 thanks for your reply.The way you suggested wasn't helpful. The binary variable doesn't take value and it cause infeasible state in my GAMS codes. $\endgroup$
    – Vida
    Aug 21, 2019 at 7:09
  • $\begingroup$ I'm sorry it wasn't helpful. I am pretty sure that the method I outlined is correct, at least in general. Maybe there's something else going on in your model that is interfering with the constraints on $y$ somehow and causing the infeasibility -- or even maybe just an implementation bug. It's also of course possible that my method is wrong, though I think it's correct -- so if you see an error or flaw in my reasoning, please let me know. $\endgroup$ Aug 21, 2019 at 13:15
  • $\begingroup$ @larrySynyder610 I checked all terms in my code GAMS. I'm sure it's correct. let me to explain it more.First, I use the method you mentioned and the model was infeasible. then, I use the constraints that I mentioned in my question and it didn't cause any problem.It seems the method isn't helpful for the case, and I keep working with these $$q_1\le b,\, q_1\le ap_1 $$ .Anyway, I really appreciate it. $\endgroup$
    – Vida
    Aug 28, 2019 at 9:53
  • $\begingroup$ Hmm, OK, well, I don't see where the logical error is. Maybe someone else can spot it. Sorry this didn't help. $\endgroup$ Aug 28, 2019 at 15:30
  • $\begingroup$ I found a different linearization for $\min$ here. Instead of your single variable $y$ they introduce two variables $d_1$ and $d_2$, with these constraints: \begin{split} L_1 &\leq x_1 \leq U_1 \\ L_2 &\leq x_2 \leq U_2 \\ \\ X &\leq x_1 \\ X &\leq x_2 \\ X & \geq x_1 - (U_1 - L_{min})(1 - d_1) \\ X & \geq x_2 - (U_2 - L_{min})(1 - d_2) \\ d_1 &+ d_2 = 1 \end{split} @LarrySnyder610 Could there be an advantage to using this approach instead of yours, or the other way around? $\endgroup$ Jan 14, 2023 at 3:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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