Linear programming - combining models

Question

(moved it here from math.se - it wasn't getting enough love out there. Sorry!)

So, I've been assigned with modeling a multi-processor setup using linear (integer) programming. Basically, there are five processors with links between them, and the goal is to find the optimal schedule of communication/processing as to minimize the time of processing a set amount of data. The graph is as follows:

---
|A|
---
 |
 |
---    ---
|B|----|D|
---    ---
 |      |
 |      |
---    ---
|C|----|E|
---    ---

with A being the data source. Now, there are a few different scenarios (related to the flow direction and the order of sending/receiving data), and for each scenario, the inequalities representing the processing time are different.

For example, if data flows from B to D, from B to C, from D to E, and from C to E, B communicates first with C, and then with D, and E receives first from C, and then from D, the total processing time for C is equal to:

Tc >= Cab + Cbc + Cce + Sc*Dc //Sc is constant

If, however, B sends data first to D, and then to C, then it's

Tc >= Cab + Cbd + Cbc + Cce + Sc*Dc //Sc is constant

And so on. Overall, there are 10 such scenarios, and for each one there's a couple of inequalities that need to be satisfied. What I need is a way to communicate to my solver "pick one of those sets of inequalities and don't mind about the rest". I presume I'll have to use some binary variables to encode those, I've also heard something about multiplying the variables by a huge value to "simulate" a conditional, but currently I can't find a way to "merge" all those mini-models into one and let the solver pick the best scenario.

Answer 1

Here's the sketch of the formulation:

You have ten scenarios, S1 through S10

Let's introduce binary variables Y_i which denotes which of the 10 scenarios is in play. So these become a Specially Ordered Set :

 Sum (over i in 1..10 )  Y_i = 1 (Only one scenario holds at a time.)

Requirement

For each scenario, there are a few inequalities that have to be obeyed. All other inequalities (applicable to other scenarios) should be ignored.

Let M be a big number. Say two orders of magnitude greater than the maximum possible processing time for any dataset.

Objective Function:

Min T

Constraints:

T >= Ta
...
T >= Tc
..
T >= Te

Let's use your scenario...Let's call it Scenario s. For each inequality that needs to be satisfied under scenario s, we introduce a M(1-Y_s) term to the LHS of the greater than inequality.

Inequalities for scenario s:

Tc + M(1-Y_s) >= Cab + Cbc + Cce + Sc*Dc //Sc is constant
Tc + M(1-Y_s) >= Cab + Cbd + Cbc + Cce + Sc*Dc //Sc is constant
...
...

Inequalities for some other scenario t:

Td + M(1-Y_t) >= Cde + Cbc + Sd*Dd //Sd is constant
Td + M(1-Y_t) >= Cde + Cbd + Cbc + Cce + Sd*Dd //Sd is constant
..

Inequalities for scenario u:

...
...
and so on.

Depending on whichever Y_i is 1, those M(1-Y_i) terms will become zero. So the inequalities will be enforced. For all the M(1-Y_j)..The left hand side will be a huge number, and the inequality will be always hold trivially.

The nice thing is that since the overall objective is to minimize T, which in turn is the max of Ta...Te...over all 10 scenarios, the Solver will automatically pick the most optimal scenario.

Hope that helps.