# Is there a name for this optimization algorithm?

I'm a software developer trying to design an optimization algorithm and I'm wondering if what I'm trying to do resembles any of these. There's a daunting number and rather than read each one, perhaps some one with a stronger math background could digest the following requirements and help me identify what kind of algorithm(s) I should read up on.

• There is a set of resources and a set of providers.
• Each provider offers every resource but at a different cost.
• There is a base cost for accessing a new provider so the cost of accessing a new provider might negate the savings of that provider's lower cost for the resource.
• I need to be able to determine from which provider(s) to acquire each resource such that the total cost is as low as possible.

Ray

• Are any of the providers "old" beforehand? – Hagen von Eitzen Jan 27 '14 at 15:53

This can be formulated as a mixed-integer linear program (MILP; or sometimes just MIP).

Number the resources $i=1,2,\dots, m$ and the providers $j=1,2,\dots,n$.

Construct a matrix $C\in\mathbb{R}^{m\times n}$, so that the cost of resource $i$ from provider $j$ is $C_{ij}$. Let $\ell\in\mathbb{R}^n$ be a nonnegative vector of resource requirements; that is, you are required to obtain exactly $\ell_i$ of resource $i$.

Our primary optimization variable is a matrix $X\in\mathbb{R}^{m\times n}$, with $X_{ij}$ denoting the amount of resource $i$ to obtain from provider $j$. Ignoring the access costs for a moment, the model looks like this: $$\begin{array}{ll} \text{minimize} & \sum_{ij} C_{ij} X_{ij} \\ \text{subject to} & \sum_j X_{ij} =\ell_i, ~ i=1,2,\dots,m \\ & X_{ij} \geq 0, ~ i=1,2,\dots,m,~j=1,2,\dots,n \end{array}$$ Of course, this is trivial to solve; simply select the least expensive provider for each product.

Now to handle the access costs. Let $f\in\mathbb{R}^n$ be a vector of the access costs, and introduce a new binary variable $y\in\{0,1\}^n$; $y_j=1$ if provider $j$ is being accessed, and $y_j=0$ otherwise. Then $\sum_j f_j y_j$ is the total access cost, and the model looks like this: $$\begin{array}{ll} \text{minimize} & \sum_j f_j y_j + \sum_{ij} C_{ij} X_{ij} \\ \text{subject to} & \sum_j X_{ij} = \ell_i, ~ i=1,2,\dots,m \\ & \sum_j X_{ij} \leq L y_j, ~ j=1,2,\dots,n \\ & X_{ij}\geq 0,~ y_j\in\{0,1\}, ~ i=1,2,\dots,m,~j=1,2,\dots,n \end{array}$$ where $L=\sum_i \ell_i$. It is not difficult to see why this works: if $y_j=0$, then the $Ly_j$ inequality prevents any resources from being selected from provider $j$. If $y_j=1$, then in theory, all of the resources can be selected from that vendor, since $\sum_j X_{ij} \leq \sum_i \ell_i = L$.

Hopefully you can see simple ways to extend this problem: for instance, you could impose capacity limits on each provider.

EDIT: One addition: some linear programming treatments and/or software prefer all inequalities or all equations, instead of a mixture of both. In this case, if the costs $C_{ij}$ are positive, then you may safely change the $\sum_j X_{ij}=\ell_i$ constraints to $\sum_j X_{ij} \geq \ell_i$ without affecting the solution.

• Thank you! This looks promising. Now I just have to digest it and translate it into software. – Raymond Saltrelli Jan 27 '14 at 21:20