Multi-objective optimization for resource allocation

Question

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.

Answer 1

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*}