0
$\begingroup$

I have an optimization problem where I have two sets containing $n$ items, which I must place inside $m$ arrays with the same capacity $c$. The cost of each array is equal to the cost of the most expensive item from the first array inside it plus the cost of each unique item in the second set it holds (if we have two equal items from the second set then we only add its cost once). If the array only has items from the second set, then we add an extra cost to it.

How would I be able to solve this problem? My first thought was to use the simplex method, but my problem isn't linear. Using backtracking starts to hang for relatively big instances (around $n$>30).

Here is an example, with mathematical formulation: Suppose we have $n=3$ different items $I$, with the following amounts: 2 of $I_1$, 1 of $I_2$ and 2 of $I_3$, where $I_3$ is a special item from set 2. We have $m=3$ arrays that can hold at most 2 items inside it. We could then create a matrix $M_{m\times n}$, to describe how many of each item is inside each array, where the rows represent the array and the columns the items inside it

$$ \left[ \begin{array}{c|ccc} & I_1 & I_2 & I_3 \\ array_1 & m_{11} & m_{12} & m_{13}\\ array_2 & m_{21} & m_{22} & m_{23}\\ array_3 & m_{31} & m_{32} & m_{33} \\ \end{array} \right] $$

Using this matrix we can write the constraints $$ \sum_{i=1}^3 m_{i,j} \leq 2, \ j=1,2,3 \\ \sum_{j=1}^3 m_{1,j} = 2 \\ \sum_{j=1}^3 m_{2,j} = 1 \\ \sum_{j=1}^3 m_{3,j} = 2 \\ $$

Let $w_n$ be the cost of the item $i$, with $w_1=30 > w_2=20$, $w_3=10$ and $w_s=15$ being the cost of having only item 3 in the array. $1(x)$ the step function (1 if x is bigger than 0 and 0 otherwise), then the cost, which I want to minimize is $$ C = \sum_{i=1}^3 [1(m_{i,1})]\ 30 + [1(m_{i,2})(1 - 1(m_{i,1}))]\ 20 + [1(m_{i,3})]\ 10 + [1(m_{i,3})(1-1(m_{i,1}))(1 - 1(m_{i,2}))]\ 15 $$ A possible solution which minimizes the cost is $$ \left[ \begin{array}{ccc} 2 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 2 \\ \end{array} \right] $$ But how to calculate it algorithmically?

Edit

Ok, by Rob suggestions, I need to do some linearization. Replacing $1(m_{ij})$ by a binary variable $x_{ij}$ and multiplying everything we end up with $$ C = \sum_{i=1}^3 30x_{i1} + 20(x_{i2}-x_{i2}x_{i1}) + 10x_{i3} + 15(x_{i3}-x_{i2}x_{i3}-x_{i1}x_{i3}+x_{i1}x_{i2}x_{i3}) $$ We also add the constraints: $$ x_{ij} \leq m_{ij} \leq u_{ij}x_{ij} $$ With $u_{ij}$ being a tight upper bound of $m_{ij}$

We then need to linearize the product between the binary variables introducing $z_{ij_1j_2}$ and $z_{ij_1j_2j_3}$ where $$ z_{ij_1j_2} \leq x_{ij_1}\\ z_{ij_1j_2} \leq x_{ij_2}\\ z_{ij_1j_2} \geq x_{ij_1} + x_{ij_2} - 1 $$ And $$ z_{ij_1j_2j_3} \leq x_{ij_n},\ n=1,2,3\\ z_{ij_1j_2j_3} \geq \sum_{n=1}^3 x_{ij_n} -2 $$

Which makes we end up with $$ C = \sum_{i=1}^3 30x_{i1} + 20(x_{i2}-z_{i12}) + 10x_{i3} + 15(x_{i3}-z_{i23}-z_{i13}+z_{i123}) $$

Can I then use the simplex method to solve this?

$\endgroup$
1
  • 1
    $\begingroup$ I made a few corrections to your linearization. The simplex method is for LP, but you have binary variables, so you would need to use a MILP solver. $\endgroup$ Commented Feb 16, 2023 at 15:27

1 Answer 1

Reset to default
1
$\begingroup$

