Monday, June 1, 2020

Simplify solutions

In the context of a real-world application, the client is interested to know about "simpler solutions". This makes the implementation of the solution an easier task. This sounds like a reasonable question. The modeling implications are not that trivial, however.

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.

No comments:

Post a Comment