(657e) Using LP-Based Heuristics for Solving Large-Scale Integer Problems

In many domains the need for more accurate optimization, e.g. shorter time scales in scheduling, often prohibits scaling up of problems. One way of speeding up the solution of larger problems is to decompose or split the problem into smaller problem instances through e.g. rolling horizon schemes or by using non-uniform time representations [1]. A more recent approach is related to machine learning, where having access to a large set of similar problems could help improving the MIP search strategy through neural branching or neural diving [2] or limiting the problem size [3]. Also, with proper ML-algorithms many variable values can be fixed a priori reducing the search space [4]. This presentation discusses approaches on how to reduce the search space for large-scale MILP problems.

In particular, here we will focus on a simple principle on analyzing an MILP problem based on its LP-relaxation. Instead of just applying some rounding heuristic, we will test some key constraints using the variable values from the LP-relaxation and based on the test results fix (or eliminate) these from the consecutive MILP problem instance. We will show that by following the simple principles the MIP solution can be made 2-5 times faster with less than an average of 1% loss of optimality.

The presented heuristic approach will be illustrated, among others, on a Unit Commitment (UC) problem [5][6], which schedules the use of electricity generators to match the electricity generation with the demand forecast, taking into account physical ramping constraints and reserve requirements in order to protect the electricity network from uncertainties e.g. owing to disturbances or deviations from the available forecasts. The UC problem by itself is already a well-studied problem and many decomposition schemes have been reported [6][8]. Due to the periodical solution of relative similar problem instances, it also offers a good opportunity for machine learning [9].

The proposed approach has the benefit that it does not require any datasets but adapts itself always to the actual problem at hand. Nevertheless, the performance shows very promising characteristics, and the principle can be applied to several types of planning problems, where a large number of binary variables are present and represent the most essential decisions in the optimization.

References

1. Velez, S., & Maravelias, C. T. (2015). Theoretical framework for formulating MIP scheduling models with multiple and non-uniform discrete-time grids. Computers and Chemical Engineering, 72, 233-254. doi:10.1016/j.compchemeng.2014.03.003
2. Nair et al: “Solving Mixed Integer Programs Using Neural Networks.” arXiv:2012.13349 [math.OC], December 2020
3. Ikonen, T. J., Heljanko, K., & Harjunkoski, I. (2020). Reinforcement learning of adaptive online rescheduling timing and computing time allocation. Computers and Chemical Engineering, 141 doi:10.1016/j.compchemeng.2020.106994
4. Harjunkoski, I., Ikonen, T., Mostafaei, H., Deneke, T., & Heljanko, K. (2020). Synergistic and intelligent process optimization: First results and open challenges. Industrial and Engineering Chemistry Research, 59(38), 16684-16694. doi:10.1021/acs.iecr.0c02032
5. Shahidehpour, H. Yamin, and Z. Li., “Market operations in electric power systems: forecasting, scheduling, and risk management”. John Wiley & Sons, 2003.
6. Harjunkoski, M. Giuntoli, J. Poland and S. Schmitt: Matheuristics for Speeding Up the Solution of the Unit Commitment Problem. Accepted to IEEE PES ISGT EUROPE 2021, Oct 18-21st, 2021
7. Niknam, A. Khodaei, and F. Fallahi, “A new decomposition approach for the thermal unit commitment problem,” Appl. Energy, vol. 86, no. 9, pp. 1667–1674, 2009, doi: 10.1016/j.apenergy.2009.01.022.
8. Fu, M. Shahidehpour, and Z. Li, “Long-term security-constrained unit commitment: Hybrid Dantzig-Wolfe decomposition and subgradient approach,” IEEE Trans. Power Syst., vol. 20, no. 4, pp. 2093–2106, 2005, doi: 10.1109/TPWRS.2005.857286
9. Alinson S. Xavier, Feng Qiu, “Shabbir Ahmed: Learning to Solve Large-Scale Security-Constrained Unit Commitment Problems.” arXiv:1902.01697 [math.OC], December 2019