18
$\begingroup$

I encounter a nonlinear constraint that contains the square root of a sum of integer variables. Of course one could use nonlinear solvers and techniques; but I like linear programming. Are there any standard results on linearizing or approximating a square root of the sum of integer variables?

For example, the constraints look like this:

$\sqrt{\sum_{i \in \mathcal{I}} a_{ij}x_{ij} } \leq \theta_j, \quad \quad \forall j \in \mathcal{J}$,

here $x_{ij} \in \{0,1\}$ are binary variables, $\theta_j \in \mathbb{R}$ are continuous variables, and $a_{ij} \geq 0$ are parameters. $\mathcal{I}$ and $\mathcal{J}$ are any given sets of polynomial size.

Of course, this constraint is part of a larger MIP, but as I am curious to general methods and results regarding this constraint I believe it not to be of interest to post it here.

$\endgroup$
  • 3
    $\begingroup$ Could you add some additional information about the constraint (maybe a simplified version)? Is the constraint convex? $\endgroup$ – Kevin Dalmeijer Jul 21 at 9:25
16
$\begingroup$

This can be handled as an MISOCP, Mixed-Integer Second Order Cone problem. The leading commercial MILP solvers can also handle MISOCP.

Specifically, due to $x_{ij}$ being binary, $x_{ij}^2 = x_{ij}$. Therefore, the left-hand side is the two-norm of the vector over $i \in I$ having elements $\sqrt{a_{ij}} x_{ij}$.

I don't know whether this is the best way to handle this constraint, but it is a way, and it is "exact".

$\endgroup$
  • 3
    $\begingroup$ I agree with this answer. To add to this: if you really want to solve an LP rather than an SOCP, you can approximate the SOCP constraint with a polynomial number of LP constraints, as discussed here. AFAIK it's generally understood that solving the problem as one SOCP is faster. $\endgroup$ – Ryan Cory-Wright Jul 21 at 21:22
  • $\begingroup$ I like this answer a lot. To add: for a good reference on modeling SOCP, see this paper. $\endgroup$ – Kevin Dalmeijer Jul 21 at 22:06
  • $\begingroup$ Could you expand on where the term $x_{i,j}^2$ comes from. If taking squares in both sides, aren't we missing the cross terms $x_{ij}x_{k,j}$? $\endgroup$ – Daniel Duque Jul 22 at 2:31
  • 3
    $\begingroup$ @Daniel Duque If $x \in \{0,1\}$ then you can simply replace $x$ by $x^2$. This is due to the fact that $0^2 = 0$ and $1^2 = 1$ and thus $x^2 = x$ for all permitted values. $\endgroup$ – Kevin Dalmeijer Jul 22 at 9:26
  • 1
    $\begingroup$ I see now, thanks. $\endgroup$ – Daniel Duque Jul 22 at 12:04
3
$\begingroup$

To linearize that constraint as it is can be hard since it is non-convex. Assuming you still want to do that, you would need to introduce binary variables that allow you characterize the function. Focusing on a single $j$, let first define $w_j=\sum_{I\in I}a_{i,j} x_{i,j}$, with $w_j\geq 0$ and assume you have a bound on such that $w_j\leq UB_j$. Now let $n$ be the number of pieces (linear inequalities) you want to use to describe $\sqrt{w_j}$, and for each piece, let $m_{k,j}$ and $b_{k,j}$ be the slope and intercept of the $k$th piece of the $j$th constraint for $k=1,\ldots,n$, which are tangent lines of $\theta_j=\sqrt{w_j}$ at (finite) points $w_{k,j}\in[0,UB_j]$ (these are the breakpoints in the $w_j$ space), $k=1,\ldots,n+1$. Since the constraint are not convex, only one piece can be "on" in an optimal solution, hence, let $\lambda_{k,j}\in\{0,1\}$ be a binary variable that is 1 if the pice is "on" for constraint $j\in J$, 0 otherwise. Putting all together,

$\sum_{k=1}^n{\lambda_{k,j}}=1 ~\forall j\in J$ #Choose only one piece for crt j

$-M(1-\lambda_{k,j}) + w_{k,j}\le w_j \le w_{k+1,j} + M(1-\lambda_{k,j}) ~ \forall j \in J, k=1,\ldots,n$ # $w_j$ need to be in the right interval if you choose piece $k$

$w_j = \sum_{I\in I}a_{i,j} x_{i,j} \forall j \in J$ # Definition of $w_j$

$\theta_j\ge m_{k,j} w_j + b_{k,j} - M(1-\lambda_{k,j}) \forall j\in J, k=1,\ldots,n$ # This is the linearized constraint, where $\theta_j$ is greater or equal to the piece that is selected.

As a side note, you have to choose the breakpoints upfront. A plot of $\theta_j\ge \sqrt(w_j)$ (for a single j, this a 2d-plot) can help to clarify the linearization.

If your constraints are convex (e.g., the inequality is $\ge$ or you treat it as an SOCP as described in the answer above), then you could implement Kelley's cutting-plane method which is an outer approximation method. Those cuts are not cuts in the integer programming sense, so don't add them as cuts. Rather, in B&B add them as lazy constraints. Alternatively, if the MIP is easy to solve, generate a single (kelley's) cut at a time an re-optimize.

$\endgroup$
  • $\begingroup$ Is all this really needed? The square root function is concave, so you could just use a series of cutting planes: linearisation of square root at $\sum_i a_i x_i = sth$ <= $\theta_j$; with enough cutting planes, you are drawing an approximation that is good enough. (Or you can use an iterative process to add new cutting planes, to reduce the total number of constraints.) I guess that's what pubsonline.informs.org/doi/abs/10.1287/moor.26.2.193.10561 does. $\endgroup$ – dourouc05 Jul 22 at 1:59
  • $\begingroup$ It is necessary due to the sense of the inequality. In the way it’s written in the question, that constraint defines a non-convex feasible region. If the inequality is the other way around, then it would be much easier as it would be a convex feasible region (ignoring the integrality of x). $\endgroup$ – Daniel Duque Jul 22 at 2:09
2
$\begingroup$

Please also have a look at the very similar question in math.stackexchange. As @Mark L. Stone mentioned in his answer, all you need is a second-order cone model to solve your problem.

$\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.