(373ah) Using LP Relaxation to Speed up Solution of Large-Scale Scheduling Problems

The solution of large-scale scheduling problems has been a challenge since introducing optimization-based approaches (Méndez et al., 2006) for the exact solution of these complex combinatorial problems. Typically, the main problem lies in the large number of possible combinations e.g. sequences and/or assignments that are modeled using binary variables. In continuous-time approaches, the main problem is often identified around the sequencing decisions, whereas discrete-time approaches may be limited by their number of time points, i.e. accuracy of the modeling of the time domain.

Inspired by the promising results of using the LP-relaxation as a basis for pre-determining part of the binary variable values for the full-space problems that were achieved in solving the unit-commitment problem from the power grid (Harjunkoski et al., 2021), in this paper we discuss the applicability of this type of strategy for scheduling problems. Particularly, we want to find out whether the LP-relaxation could be useful for the general precedence approach (Méndez and Cerdá, 2003). Here the main challenge is caused by the poor relaxation of the model due to the triple-big-M constraints.

We will look into the optimality and efficiency of trying to predetermine mainly sequencing variables values and study the effect of different big-M values, as well as, reformulating the sequencing constraints using convex hull formulations. The results indicate further challenges, which are discussed along possible next steps.

References

Harjunkoski I., Giuntoli M., Poland J., Schmitt S. (2021). Matheuristics for Speeding Up the Solution of the Unit Commitment Problem. Proceedings of 2021 IEEE PES Innovative Smart Grid Technologies Europe: Smart Grids: Toward a Carbon-Free Future, ISGT Europe 2021, doi: 10.1109/ISGTEurope52324.2021.9640029

Méndez, C.A., Cerdá, J. (2003). An MILP Continuous-Time Framework for Short-Term Scheduling of Multipurpose Batch Processes Under Different Operation Strategies. Optimization and Engineering 4, pp. 7–22, doi: 10.1023/A:1021856229236

Méndez C.A., Cerdá J., Grossmann I.E., Harjunkoski I., Fahl M. (2006). State-of-the-art review of optimization methods for short-term scheduling of batch processes. Computers and Chemical Engineering, 30 (6-7), pp. 913 - 946, doi: 10.1016/j.compchemeng.2006.02.008