So I have a problem, that is really similar to the assignment problem.
Basically there is a company producing square envelopes. A number of papers should be put into the envelope. Exactly one paper pr envelope the papers are square and the sidelenghts of the papers are between 120mm to 900mm.
The size of the document i is $s_i$
There are S different sizes of envelopes, and we can ignore the thickness of the envelope.
There are N documents.
We want to choose the size of the envelopes, so that the the total amount of (surface
area) of paper used to produce the envelopes is minimized.
The problem can be described using an assignment formulation: For $i = 1, . . . , N$ and $j = 1, . . . , S$ define $x_{ij}$ by: \begin{cases} 1 & \text{if document $i$ is chosen} \\ 0 & \text{Otherwise} \end{cases} Define $a_i$ as area of envelope $j$ for $j = 1, . . . , S.$ we have these constraints:
\begin{align*} \min &\sum_{i=1}^{N}\sum_{j=1}^{S}a_jx_{ij}\\ st. &\sum_{j=1}^{S}x_{ij}=1, \quad i=1,...,N\quad (Assign)\\ &x_{ij}=1 \: \text{then}\: a_j\geq s_i^2, \quad i=1,...,N\: j = 1, . . . , S\quad (fit)\\ &x_{ij}\in\{0,1\}, \quad i=1,...,N\: j = 1, . . . , S\\ &a_j\geq 0\quad j = 1,...,S\\ \end{align*}
There are two problems. 1) The objective function is not linear. 2) the (fit) constaint is not written as a constraint.
Question: Introduce variable $y_{ij}=a_jx_{ij}$ and use this to establish a model with a linear objective and linear constraints.
Attempt:
Ok, so I thought of substituting the variable in the objective function. Now I have:
$$\min \sum_{i=1}^{N}\sum_{j=1}^{S}y_{ij}$$
Is this enough to solve the problem with the objective function?
And can someone help me with how to solve the problem with the constraints?
Any help is appreciated! :)
You need to introduce additional constraints to linearize the product. See https://or.stackexchange.com/questions/6028/mixed-integer-optimization-with-bilinear-constraint