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.
Thanks in advance,
Ray
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.