Nonlinear Binary Programming

Question

I am trying to understand what is the best approach to solve this binary programming problem

$$ \max_{X\in \left\{0,1 \right\}^{N}} \left(\sum_{i=1}^{N} a_{i}X_{i}\right)^{\beta} - \sum_{i=1}^{N}c_{i}X_{i} $$

with $X\in \left\{0,1 \right\}^{N}, a_{i}>0, c_{i} >0 $ and $\beta>0$. Would linearization techniques be useful in this case? I think relaxation will not work given that the function is not concave. Can it be formulated as a more specific well-known problem? Are there any optimized algorithms known for it?

Thanks so much in advance

Answer 1

The title says polynomial, so I will assume that $\beta$ is an integer. Yes, you can linearize by expanding the power and introducing a new binary variable for each resulting product of $X_i$s. For example, if $\beta=3$, one of the products is $X_1 X_2 X_3$ and you would introduce binary variable $Y_{1,2,3}$, together with constraints \begin{align} Y_{1,2,3} &\le X_1 \tag1\\ Y_{1,2,3} &\le X_2 \tag2\\ Y_{1,2,3} &\le X_3 \tag3\\ X_1 + X_2 + X_3 - 2 &\le Y_{1,2,3} \tag4\\ \end{align} Constraints $(1)$ through $(3)$ enforce $Y_{1,2,3} \le X_1 X_2 X_3$. Constraint $(4)$ enforces $Y_{1,2,3} \ge X_1 X_2 X_3$.

You can optionally relax $Y$ to be nonnegative because it will automatically take values $\{0,1\}$ when $X$ is binary.

---

Here's an alternative linearization for the case that $\beta$ is not necessarily integer. Suppose you know that $\sum_i a_i X_i \in S$ for some finite set $S$ that is easy to generate. For example, if the $a_i$ are positive integers, you can take $S=\{0,1,\dots,\sum_i a_i\}$. Now for each $s \in S$, let binary variable $Z_s$ indicate whether $\sum_i a_i X_i = s$. The problem is to maximize $$\sum_{s \in S} s^\beta Z_s - \sum_{i=1}^N c_i X_i$$ subject to \begin{align} \sum_{s \in S} Z_s &= 1 \\ \sum_{s \in S} s Z_s &= \sum_{i=1}^N a_i X_i \tag1\\ \end{align}

If you cannot easily generate $S$ such that $\sum_i a_i X_i \in S$, you can approximate by letting $\Delta=(\sum_i a_i)/m$, taking $S=\{0,\Delta,2\Delta,\dots,\sum_i a_i\}$, and relaxing equality constraint $(1)$ to an inequality: $$-\frac{\Delta}{2} \le \sum_{s \in S} s Z_s - \sum_{i=1}^N a_i X_i \le \frac{\Delta}{2}$$

Answer 2

You could perform no-frills branch-and-bound on the problem. Let level 0 contain just the root node. At each node in level $i$, you create one child node with $X_{i+1} = 1$ and one with $X_{i+1} = 0$. Suppose you are at a node in level $L>0$, meaning you have values for $X_1, \dots, X_L$. Set $A_L=\sum_{i=1}^L a_i X_i$ and $C_L=\sum_{i=1}^L c_iX_i$. Since there are no constraints, you have a candidate solution with objective value $A_L^\beta - C_L$ by setting the remaining variables zero, which may or may not be a new incumbent. The child with $X_{L+1}=0$ has a valid upper bound of $(A_L + \sum_{i=L+2}^N a_i)^\beta - C_L$ and the child with $X_{L+1}=1$ has a valid upper bound of $(A_L + a_{L+1} + \sum_{i=L+2}^N a_i)^\beta - C_{L+1}$. Whether those bounds are good enough to save you from essentially full enumeration is an empirical question.