6
$\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$
  • 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 '19 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$ – Kevin Dalmeijer Aug 4 '19 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$ – LarrySnyder610 Aug 5 '19 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$ – Mark L. Stone Aug 5 '19 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$ – Oguz Toragay Aug 5 '19 at 11:39
7
$\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$
  • $\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 '19 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$ – LarrySnyder610 Aug 21 '19 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 '19 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$ – LarrySnyder610 Aug 28 '19 at 15:30

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.