1
$\begingroup$

I have an optimization problem which goes:

\begin{align*} \text{Minimize:} \\ & \sqrt{x} + \sqrt{y} \tag{NL-objective} \\ \text{Subject to:} \\ &3x + 2y \geq 2 & \tag{C1} \\ &2x + 3y \geq 2 & \tag{C2} \end{align*}

I am attempting to piecewise linearize it. The idea is to approximate the non-linear function with a bunch of linear functions and solve the MILP problem. I break the function in 2 lines each, equidistant in x. For reference, the image is attached below.

PWL objective

As you can see, $\sqrt x$ can be written as $\min\{0.7071 x,0.5858 x+0.4142\}$ in its piecewise linear form, where minimum is over the lines. Similarly we can write a minimum of linear functions for $\sqrt y$. Generally, we write min of linear functions as MILP as given in image below.

Generalization of <span class=$min\{f_i(x); i=1..n\}$" />

So, I get \begin{align*} \text{Minimize:}\\ &d_{1} + d_{2} \tag{Objective-PWL}\\ \text{Subject to:}\\ &3x+2y \geq 2 &\tag{C1} \\ &2x+3y \geq 2 &\tag{C2} \\ &y_{11} = \sqrt 2 x_{11} &\tag{first line, x} \\ &y_{12} = 0.5858 x_{12}+0.4142 &\tag{second line, x} \\ &y_{21} = \sqrt 2 x_{21} &\tag{first line, y} \\ &y_{22} = 0.5858 x_{22}+0.4142 &\tag{second line, y} \\ &0 \leq y_{11}, y_{21} \leq 0.7071 &\tag{1.i} \\ &0.7071 \leq y_{21}, y_{22} \leq 1 &\tag{1.i} \\ &d_{1} \leq y_{11}, y_{12} &\tag{2.i} \\ &d_{2} \leq y_{21}, y_{22} &\tag{2.i} \\ &d_{1} \geq y_{11} - 0.7071(1 - z_{11}) &\tag{3.i} \\ &d_{1} \geq y_{12} - (1 - z_{12}) &\tag{3.i} \\ &d_{2} \geq y_{21} - 0.7071(1 - z_{21}) &\tag{3.i} \\ &d_{2} \geq y_{22} - (1 - z_{22}) &\tag{3.i} \\ &z_{11}+z_{21}=1 &\tag{4.i} \\ &z_{21}+z_{22}=1 &\tag{4.i} \\ \end{align*}

However, there seems to be an issue with this formulation because there is no co-relation between $x, x_{11}, x_{12}$ What I think I have done is basically replaced the $\sqrt x$ and $\sqrt y$ with a bunch of lines, and converted the linear functions as $\min (f_1(x), f_2(x))$ and reformulated the min part as MILP. I do not know how to incorporate other constraints. Can someone help me figure out the correct formulation?

$\endgroup$
1
  • $\begingroup$ I think you want $1.414x$ rather than $0.707x$ for the first half of the approximation of $\sqrt{x}.$ $\endgroup$
    – prubin
    May 26, 2023 at 17:52

1 Answer 1

2
$\begingroup$

Your model contains a lot more items than are needed. Assume that $M$ is a sufficiently large positive parameter. I'll add two binary variables $z_x$ (used to linearize $\sqrt{x}$) and $z_y$ (used to linearize $\sqrt{y}$), and change your $d_1$ and $d_2$ to $d_x$ and $d_y$ just for clarity, resulting in the following model:

\begin{align*} \text{Minimize:}\\ &d_{x} + d_{y} \\ \text{Subject to:}\\ &3x+2y \ge 2 & \\ &2x+3y \ge 2 & \\ &d_x \ge \sqrt 2 \cdot x - M(1 - z_x)& \\ &d_x \ge 0.5858 x + 0.4142 -M z_x & \\ &d_y \ge \sqrt 2 \cdot y - M(1 - z_y)& \\ &d_y \ge 0.5858 y + 0.4142 -M z_y & \\ &z_x, z_y \in \lbrace 0, 1 \rbrace &\\ \end{align*}

A key here is that you are minimizing the sum of the surrogate ($d$) variables, meaning you don't have to worry about their being too large. You just have to make sure they are not too small.

If you use more than two linear segments in approximating the square root function, you need additional binary variables and an SOS1 constraint for each set of binaries.

$\endgroup$
1
  • $\begingroup$ Thanks! This is a demo example to demonstrate the working of the approach. In general, the program is encoded to break into n segments and there are m such components in objective. And hence the unnecessary equations, I think. I followed the template so audience can understand for more general case. I'll use this for the time being. $\endgroup$
    – madhafakha
    May 27, 2023 at 7:26

Your Answer

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