Is the following optimization problem convex?

Question

I'm not an mathematician so sorry for the possibly trivial question.

I have written the following integer programming model:

\begin{align} \max z &= \sum_{i=1}^M \left(\sum_{j=1}^N b_j x_{ij}- c_i y_{i}\right)\\ \text{s.t.} & \sum_{j=1}^N a_{ij}x_{ij} \le d_i, & i=1,\dots,M,\\ & \sum_{i\in\mathcal{F}} x_{ij} = 1, & j=1,\ldots,N,\\ & \sum_{j\in\mathcal{N}} x_{ij} \le N y_{i}, & i=1,\ldots,M,\\ & x_{ij} \in \{0,1\}, & i=1,\ldots,M, j=1,\ldots,N,\\ & y_{i} \in \{0,1\}, & i=1,\ldots,M. \end{align} where $a_{ij}$, $b_j$, $c_i$ and $d_i$ are suitable real parameters.

I suspect this problem is not convex for the third constraint, do you?

A possible alternative formulation is to replace in the objective function the $y_i$ decision variables with the following: \begin{equation} \operatorname{sgn}\biggl(\sum_{j=1}^N x_{ij}\biggr) \end{equation} and thus I can remove the third constraint. The rationale for using the $\operatorname{sgn}$ function is that whenever $y_i=1$ in the original problem, there must be some $x_{ij}=1$ (for some $j$); while, if $y_i=0$ in the original problem, then $x_{ij}=0$ for all $j$.

But, again I suspect that this version is not convex too, due to the presence of the $\operatorname{sgn}$ function, do you?

Thank you very much for the help

Best Regards

Answer 1

No, it is not convex, but not because of the third constraint. The third constraint is, in fact, convex in $x$ and $y$. It is not a convex optimization problem because the variables are binary. A convex program must have a convex feasible set, which cannot be the case if the variables are not continuous.

Its continuous relaxation, however---that is, the model obtained by replacing each constraint of the form $z\in\{0,1\}$ with $z\in[0,1]$---is convex. In fact, the relaxation is a linear program. This is important in practice, because there is software available to globally solve binary linear programs. Of course, these solvers cannot guarantee a bound on execution time---and since the number of binary variables here is $MN+M$, it wouldn't take long for this to grow to unwieldy proportions.

That said, the structure of this problem resembles certain linear assignment problems so there may be some specialized methods out there that could be adapted to it.