As a highly simplified example consider the solution:
---- 32 VARIABLE x.L patterns i1 i2 i3 i4 i5 i6 i7 i8 t1 1 4 3 2 1 1 2 4 t2 3 5 3 5 4 1 3 t3 1 1 3 2 2 2 1 1 t4 3 4 1 3 4 2 1 3 t5 1 4 1 1 3 4 3 2 t6 2 1 2 2 1 3 3 t7 4 1 3 4 3 1 1
We see we have a different pattern for each time period \(t\). The question is: can we reduce the number of different patterns? Say, we want to allow just 4 different patterns.
Quadratic formulation
One way to model this is to have a pool of candidate patterns \(y_{c,i}\) with 4 candidates \(c\). Then use a standard assignment-like construct to pick from those candidates;\[\begin{align}&x_{t,i} = \sum_c \mathit{select}_{t,c}\cdot y_{c,i}\\& \sum_c \mathit{select}_{t,c}=1&&\forall t\\ & \mathit{select}_{t,c} \in \{0,1\}\end{align}\] Unfortunately this is non-linear as both \(\mathit{select}_{t,c}\) and \(y_{c,i}\) are decision variables. We can solve this with a number of solvers such as global MINLP solvers (Baron, Couenne, Antigone), or global MIQCP solvers (Gurobi). The solution can look like:
---- 49 VARIABLE y.L candidate patterns i1 i2 i3 i4 i5 i6 i7 i8 cand1 3 4 1 3 4 2 1 3 cand2 1 4 2 1 2 1 3 3 cand3 3 5 3 5 4 1 3 cand4 1 1 3 3 3 2 1 1 ---- 49 VARIABLE select.L select from candidates cand1 cand2 cand3 cand4 t1 1 t2 1 t3 1 t4 1 t5 1 t6 1 t7 1 ---- 49 VARIABLE x.L patterns i1 i2 i3 i4 i5 i6 i7 i8 t1 1 4 2 1 2 1 3 3 t2 3 5 3 5 4 1 3 t3 1 1 3 3 3 2 1 1 t4 3 4 1 3 4 2 1 3 t5 1 4 2 1 2 1 3 3 t6 1 4 2 1 2 1 3 3 t7 1 1 3 3 3 2 1 1
Indeed we see that the \(x\) variables show four different patterns.
Note again that all these quantities (\(x\), \(y\), and \(\mathit{select}\)) are endogenous (i.e. determined by the solver).
Linearization
We can linearize this approach. First, we assume the variables \(x\) and \(y\) are bounded: \[x_{t,i}, y_{c,i} \in [0,U]\] We define \[sy_{t,c,i} = \mathit{select}_{t,c}\cdot y_{c,i}\] With this we can formulate the linearization: \[\begin{align}& sy_{t,c,i} \le \mathit{select}_{t,c} \cdot U \\ & sy_{t,c,i} \le y_{c,i} \\ & sy_{t,c,i} \ge y_{c,i} - U(1-\mathit{select}_{t,c}) \\ &x_{t,i} = \sum_c sy_{t,c,i} \\ & sy_{t,c,i} \in [0,U]\end{align}\]
The results look like:
---- 62 VARIABLE y.L candidate patterns i1 i2 i3 i4 i5 i6 i7 i8 cand1 1 4 2 1 2 1 3 3 cand2 1 1 3 3 3 2 1 1 cand3 3 5 3 5 4 1 3 cand4 3 4 1 3 4 2 1 3 ---- 62 VARIABLE select.L select from candidates cand1 cand2 cand3 cand4 t1 1 t2 1 t3 1 t4 1 t5 1 t6 1 t7 1 ---- 62 VARIABLE sy.L sy=select*y i1 i2 i3 i4 i5 i6 i7 i8 t1.cand1 1 4 2 1 2 1 3 3 t2.cand3 3 5 3 5 4 1 3 t3.cand2 1 1 3 3 3 2 1 1 t4.cand4 3 4 1 3 4 2 1 3 t5.cand1 1 4 2 1 2 1 3 3 t6.cand1 1 4 2 1 2 1 3 3 t7.cand2 1 1 3 3 3 2 1 1 ---- 62 VARIABLE x.L patterns i1 i2 i3 i4 i5 i6 i7 i8 t1 1 4 2 1 2 1 3 3 t2 3 5 3 5 4 1 3 t3 1 1 3 3 3 2 1 1 t4 3 4 1 3 4 2 1 3 t5 1 4 2 1 2 1 3 3 t6 1 4 2 1 2 1 3 3 t7 1 1 3 3 3 2 1 1
This linearized formulation yields the same solution as the quadratic formulation shown earlier.
Notes:
- The all-zero records in the \(sy\) variable are not printed.
- For large problems with many candidate solutions, it may be advantageous to reduce symmetry in \(y\). One simple way would be to order solutions by their first index: \[ y_{c+1,'i1'} \ge y_{c,'i1'}\]
- In my application, \(x\) has more dimensions. This does not really affect the approach.
Making the number of different patterns variable
Until now, we assumed that the maximum number of different patterns is fixed. In the above case, this was 4. What if we want to make it variable, so we can add it to the objective (with a certain weight) in order to minimize it? Well, we can use the \(\mathit{select}\) variable for that. We can write: \[\begin{align} & \mathit{patternUsed}_c \ge \mathit{select}_{t,c}&& \forall t,c\\ & \mathit{numPatternsUsed} = \sum_c \mathit{patternUsed}_c\end{align}\] Now, we can minimize \(\mathit{numPatternsUsed}\). Of course, we should make sure the set \(c\) is large enough (we can make it identical to the set \(t\)). To reduce symmetry, we can impose something like: \[ \mathit{patternUsed}_c \le \mathit{patternUsed}_{c+1}\] This will keep used patterns at the beginning.
With this objective, we will try to find schedules with fewer unique patterns, when this is not too costly in terms of the other objectives.
Conclusion
This is a MIP formulation to keep track of the number of different, unique patterns. We can use it to simplify schedules and plans where it is beneficial to reduce the number of unique patterns. In my case, this was about creating simpler, less complex schedules that are easier to implement and communicate. The formulation is interesting, and not immediately obvious.
Would you have an idea on how to write the linearization in GNU MathProg coding please? More specifically, how do you define the bound (U)? Is this the maximum of 4 different patterns?
ReplyDeleteThese are problem dependent.
DeleteIn the problem in your post, what would it be? I have more or less the same problem setting.
DeleteI hope you realize this is not a very good question. If I say, for my model (and my data), U=5, how would that help you?
DeleteApologies, I meant more the coding of your problem in GNU MathProg.
DeleteAlso, in my model I would need a limit of 4 patterns. Would the U then also be 5? Or to what data would this be linked?
If you don't have a good bound on the solution values x, then other formulations are possible. SOS1 variables or indicator constraints are supported by many MIP solvers. Not sure if they are supported by your tools.
Delete"Also, in my model I would need a limit of 4 patterns. Would the U then also be 5?" No, no. You totally misunderstand this post. I suggest discussing this with your teacher.
DeleteU is an upperbound on the values of x (and thus of y).
Delete