# Multi-objective optimization for resource allocation

Say I have several portfolios of the format:

Product Name Product Amount Price per unit
A_1 10 2
B_1 20 6
... ... ...
Z_1 30 7

We can call this $$\text{Portfolio}_{1}$$.

Similarly, $$\text{Portfolio}_{2}$$ could look like:

Product Name Product Amount Price per unit
A_2 100 3
B_2 50 8
... ... ...
Z_2 50 17

For simplicity's sake we can assume we have 13 distinct portfolios.

I have two groups of customers. One that enters in a one year contract with me in January and the other group enters in February.

I know the monthly demand for each group in each month. However, my objective is to reach an "average annual price target".

For example, say the January group has monthly demand targets of

$$[10,200,300,400,500,600,700,800,900,100,110,120]$$

Where the index of each element corresponds to the monthly demand. So I need to allocate $$10$$ units from $$\text{Portfolio}_{1}$$, $$200$$ units from $$\text{Portfolio}_{2}$$ etc.

From $$\text{Portfolio}_{1}$$ I can allocate all of product $$A_1$$. I then need to calculate the average price, which in this case is

$$J_{1} = \frac{10*2}{10} = 2$$

From $$\text{Portfolio}_{2}$$ I could allocate all of $$A_2, B_2, Z_2$$ to meet the monthly demand of $$200$$ (Note that we also need to allocate products from $$\text{Portfolio}_{2}$$ to meet the demand for the February group). And the resulting average price would be

$$J_{2} = \frac{100*3 + 50*8 + 50*17}{200}$$

My objective is to reach a target of all the averages, lets say for the January group this is 50. And for the Febuary group it is 100 I.e.

$$J^{*} = \frac{J_1 + J_2 + ... + J_{12}}{12} = 50$$

$$F^{*} = \frac{F_1 + F_2 + ... + F_{12}}{12} = 100$$

So the January group gets products from $$\text{Portfolio}_{1},..., \text{Portfolio}_{12}$$. The Febuary group gets products from $$\text{Portfolio}_{2},..., \text{Portfolio}_{13}$$. So as you can see, there is some overlap.

My approach:

I have never worked with multi-objective algorithms before so I am not even sure if they are applicable. So any feedback on my naive approach would be appreciated.

So, as my objective is to reach a target average value, I broke this down to linear programming problems. For example, as I know that the January group has a target of 50, I set up 12 linear programming problems where I allocated products from each portfolio with the objective of reaching a value of 50 for each component, subject to the monthly demand constraint.

I.e., I wanted each $$J_1, J_2, ... J_{12}$$ to reach a value of 50, subject to meeting the monthly demand constraints. Similarly, for February, I wanted each $$F_1,...F_{12}$$ to be 100, subject to the monthly demand constraint for the February group.

So my question is essentially if there is a better approach. Rather than having each $$J_i, F_i$$ be the "annual average target", is there a better distribution?

EDIT:

The confusion I am having with setting this up as a single linear program (where I aim to minimise the sum of absolute deviation from $$J*, F*$$) is that it seems like I have two types of decision variables now. I have the individual monthly components (the J_i, F_i) and the allocation of products. Where the allocation of products obviously affect the (J_i, F_i). So as $$J_i, F_i$$ are functions of the product allocations I suppose there is in fact just one decision variable but I am just having a hard time formulating the problem.

So would the problem look something like:

$$\min_{J_{1},...,J_{12},F_{1},...F_{12}} [(J^{*} - 50) + (F^{*} - 100)]$$

Where I would somehow have to impose the demand constraints on each $$J_{i}, F_{i}$$? But since (J_i, F_i)'s are average prices, I don't quite see how I can impose demand constraint on them.

• Your "January group" vector has 12 components but you said to assume 13 portfolios. Typo somewhere?
– prubin
Commented Aug 27, 2022 at 19:35
• Is the 10 units for A_1 an annual supply or a monthly supply? Can you allocate fractional amounts from a portfolio (e.g., 3.7 units from B_2 in March)? Do you want to hit the average price targets exactly, or average price at most target, or average price at least target?
– prubin
Commented Aug 27, 2022 at 19:37
• I have 13 portfolios because the February Group enters one month after the Jan group, so their allocation starts from Portfolio_2. I'll update the post by making the relevant section bold. And A_1 is a monthly supply, so we have 10 units available from product A_1 in Portfolio_1. So this cannot be used in e.g. J_2, F_2 or any other month other than January. Commented Aug 27, 2022 at 19:44
• So Portfolio_1,...,Portfolio_12 can be thought of as monthly portfolios. The January Group is allocated from these. The February Group receives allocations from Portfolio_2,...,Portfolio13, where you can think of Portfolio_13 as the portfolio from January of the following year. Commented Aug 27, 2022 at 19:50

