4
$\begingroup$

I'm writhing an essay on a optimization model. But I can't seem to find a answer to this problem. Is there anybody who could enlighten me?

by the way, I am new to this forum. So let me say sorry in advance for asking the question this way.

Ok, lets say there is a $m$ number of boxes $i$ ($i=1,2,...,m$). Furthermore, every box has his own estimated unpacking time $r_i$ (with $r_i$ as integer and $r_i \geq 1$) and profit $p_i$ (with $p_i \geq 0$). If we'd like to maximize the profit with a limited unpacking time, say $T$, it could be considered a Knapsack problem or a integer programming problem with $x_i \geq 0$. It may be formulated as the following maximization problem:

\begin{equation} maximize \ \ \sum_{i=i}^{m} x_i p_i \end{equation}

\begin{equation} subject \ \ to \ \ \sum_{i=i}^{m} x_i r_i \leq T \end{equation}

\begin{equation} x_i \in \{ 0,1 \}, \ \ i=1,2,...,m \\, \end{equation}

where $x_i$ is a binary variable equaling 1 if box $i$ should be unpacked.

In addition to the problem there's another positive integer coefficient $g_i$ which represents the number of goods box $i$ contains. So, if we would like to maximize the number of total goods it gives us:

\begin{equation} maximize \ \ \sum_{i=i}^{m} x_i g_i \end{equation}

\begin{equation} subject \ \ to \ \ \sum_{i=i}^{m} x_i r_i \leq T \end{equation}

\begin{equation} x_i \in \{ 0,1 \}, \ \ i=1,2,...,m \\, \end{equation}

where $x_i$ is a binary variable equaling 1 if box $i$ should be unpacked.

But there is more, lets say we know the boxes contain four sorts of products (product a, b, c and d). So let the value of the coefficients a,b,c and d in box $i$ be binary ($a_i, b_i, c_i, d_i \in \{ 0,1 \}$). So when the coefficients $a,b,c,d=1$ it means the box contains the productsort.

Further more, there are four integer coefficients ($A_i, B_i, C_i, D_i \in N $) representing the number of products (a,b,c and d) in box $i$, so $g_i =A_i + B_i + C_i + D_i$, with ($A_i, B_i, C_i, D_i \geq 0$)

As last addition to the problem: The profit of box $i$ is the sum of the profit of its content. Lets $pa_i, pb_i, pc_i, pd_i$ be positive coefficients which represent, respectively the profit of the products a, b, c and d in box $i$.

So my question is: Is there a way you can rewrite the Cost function to maximize the profit and number of packages?

$\endgroup$
1
$\begingroup$

It sounds as though you have several things that you would like to maximize simultaneously. That makes this a multi-objective optimization problem. As the Wikipedia page indicates, there are quite a few ways to deal with multiple objectives. A non-exhaustive list includes: taking a weighted sum of the various objectives (where you have to choose the weights up front); minimizing the distance (in some metric) to a "utopia" point (which typically consists of the best value of each individual objective if you optimize it ignoring the others); optimizing one objective while setting constraints on how bad the others can be; and "goal programming", in which you set "aspiration levels" for each objective and prioritize them, then sequentially minimize the lack of achievement of each aspiration level subject to the requirement that you don't fall any further below any higher priority aspiration level.

$\endgroup$
  • $\begingroup$ Thanks that's the first step! I am going to find some literature on the multi-objetive optimization problem. $\endgroup$ – J.O.P.P. Jan 25 at 10:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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