Hello all,

I need to implement this constraint in an MILP formulation:

$$(x_{1} \cdot C_{1} + x_{2}) \cdot x_{3} \geq (x_4-x_2)^2 \cdot C_2$$

where \(x_{1}\) is an integer decision variable, \(x_2\), \(x_3\) and \(x_4\) are real decision variables, and \(C_1\) and \(C_2\) are constants.

Is there a way to linearize this expression? The integer variable \(x_1\) could be relaxed to a real variable if that would make things easier.

Thank you very much!

asked 04 Sep '17, 12:46

Luis%20Badesa's gravatar image

Luis Badesa
153
accept rate: 0%

edited 04 Sep '17, 13:09


If the continuous variables are bounded, and the variable products appear in relatively few constraints, a possible approach is to choose one of the continuous variables in each product to be represented according to its binary expansion (expanding to the right of the decimal), for example see Section 3.1 here.

With this method, it is possible to approximate a continuous variable to any degree of desired accuracy with a linear expression of binary variables (a logarithmic number of binary variables is needed for each expansion). Then, using this expansion, the standard technique of linearizing the product of binary variables with (the other) continuous variable can be applied.

link

answered 05 Sep '17, 17:19

AndyT's gravatar image

AndyT
6788
accept rate: 7%

Thanks Andy! I think that will do it

(06 Sep '17, 06:40) Luis Badesa

No, I'm pretty sure you cannot linearize that constraint, at least not exactly. You could approximate it via piecewise linear expressions, but I think that would be a pain in the butt to do (and, again, would only be approximate).

If your reason for linearizing was so that you could use a MIP solver, it may not be necessary. You did not specify signs for \(C_1\) and \(C_2\), nor sign restrictions for the \(x_i\), but if everybody happens to be nonnegative, your problem likely meets the qualifications CPLEX has for solving mixed integer quadratically constrained problems (MIQCPs). I suspect that means at least some other solvers can also handle it.

I'm going to assume that the objective function is linear or convex quadratic and that all other constraints are linear. Let \(w = C_1 x_1 + x_2\) be an auxiliary variable, allowing us to rewrite the constraint as \((x_2, x_4)' Q (x_2, x_4) \le w \cdot x_3\) where \[ Q=C_{2}\left[\begin{array}{cc} 1 & -1\\ -1 & 1 \end{array}\right]. \]The \(Q\) matrix is positive semidefinite if \(C_2\ge0\). If \(w\ge0\) and \(x_3\ge 0\), and if I'm reading the CPLEX docs correctly, CPLEX can turn this into a second order cone problem, which it can solve.

If any of the qualifications I mentioned (nonnegativity, linear/convex quadratic objective function) are not met, all bets are off.

link

answered 04 Sep '17, 18:38

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

Thanks for your quick reply Paul! That's why I feared, it looks quite complicated to linearize.

However, I need to implement it in an MILP, as I am working with a quite complicated model. On top of that, I am solving a Stochastic Program, so the computational burden would be to high if the model were non-linear.

An approximation is acceptable for my purposes, though. Since the right-hand side is convex, both \(x_4\) and \(x_2\) are positive and bounded, I have though of approximating it by cutting planes. I would then have a series of constraints in the form:

(continues next)

(04 Sep '17, 19:07) Luis Badesa

$$ (x_1 \cdot C_1 + x_2) \cdot x_3 \geq a_1 \cdot x_4 + b_1 \cdot x_2 + c_1 $$ $$ (x_1 \cdot C_1 + x_2) \cdot x_3 \geq a_2 \cdot x_4 + b_2 \cdot x_2 + c_2 $$ etc.

Where \(a_i\), \(b_i\) and \(c_i\) are the constants of the cutting planes.

On the left-hand side, I still have the sum of: 1) a bilinear term (\(x_1 \cdot x_3 \cdot C_1\)); and 2) a product of continuous variables (\(x_2 \cdot x_3\)). I know that the big-M method can be used to linearize bilinear terms, but do you know how can I deal with both that one and the product of \(x_2 \cdot x_3\) at the same time?

(04 Sep '17, 19:14) Luis Badesa
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×190
×65
×16

Asked: 04 Sep '17, 12:46

Seen: 601 times

Last updated: 06 Sep '17, 06:40

OR-Exchange! Your site for questions, answers, and announcements about operations research.