I need some advice on how to describe this as an optimization problem. There are a number of items stored in warehouses, that need to be reorganized in order to minimize new purchases.
To illustrate the problem, here is some example data:
Warehouse | Item | Demand | Stocks |
----------|------|--------|--------|
A | 1 | 20 | 30 |
A | 2 | 10 | 20 |
B | 1 | 20 | 0 |
B | 2 | 20 | 5 |
C | 1 | 40 | 10 |
C | 2 | 20 | 0 |
Also, the following costs per transfer between warehouses should apply (that I'd like to apply as a penalty to my objective):
From | To | Cost |
-----|------|-------|
A | B | 5 |
A | C | 0 |
B | C | 2 |
My goal is to find optimal transfers that satisfy most of the demand, while keeping transport costs as low as possible. Should I store transfer data in a separate vector/matrix? Also, how could I introduce transfer costs in the problem?
You can solve this as a multicommodity flow problem. A linear programming formulation is as follows. Let decision variable $x_{i,j,k} \ge 0$ denote the flow (number of items) transferred from warehouse $i$ to warehouse $j$ of commodity $k$, with unit cost $c_{i,j}$. Let $b_{i,k}$ be the net supply (stock minus demand) at warehouse $i$ for commodity $k$. The objective is to minimize $\sum_{i,j,k} c_{i,j} x_{i,j,k}$ subject to flow balance constraints for all $i$ and $k$: $$\sum_{j \not= i} (x_{i,j,k} - x_{j,i,k}) \le b_{i,k}$$ This formulation assumes that the total supply is at least the total demand for each commodity $k$. In your case, this is not true, so you can introduce a dummy node to capture the unmet demand. You will need to somehow penalize flow out of the dummy node to encourage meeting the demand.
By the way, unless there are upper bounds on the total flow (summed across commodities) for each arc, you can solve a separate problem for each commodity.