Originally posted by: SaqibIlyas

I found the following message posted by on a forum by Michael Hennebry:

"If one has 100 things, each of which is to be associcates with one of a hundred places and one of a hundred time intervals, inefficient formulation could produce a million thing-place-time variables explicitly constrainted to be binary. A more efficient formulation would have 10,000 thing-place and
10,000 thing-time variables explicitly constrained to be binary. Even if one needs the million thing-place-time variables, they wouldn't need to be explicitly constrained to be binary."

I didn't quite understand the suggested sort of representation. I posted to the original forum, but did not receive an answer. Can someone on this forum elaborate on this? Or perhaps suggest another more relevant forum where I might find an answer?
Thanks and best regards
Saqib
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SaqibIlyas

Here is the link to that posting:
http://www.mathkb.com/Uwe/Forum.aspx/op-research/1594/About-a-huge-MIP-problem
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I'm not sure this will fully answer your question, but it should get you started. Suppose I have a problem that involves assigning jobs (subscript j) to machines (subscript m) at various times (subscript t). As a first cut, you might be tempted to create a binary variable assign[j,m,t]. If we let J, M and T be the number of jobs/machines/times respectively, you would have J*M*T binary variables.

Now suppose I create binary variables makeOn[j,m] and makeAt[j,t], and define assign[j,m,t] to be continuous (and nonnegative). I now have J*M*T continuous variables and J*M + J*T binaries, so more variables overall but fewer (many fewer?) binaries. I add constraints that assign[j,m,t] <= makeOn[j,m] and assign[j,m,t] <= makeAt[j,t]. If necessary, I can also add assign[j,m,t] >= makeOn[j,m] + makeAt[j,t] - 1. So I get a valid model with more constraints and more variables overall, but fewer binary variables (which means less depth to the search tree).

In some situations, I think the assign variables can be dispensed with entirely, and you can live with just the makeOn and makeAt variables.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SaqibIlyas

Thanks Paul. I'll go back to the drawing board with this information. If I have any other questions or need feedback on the revised formulation, I'll post again to this thread.
Thanks again.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SaqibIlyas

That sort of formulation works fine in case each job must be mapped to a machine at only one interval out of T, right? What if each job must be mapped to a machine at every interval? This sort of formulation wouldn't work in that case, right? Can we still reduce the number of binary variables in that case?
Thanks and best regards
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> SaqibIlyas wrote:
> That sort of formulation works fine in case each job must be mapped to a machine at only one interval out of T, right?

It works when jobs are assigned to a single machine (which has to be enforced by a constraint) but can be on that machine at multiple times. It also works if jobs can occupy multiple machines but each job has to be processed in a single time period. It does not work if a single job can occupy two different machines at different times (i.e., job j is processed by machine m at period t and machine m'!=m at period t'!=t). Off-hand, I don't know a trick for reducing the number of binary variables in that scenario (other than perhaps some version of column generation/branch-price-cut).

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SaqibIlyas

OK, my problem belongs to the latter class of problems. Let me try to describe it in terms of all the decision variables. I'd appreciate if you could suggest what would be the best way to improve the problem formulation to make it amenable to efficient optimal solution.
We have l items, m locations and n intervals. Each item must be assigned to one location at every interval. An item may be assigned to different locations at different intervals. The objective is to minimize the cumulative cost over all intervals and all locations at a given interval. The cost has the following factors:
1- Some idling cost. Cost that would be incurred if a location is "on" even if it is not handling any item.
2- Some utilization cost. Cost that is linearly depended on the workload of the items.
3- Some turn on and turn off costs. If a location was off at interval i-1 and it is on at interval i, we will incur some cost to turn it on. A turn off cost is also incurred vice versa.

So, I have the following decision variables:

1- x_i_j_k which is 1 if item i is mapped to location j at interval k, 0 otherwise.
2- p_j_k which is 1 if location j is on at interval k, 0 otherwise.
3- b_j_k which is 1 if location j is turned on at interval k, 0 otherwise.
4- s_j_k which is 1 if location k is turned off at interval k, 0 otherwise.

Some given parameters:

1- r_j_k: the unit cost at location j at interval k
2- w_i_k: the amount of workload presented by item i at interval k
3- c_j: the workload capacity of location j

