1
$\begingroup$

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

$\endgroup$

2 Answers 2

2
$\begingroup$

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

$\endgroup$
11
  • $\begingroup$ Thanks so much for the answer. This is super useful. I made a mistake by including the word polynomial on the title, I want $\beta$ to be any non-negative real. Is there any "general" way of approaching this problem under this assumption? $\endgroup$ Commented Jan 22, 2021 at 14:11
  • $\begingroup$ Are the $a_i$ values integer or do you otherwise know a small discrete set of values that $\sum_i a_i X_i$ must take? $\endgroup$ Commented Jan 22, 2021 at 14:37
  • $\begingroup$ The $a_{i}$ and $c_{i}$ are just parameters, which are known at the time of optimizing. Therefore, I can evaluate the sum for any set of $X_{i}$, however, since N might be large the problem is combinatorial. $\endgroup$ Commented Jan 22, 2021 at 14:51
  • $\begingroup$ Do you even know bounds on $a_i$? $\endgroup$ Commented Jan 22, 2021 at 14:54
  • $\begingroup$ Yes, I know all the $a_{i}$! Also, the dimension is not as large. N should be around 100. $\endgroup$ Commented Jan 22, 2021 at 14:57
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ This approach might benefit from reindexing so that $a_i/c_i$ (or maybe $a_i$ or $c_i$?) is sorted. $\endgroup$ Commented Jan 24, 2021 at 6:00
  • $\begingroup$ Rob: You are correct about the subscript (I just fixed it), and I would not be surprised if sorting helped, although I'm not sure exactly what sort would work best. Also, as in MIP solving, nodes would be pruned faster if you could get a good (near-optimal) solution from a heuristic. $\endgroup$ Commented Jan 25, 2021 at 16:17

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.