# How to solve a Multi-Objective optimization (Knapsack problem)

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:

$$$$maximize \ \ \sum_{i=i}^{m} x_i p_i$$$$

$$$$subject \ \ to \ \ \sum_{i=i}^{m} x_i r_i \leq T$$$$

$$$$x_i \in \{ 0,1 \}, \ \ i=1,2,...,m \\,$$$$

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:

$$$$maximize \ \ \sum_{i=i}^{m} x_i g_i$$$$

$$$$subject \ \ to \ \ \sum_{i=i}^{m} x_i r_i \leq T$$$$

$$$$x_i \in \{ 0,1 \}, \ \ i=1,2,...,m \\,$$$$

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?

• or.stackexchange.com Jan 24, 2020 at 8:17
• You could try dynamic programming or simply brute force. Jan 25, 2020 at 11:29