How do you formulate a "multi-supplier" problem as a MOP?

Question

How do you formulate a "multi-supplier" problem as a MOP (Multi-Objective Optimization Problem)?

E.g. a basic linear program where you have some suppliers for resources and you are the purchaser. The goal would be to decide from which suppliers to get what (or one could make other objectives such as minimizing cost, minimizing distance, ...).

If I had only one supplier then intuitively I could merely express the products as some kind of linear combination. But what if I have to do a choice on each product? Would I specify that the $x_i$ must take values from pre-defined sets? Where the set contains "the possible costs that it can take"?

---

What if I just did like ($S_i$ is for supplier $i$):

$$\min S_1+S_2+S_3$$

where each $S_i=\sum_i c_i x_i$

where $c_i$ is cost of resource $i$ and $x_i$ is the solvable parameter, i.e. e.g. "number of units bought".

Then if I minimized this I could discover what choices give minimum cost?

But this is not a MOP? So if I wanted to add the objective "minimize travelled distance", then what should I do?

Answer 1

Let me first propose a way to model this problem not as a multi-objective problem.

Sets:

• $I$ = set of resources (products)
• $J$ = set of suppliers

Parameters:

• $c_{ij}$ = the cost to purchase resource $i$ from supplier $j$
• $d_i$ = total required number of units of resource $i$ that must be purchased
• $r_{ij}$ = number of units of resource $i$ available from supplier $j$ (this was not in your question but I'll add it anyway; you can always set it to $\infty$)

Decision Variables:

• $x_{ij}$ = number of units of resource $i$ purchased from supplier $j$

Linear Programming (LP) Formulation:

$$\begin{alignat}{2} \text{minimize} \quad \sum_{i\in I} \sum_{j\in J} & c_{ij}x_{ij} && \\ \text{subject to} \quad \sum_{j\in J} x_{ij} & = d_i &\quad& \forall i\in I \\ 0 & \le x_{ij} \le r_{ij} && \forall i\in I, j\in J \end{alignat}$$

The objective function calculates the total cost; the first constraint ensures we purchase enough of each resource; and the second constraint ensures we purchase no more than the maximum amount (and no less than 0).

Now, your question seems to suggest that you want to formulate this problem as a multi-objective problem, or you think it should be. To that point, no -- there is no particular reason why this sourcing problem should itself be formulated as a multi-objective problem.

However, if you have a second objective that you want to consider, it of course becomes multi-objective. You said "minimize traveled distance"; I'm interpreting this to mean you want to minimize the total distance traveled to the suppliers. To avoid having to introduce new binary variables, let's assume that you want to minimize the distance weighted by the volume. So let $t_i$ be the distance to supplier $i$. Then you have a second objective $$\text{minimize} \quad \sum_{i\in I} \sum_{j\in J} t_ix_{ij}.$$

To formulate this as a multi-objective problem, it's typical to just write both objectives along with the constraints:

Multi-Objective Formulation:

$$\begin{alignat}{2} \text{minimize} \quad z_1 = \sum_{i\in I} \sum_{j\in J} & c_{ij}x_{ij} && \\ \text{minimize} \quad z_2 = \sum_{i\in I} \sum_{j\in J} & t_ix_{ij} && \\ \text{subject to} \quad \sum_{j\in J} x_{ij} & = d_i &\quad& \forall i\in I \\ 0 & \le x_{ij} \le r_{ij} && \forall i\in I, j\in J \end{alignat}$$

To solve this problem -- i.e., to find the Pareto curve, or the set of non-dominated solutions -- you have two choices. You can use the weighting method, where you combine the two objectives into a weighted sum:

$$\text{minimize} \quad \alpha z_1 + (1-\alpha)z_2$$

and solve the problem with the original constraints. By varying $\alpha$ ($0 \le \alpha \le 1$) you get different non-dominated solutions.

Or you can use the constraint method, where you move one of the objectives into the constraints:

$$\begin{align} \text{minimize} \quad & z_1 \\ \text{subject to} \quad & z_2 \le C \\ & \text{[plus the other constraints]} \end{align}$$

By varying $C$, you get different non-dominated solutions.

This is the general approach for any problem -- not just sourcing problems -- and not just for the particular form of $z_2$ used here. There are pros and cons of the weighting and constraint methods, which I won't get into.

Hope this helps.

By the way: There is an effort to launch a Stack Exchange site for operations research, where questions like this will be welcomed. You might consider committing to that site if you're interested.