Sparse input data and data binding
Solver Foundation supports flexible data binding so that the algebraic model can be separated from the data source. In Solver Foundation, both parameters and decisions can be bound to data source. It makes writing and maintaining models really easy.
To bind a parameter to a data source, we usually need to specify the data source, the value field, and indexes. For example, the following parameter WarehouseCap is bound to the table that has two columns.
The table looks as follows.
warehouse |
capacity |
1 |
10 |
2 |
29 |
3 |
13 |
Column warehouse is the index column/field, and column capacity is the value column/field.
In C#, the binding can be set via the following line.
_model.WarehouseCap.SetBinding(warehouseCaps, "Capacity", "Warehouse");
assuming warehouseCaps is an IEnumerable that contains the data.
The sparse data case is where the table contains multiple index columns and not all the combinations of the index values exist in the table. For example, there could be a table that records the cost of shipping goods from warehouses to stores. However, it is usually not the case that every warehouse can ship goods and every store. For example,
warehouse |
store |
cost |
1 |
2 |
100 |
2 |
3 |
200 |
3 |
1 |
150 |
Such table represents input data that are sparse. By default, the missing rows all have the value column being zero.
Currently in Solver Foundation v2.0, we cannot bind to such sparse data directly. However, we observe that the values appearing in an index column of the sparse table form a subset of the values allowed for that index column. Furthermore, Solver Foundation allows parameters to appear as the indexes to other parameters or decisions. We can use the following approach to bind to this sparse table.
Let us introduce a helper column called costid into the table.
costid |
warehouse |
store |
cost |
0 |
1 |
2 |
100 |
1 |
2 |
3 |
200 |
2 |
3 |
1 |
150 |
Now we create two extra parameters called CostWarehouse and CostStore, which will be bound to the warehouse column and store column respectively. The needed parameter Cost will be bound to the cost column as we expected. All three parameters now use costid as the index.
Here are the actual definitions for the three parameters.
Parameters[ Sets[Any], costid ], Parameters[ Integers[0, Infinity], CostWarehouse[costid], CostStore[costid] ], Parameters[ Reals[-Infinity, Infinity], Cost[costid] ], |
Assume we have a decision called Ship defined as follows.
Parameters[ Sets[Any], warehouse, store ], Decisions[ Integers[0, 1], Ship[warehouse, store] ], |
Ship[w, s] being 1 if and only if we want to ship goods from warehouse w to store s.
Now suppose we want to construct as constraint that says “the total cost of shipping is between 100 and 400. The constraint can be written as follows.
100 <= Sum[{id, costid}, Cost[id] * Ship[CostWarehouse[id], CostStore[id]]] <= 400 |
Notice that we iterate through all rows in the cost table and use parameter CostWarehouse[id] and CostStore[id] as indexes on decision Ship.
To ensure that we do not ship any goods from incompatible warehouse and store pairs, we add the following constraint using the fact that default values are zero:
Foreach[{w, warehouse}, {s, store}, Ship[w, s] <= Sum[{id, costid}, AsInt[CostWarehouse[id] == w & CostStore[id] == s]] |
We leave it to the reader to figure out how this constraint works. Notice that, in the last constraint, the complicated right-hand side of the inequality actually is reduced to a constant value. So the model is still a MILP model.
Here is the complete model.
Model[ Parameters[ Sets[Integers[0, Infinity]], costid, warehouse, store ], Parameters[ Integers[0, Infinity], CostWarehouse[costid], CostStore[costid] ], Parameters[ Reals[-Infinity, Infinity], Cost[costid], WarehouseCap[warehouse], StoreCap[store] ], Decisions[ Integers[0, 1], Ship[warehouse, store] ], Constraints[ Constraint1 -> 100 <= Sum[{id, costid}, Cost[id] * Ship[CostWarehouse[id], CostStore[id]]] <= 400, Constraint2 -> Foreach[{w, warehouse}, {s, store}, Ship[w, s] <= Sum[{id, costid}, AsInt[CostWarehouse[id] == w & CostStore[id] == s]]] ], Goals[ Maximize[ Goal1 -> Annotation[Sum[{w, warehouse}, {s, store}, Ship[w, s]], "order", 0] ] ] ] |
Here is a sample run.
[11/2/2009 10:54:59 PM] Solve started... [11/2/2009 10:55:00 PM] ===Solver Foundation Service Report=== Datetime: 11/2/2009 10:55:00 PM Model Name: Default Capabilities Requested: MILP Solve Time (ms): 34 Total Time (ms): 187 Solve Completion Status: Optimal Solver Selected: SolverFoundation.Plugin.Gurobi.GurobiSolver Algorithm: Dual Arithmetic: Double Variables: 9 -> 20 + 11 Rows: 11 -> 11 Nonzeros: 21 Eliminated Slack Variables: 0 Pricing (double): Automatic Pivot Count: 0 Phase 1 Pivots: -1 + 0 Phase 2 Pivots: -1 + 0 Factorings: -1 + 0 Degenerate Pivots: -1 (0.00 %) Branches: 0 ===Solution Details=== Goals: Goal1: 2 Decisions: Ship(1, 2): 1 Ship(2, 3): 1 Ship(3, 1): 0 Ship(1, 1): 0 Ship(1, 3): 0 Ship(2, 1): 0 Ship(2, 2): 0 Ship(3, 2): 0 Ship(3, 3): 0 [11/2/2009 10:55:00 PM] Solve Complete |
The actual workbook is attached too.
Lengning