Nonlinear Binary Programming 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
 A: 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}$$
A: 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.
