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?
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:
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.