You can linearize $1(m_{ij})$, where $u_{ij}$ is a constant upper bound on $m_{ij}$, by introducing a new binary decision variable $x_{ij}$ and imposing linear constraints: $$x_{ij} \le m_{ij} \le u_{ij} x_{ij}$$ To see that this works, just check the two cases:

  • If $x_{ij}=0$, then $0 \le m_{ij} \le 0$.
  • If $x_{ij}=1$, then $1 \le m_{ij} \le u_{ij}$.

Now replace $1(m_{ij})$ with $x_{ij}$ everywhere, yielding a polynomial with binary variables, which you can further linearize by introducing a binary decision variable for each product, as shown here. You can then call an integer linear programming solver.

As an alternative to the usual linearization of a product, you can get by with only two new variables per $i$ in your example. You want to minimize $$\sum_{i=1}^3 \left(30 x_{i1} + 20 x_{i2}(1 - x_{i1}) + 10 x_{i3} + 15 x_{i3}(1-x_{i1})(1 - x_{i2})\right).$$ Introduce binary decision variables $y_i$ and $z_i$, and rewrite your objective function as $$\sum_{i=1}^3 \left(30 x_{i1} + 20 y_i + 10 x_{i3} + 15 z_i\right).$$ Because we are minimizing and the objective coefficients are positive, we need only enforce two logical implications: \begin{align} (x_{i2} \land \lnot x_{i1}) &\implies y_i \tag1\label1 \\ (x_{i3} \land \lnot x_{i1} \land \lnot x_{i2}) &\implies z_i \tag2\label2 \end{align} Rewriting \eqref{1} in conjunctive normal form yields \begin{align} (x_{i2} \land \lnot x_{i1}) &\implies y_i \\ \lnot (x_{i2} \land \lnot x_{i1}) &\lor y_i \\ \lnot x_{i2} \lor x_{i1} &\lor y_i \\ (1 - x_{i2}) + x_{i1} + y_i &\ge 1 \tag3\label3 \end{align} Similarly, rewriting \eqref{2} in conjunctive normal form yields \begin{align} (x_{i3} \land \lnot x_{i1} \land \lnot x_{i2}) &\implies z_i \\ \lnot (x_{i3} \land \lnot x_{i1} \land \lnot x_{i2}) &\lor z_i \\ \lnot x_{i3} \lor x_{i1} \lor x_{i2} &\lor z_i \\ (1 - x_{i3}) + x_{i1} + x_{i2} + z_i &\ge 1 \tag4\label4 \end{align} So linear constraints \eqref{3} and \eqref{4} achieve the linearization.

$\endgroup$
9
  • $\begingroup$ So, if $m_{ij}$ is 2, then I must choose $u_{ij}=2$ or a value bigger than 2(as in, any upper bound is enough)? $\endgroup$ Commented Feb 16, 2023 at 12:06
  • 1
    $\begingroup$ Any upper bound is sufficient, but smaller values are preferable numerically. For your example, you can take $u_{1j}=u_{3j}=2$ and $u_{2j}=1$. $\endgroup$ Commented Feb 16, 2023 at 13:39
  • $\begingroup$ Thank you. I edited my post doing the linearization you suggested and then linearized the binary variables which would multiply each other in the example. Is everything ok to apply a linear optimization algorithm like simplex with the new cost function and constraints? $\endgroup$ Commented Feb 16, 2023 at 14:55
  • $\begingroup$ Instead of doing $(1-1(m_{i,1}))(1−1(m_{i,2})$ could I do $1-1(m_{i,1}+m_{1,2})$ with constraint $x_{i12} \leq m_{i_1} + m_{i_2} \leq u_{i1} u_{i2} x_{i12}$? That would simplify the constraints for larger sets of different items $\endgroup$ Commented Feb 16, 2023 at 17:06
  • $\begingroup$ Those two expressions are not equal when $m_{i1}=m_{i2}=1$. An alternative approach to simplify the linearization is to note that $1-y$ is binary iff $y$ is binary and then explicitly introduce binary variable $z$ to replace $1-y$, together with linear constraint $y+z=1$. This way, you need to linearize only two products (the ones with coefficients 20 and 15) in your example. $\endgroup$ Commented Feb 16, 2023 at 17:39

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.