This is not necessarily a multiobjective problem. One approach is to write a single linear program (if allocation amounts are continuous) or mixed integer linear program (if allocation amounts are integer-valued) where the objective function minimizes the sum of the absolute deviations of $$J*$$ and $$F*$$ from their respective targets. I'm assuming that the goal is to hit the targets exactly, rather than staying at or under the targets (or at or over the targets). If you want to prioritize one group over the other, you can weight one of the objective terms higher than the other.

If one group has an absolute priority over the other (e.g., get as close as possible to the January target regardless of how much that makes you miss the February target), you can use a lexicographically ordered objective. One way to do that is to solve two problems. In the first problem, get as close as you can to the higher priority target without regard for the lower priority target. In the second problem, get as close as possible to the lower priority target with the added constraint that you cannot miss the higher priority target by more than what the optimal solution to the first model accomplished. Another way to handle it is to use a solver that supports lexicographic objectives. (Recent versions of CPLEX do, for instance.)

Addendum: Here is an LP formulation for the single objective case. I'll number the months 1 through 13, where the January has demands $$d_{1,1},\dots,d_{1,12}$$ and the February group has demands $$d_{2,2},\dots,d_{2,13}.$$ The available amount of any product $$i$$ is $$S_{i}$$ and its unit cost is $$c_{i}.$$ The set of products available in month $$t$$ is denoted $$P_{t}.$$ For instance, $$P_{2}=\left\{ A\_2,\dots,Z\_2\right\} .$$

Variables $$x_{1,i}\ge0$$ capture the amount allocated of product $$i$$ to demand from the January group in the appropriate month (e.g., if $$i$$ is B_7'' then it must be month 7). $$J_{t}$$, $$F_{t}$$, $$J^{*}$$ and $$F^{*}$$ are as in the original post. Variables $$y_{J}$$ and $$y_{F}$$ capture the absolute deviations of $$J^{*}$$ and $$F^{*}$$ from their targets (denoted $$T_{J}$$ and $$T_{F}$$ respectively).

The objective is to minimize $$y_{J}+y_{F}.$$ The first set of constraints ensures that each group gets their required allocation in each month.

\begin{align*} x_{1,A\_1}+\dots+x_{1,Z\_1} & =d_{1,1}\\ \cdots\\ x_{2,A\_13}+\dots+x_{2,Z\_13} & =d_{2,13}. \end{align*}

The second set of constraints ensures that you don't allocate product you don't have.

\begin{align*} x_{1,A\_1} & \le S_{A\_1}\\ \cdots\\ x_{1,A\_2}+x_{2,A\_2} & \le S_{A\_2}\\ \cdots\\ x_{2,Z\_13} & \le S_{Z\_13} \end{align*} where the left sides have two terms except in the first and last January (where one of the two groups is not in play).

Finally, we need constraints to define the remaining variables. \begin{align*} J_{t} & =\frac{1}{d_{1,t}}\sum_{i\in P_{t}}c_{i}x_{1,i}\quad t=1,\dots,12\\ F_{t} & =\frac{1}{d_{2,t}}\sum_{i\in P_{t}}c_{i}x_{2,i}\quad t=2,\dots,13\\ J^{*} & =(J_{1}+\dots+J_{12})/12\\ F^{*} & =(F_{2}+\dots+F_{13})/12\\ y_{J} & \ge J^{*}-T_{J}\\ y_{J} & \ge T_{J}-J^{*}\\ y_{F} & \ge F^{*}-T_{F}\\ y_{F} & \ge T_{F}-F^{*}. \end{align*}

• Many thanks for the feedback! I like the first approach you mentioned (the allocation amounts are indeed continuous). I will add an edit to my post clarifying a source of confusion with this approach. Commented Aug 27, 2022 at 20:17