Ttdfjt

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$,

here $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=sum_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 1 if the pice is "on" for constraint $jin J$, 0 otherwise. Putting all together,

$sum_k=1^nlambda_k,j=1 ~forall jin J$ #Choose only one piece for crt j

$-M(1-lambda_k,j) + w_k,jle 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_Iin Ia_i,j x_i,j forall j in J$ # Definition of $w_j$

$theta_jge m_k,j w_j + b_k,j - M(1-lambda_k,j) forall jin 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_jge 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.