Bsrgvty

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:

$$sqrtsum_i in mathcalI a_ijx_ij leq theta_j, quad quad forall j in mathcalJ$$

where $x_ij in 0,1$ are binary variables, $theta_j in mathbbR$ are continuous variables, and $a_ij geq 0$ are parameters. $mathcalI$ and $mathcalJ$ 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.

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 $sqrta_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".

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.

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=sumlimits_Iin Ia_i,j x_i,j$, with $w_jgeq 0$ and assume you have a bound on such that $w_jleq UB_j$. Now let $n$ be the number of pieces (linear inequalities) you want to use to describe $sqrtw_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=sqrtw_j$ at (finite) points $w_k,jin[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,jin0,1$ be a binary variable that is one if the piece is "on" for constraint $jin J$, zero otherwise. Putting all together,

• Choose only one piece for crt $j$: $$sumlimits_k=1^nlambda_k,j=1 quadforall jin J$$




• $w_j$ need to be in the right interval if you choose piece $k$ $$-M(1-lambda_k,j) + w_k,jle w_j le w_k+1,j + M(1-lambda_k,j) quad forall j in J,,k=1,ldots,n$$




• Definition of $w_j$: $$w_j = sumlimits_Iin Ia_i,j x_i,j quadforall j in J$$




• This is the linearized constraint, where $theta_j$ is greater or equal to the piece that is selected: $$theta_jge m_k,j w_j + b_k,j - M(1-lambda_k,j) quadforall jin J,, k=1,ldots,n$$

As a side note, you have to choose the breakpoints upfront. A plot of $theta_jge sqrtw_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.

_Reference

_{[1] Kelley, J. E., Jr. (1960). The Cutting-Plane Method For Solving Convex Programs. Journal of the Society for Industrial and Applied Mathematics. 8(4):703-712.}

You can manipulate this inequality as follows

$$sqrtsum_i in mathcalI a_ijx_ij leq theta_j, quad quad forall j in mathcalJ$$

$$sum_i in mathcalI a_ijx_ij leq theta_j^2, quad quad forall j in mathcalJ$$

Now, you need to linearize $theta_j^2$ using McCormick Envelopes. To do this, assume $-M_jleq theta_j leq M_j$ and consider $w_j=theta_j^2$

$$
beginalign
0leq (theta_j + M_j)(theta_j + M_j) & implies & -w_j - 2M_jtheta leq M_j^2\
0leq (M_j - theta_j)(M_j - theta_j) & implies & -w_j + 2M_jtheta leq M_j^2\
0leq (theta_j + M_j)(M_j - theta_j) & implies & w_j leq M_j^2\
endalign
$$

The final set of constraints is

$$
beginalign
sum_i in mathcalI a_ijx_ij leq w_j, quad quad forall j in mathcalJ\
-w_j - 2M_jtheta_j leq M_j^2, quad quad forall j in mathcalJ\
-w_j + 2M_jtheta_j leq M_j^2, quad quad forall j in mathcalJ\
0 leq w_j leq M_j^2, quad quad forall j in mathcalJ\
-M_j leq theta_j leq M_j, quad quad forall j in mathcalJ\
endalign
$$

OBS: Verify my counts, please.