2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Is $b_j$ a constant or a decision variable? $\endgroup$
    – RobPratt
    Oct 17, 2022 at 2:35
  • $\begingroup$ @RobPratt $b_j$ is a constant between 0 and 1 $\endgroup$
    – jpaul45
    Oct 17, 2022 at 5:30

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Sorry for the confusion, your representation of the objective function with product summation is what I intended. I've edited my original post to reflect it. So your recommendation is to expand the product in the objective function and linearize each resulting term individually, correct? It's going to be a mess to code, but I'll try to work through it. Thanks for the help. $\endgroup$
    – jpaul45
    Oct 17, 2022 at 21:47
  • $\begingroup$ Some solvers will automatically linearize this for you. $\endgroup$
    – RobPratt
    Oct 18, 2022 at 3:53
  • $\begingroup$ Are you able to share your data? $\endgroup$
    – RobPratt
    Oct 18, 2022 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.