Linearize a higher order polynomial objective function?

Question

My question up front with context below:

Is there a generalized linearization possible for a higher order polynomial (max degree 6 in my case) involving a mix of binary and real variables? If not, does anybody see a way to re-formulate the problem below in linear form? And if the answer to that is also no, is there an optimization programming technique that can handle this problem form? If at all possible I'd like to stick to a method that can be handled by CPLEX.

---

I'm trying to solve an optimization problem as an MILP using docplex. All constraints are linear and all constraint variables are binary. However, I have a condition where decision variables belong to subsets and if any variable within an arbitrary subset is 'active' in the solution, then the objective function cost terms corresponding to all variables in the set are modified by a scalar.

In plain terms, if a decision variable appears in a solution, then the cost for other members of its subset to appear in the same solution are reduced. Note that variables can be members of multiple subsets.

For example, for a variable subset $\left (x_1, x_2, x_3, x_4, x_5 \right )$:

If:

$$\sum_{i=1}^{5}x_i \geq 1$$ Then: $$c_i = \left(1-b\right)c_{i} \quad \mathrm{for \ all} \quad i \in \left (1, ..., 5 \right ) \quad \mathrm{with} \quad 0 \le b\le 1$$

Where $b$ is a percentage reduction in cost for members of the subset, and the objective function is in the form: $$min \sum_{i=1}^{n}c_{i}x_{i}$$

My plan was to implement this by adding dummy variables to the objective function in the form: $$min\sum_{i=1}^{n}c_{i}x_{i}\prod_{j}^{m} \left (1-b_{j}y_{j} \right ) \quad \mathrm{with} \quad c_{i}, b_{j} \in \mathbb{R} \quad \mathrm{and} \quad x_{i}, y_{j} \in \left ( 0, 1 \right )$$

Where $m$ is the number of variable subsets that $x_i$ belongs to. I would add boolean constraints: $$y_{j}== \begin{equation} \begin{cases} 1 & \text{if } \sum x_{i} \geq 1\\ 0 & \text{if } \sum x_{i} = 0\\ \end{cases} \end{equation} \quad \text{for }i \in \left (\text{subset }j \right )$$

Then I planned to linearize the objective function using the general case of $n$ binary variables here: How to linearize the product of two binary variables?

$\sum_{i} \sum_{j} c_{i}x_{i}y_{j}$ could be linearized trivially, but as far as I can tell the method falls apart with inclusion of the $b_j$ scalar. The $b_jy_j$ term causes problems when for a given $j$ it's $\in \left ( 0, 0.8 \right )$, for example, instead of $\in \left ( 0, 1 \right )$.

---

EDIT: Fixed my representation of the objective function above thanks to @RobPratt comment.

So for example, assuming $x_1$ belongs to $m=5$ subsets, the term with $i=1$ becomes:

$$c_1x_1\left(1-b_1y_1 \right)\left(1-b_2y_2 \right)\left(1-b_3y_3 \right)\left(1-b_4y_4 \right)\left(1-b_5y_5 \right)$$

This is what I'm trying to linearize.

Answer 1

To linearize $c_i x_i b_j y_j$, rewrite as $c_i b_j z_{ij}$, where $z_{ij}$ arises from the usual linearization of a product of two binary variables, as in the link you provided. The constant $b_j$ does not cause any issue; just think of $c_i b_j$ as another constant.

But I don’t see any sixth-degree polynomial in your formulation. You have only a quadratic polynomial. Did you maybe instead want $$\sum_i c_i x_i \prod_j (1-b_j y_j)$$ as the objective function? In any case, polynomials of binary variables can be linearized by linearizing each product of binary variables.