So, the total cost is:

sum_i ( sum_j (sum_k (x_i_j_k * w_i_k * r_j_k))) + sum_j(c_j*sum_k (p_j_k * r_j_k)) + sum_k(sum_j(c_j*b_j_k*r_j_k)) + sum_k(sum_j(c_j*s_j_k*r_j_k))

where the first term indicates cost of handling workload, the second term indicate the idling cost, the third one is the cost due to turning location on and the last term is the overhead due to turning a location off.
The constraints are:

x_i_j_k, p_j_k, b_j_k, s_j_k are binary
sum_i(x_i_j_k*w_i_k) <= c_j for all j, for all k
sum_j(x_i_j_k) = 1, for all i, for all k
b_j_k >= p_j_k - p_j_(k-1)
s_j_k >= p_j_(k-1) - p_j_k
b_i_0 = p_i_0
s_i_0 = 0
p_j_k >= x_i_j_k

The second constraint is the location capacity constraint. The third one ensures that each item is completely handled at each interval. The fourth and fifth constraints ensure that a turn on/turn off is recorded if a location gets turned on/off at interval k, while it was off/on at interval k-1. We assume that each location is initially off, so a turn on cost is incurred if a location is on during the first (0th) interval. No turn off cost is needed if a location is off during the 0th interval, because all locations were off to begin with. Lastly, a location should be indicated on during an interval if at least one item is mapped to it during that interval.
Do you see a room for improvement in this model? Pointers would be helpful.
Thanks and best regards
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> SaqibIlyas wrote:
> Do you see a room for improvement in this model? Pointers would be helpful.

I'm not sure I can be of much help, but we'll see. My usual disclaimer here: MIP models, like government officials, do not necessarily behave in a logical or rational manner. So any advice about modeling approaches comes with an implicit "might make it better, might make it worse" qualifier.

The first thing that strikes me is that you charge the same amount (capacity*current production cost) at each location for three things: operating the location; turning the location on; and turning the location off. You also charge the actual product production costs (same cost per unit of work, but multiplied by actual work done rather than capacity). The fact that all the costs are the same looks goofy to me. I don't know if that's intentional or if you were just simplifying the model for me, but it's intentional, then you don't need the s variables. Just use b to indicate "change of state" (either direction), set p_j_{-1} = 0 (forcing a change in any location that is on in time period 0), and substitute b for s. You only need to have both b and s if the switch-on and switch-off costs are different.

I don't see a way to break x into a bunch of doubly-subscripted binaries. (That's not to say it can't be done, just that I don't see a way.) Benders decomposition might be one way to make the model more tractable. I'd be inclined to put the p, b and s variables (if s is needed) in the master problem, along with the switch-on, switch-off constraints that tie them together. Operating and switching costs would appear directly in the master problem objective function. The master problem would also contain one continuous variable (call it z_k) for each period, added to the objective, that would capture the direct production costs (the first sum in your objective function).

There would be one subproblem for each period, which would contain the item-location assignments for that period, with the item production costs as the objective. Subproblems would generate either feasibility cuts (the current solution does not allow all items to be assigned in period k, so the p variables have to change to conform to some new cut) or optimality cuts (z_k is currently underestimated in the master and has to be at least some linear inequality involving the p variables).

Another possibility is to treat it somewhat like a cutting stock or crew scheduling problem. Generate assignment patterns, each being a column of 0s and 1s indicating to which location each job is assigned. Patterns have to be feasible, in the sense that they don't violate capacity limits, and every job gets assigned to a location. Now the master problem is to pick the pattern to use in each period, accounting for all costs. What would essentially be the Gilmore-Gomory heuristic (for 1-D cutting stock problems) would solve the LP relaxation, use dual values to guide a subproblem that generates new patterns (which I think would be a variant of a bin-packing problem), iterate ad nauseum and then, when no new columns were found, "unrelax" and solve the master as an IP. This is a heuristic -- it's not guaranteed to find an optimum. Turn it into a branch-price-and-cut approach (which requires additional software; CPLEX does not do BPC) and you get an optimal solution.

Again, I offer no guarantee that either of those approaches is better than solving it as a single MIP.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization