(648g) The Curse of Dimensionality in Discrete-Time Scheduling – How to Maintain Computational Tractability When Considering Long Planning Horizons with Fine Discretizations? | AIChE

(648g) The Curse of Dimensionality in Discrete-Time Scheduling – How to Maintain Computational Tractability When Considering Long Planning Horizons with Fine Discretizations?


Schäfer, P. - Presenter, RWTH Aachen University
Mitsos, A., RWTH Aachen University
During the past decade, scheduling formulations have gained substantial attraction in the context of demand side management, as they allow to raise economic potentials through the exploitation of time-variable electricity prices [1]. In particular, numerous authors have proposed discrete-time scheduling formulations that use the same temporal discretization as the electricity market and assign optimal loads and modes of operation to the individual scheduling intervals [2-4]. Consequently, the dimensionality of the optimization problems, i.e. the number of variables and equations, scales linearly with the number of considered intervals and thus – for a fixed temporal discretization – with the length of the planning horizon. In case of linear process models that lead to mixed-integer linear programming (MILP) formulations for scheduling, this observation does commonly not appear problematic due to the efficiency of state-of-the-art MILP solvers.

Real processes are however often characterized by nonlinear relationships, particularly by nonlinear efficiency characteristics, which are crucial for scheduling subject to time-variable electricity prices. Such efficiency losses commonly lead to a net increase in the electricity consumption if varying the process loads, making flexible operating schemes profitable only in the presence of sufficient price spreads. To take these circumstances into account, piecewise linearization approaches have been proposed, which still give MILPs [5,6]. As an alternative, the use of sophisticated nonlinear surrogate models, whose application to chemical engineering problems is currently extensively studied in literature (e.g., [7,8]), in scheduling formulations appears highly promising. However, this leads to (mixed-integer) nonlinear programs ((MI)NLP) with potentially multiple local solutions. Consequently, even moderate horizon lengths in discrete-time scheduling problems with nonlinear models embedded result in problem sizes that are currently prohibitive for desired deterministic global solution approaches, so that the few existing works in this area confine to the consideration of short horizon lengths (e.g., [9]). Consequently, an important research perspective lies in the identification of low-dimensional yet accurate approximations of the full-dimensional scheduling problem.

Existing approaches addressing a reduction of the (temporal) dimensionality of scheduling problems can be classified into three categories: (a) time series aggregation, (b) tailored time grids, and (c) truncated time series transforms. Herein, we briefly introduce the underlying concepts of the different approaches and present the most recent progress in the respective research areas. A distinct focus will be set on restrictions on the applicability of the methods as well as on their computational efficiency.

In this contribution, we show that time series aggregation methods (e.g., [10-12]) enable user-defined reductions of the dimensionality of the optimization problems that translate into inherent savings in computational times. However, the consideration of time-coupling constraints is usually problematic and requires work-arounds [13,14] in order to prevent infeasible schedules. Consequently, we discuss the concept of tailored time grids as an alternative, which explicitly considers all scheduling intervals further on and thus allows for respecting all constraints, thereby furnishing feasible schedules. Here, we first introduce formulations using intervals of variable lengths [15,16], i.e. that assign similar degrees of freedom (DoFs) to multiple consecutive intervals. Afterwards, we present an extension of this approach by assigning similar DoFs to multiple nonconsecutive intervals that are characterized by comparable input conditions [17]. In this context, we also thoroughly discuss how reductions in the number of DoFs translate into savings in computational times if using reduced-space optimizations techniques (cf. [18]) that only expose the DoFs to the solver. Moreover, we also demonstrate the adaptation of a heuristic iterative refinement strategy from dynamic optimization (cf. [19]) to scheduling problems. Finally, we present our most recent research concerning a scheduling optimization directly in the space of a truncated transform of the time series of independent process input variables [20]. In particular, we show for the case of continuous variables how the use of truncated wavelet transforms also allows for quantitative measures of improvements in the objective function from adding specific optimization variables to the problem through the analysis of Lagrangian multipliers.


The authors gratefully acknowledge the financial support of the Kopernikus project SynErgie by the Federal Ministry of Education and Research (BMBF) and the project supervision by the project management organization Projektträger Jülich.


[1] Zhang Q, Grossmann IE. Enterprise-wide optimization for industrial demand side management: Fundamentals, advances, and perspectives. Chem Eng Res Des. 2016;116:114-131.

[2] Ierapetritou MG, Wu D, Vin J, Sweeney P, Chigirinsky M. Cost minimization in an energy-intensive plant using mathematical programming approaches. Indus Eng Chem Res. 2002;41(21):5262-5277.

[3] Karwan MH, Keblis MF. Operations planning with real time pricing of a primary input. Comput Oper Res. 2007;34(3):848-867.

[4] Mitra S, Grossmann IE, Pinto JM, Arora N. Optimal production planning under time-sensitive electricity prices for continuous power-intensive processes. Comput Chem Eng. 2012;38:171-184.

[5] Zhang Q, Grossmann IE, Heuberger CF, Sundaramoorthy, A, Pinto JM. Air separation with cryogenic energy storage: Optimal scheduling considering electric energy and reserve markets. AIChE J. 2016;61(5):1547-1558.

[6] Kelley MT, Pattison RC, Baldick R, Baldea M. An MILP framework for optimizing demand response operation of air separation units. Appl. Energy 2018;222,951-966.

[7] Cozad A, Sahinidis NV, Miller DC. Learning surrogate models for simulation‐based optimization. AIChE J. 2014;60(6):2211-2227.

[8] Schweidtmann AM, Mitsos A. Deterministic global optimization with artificial neural networks embedded. J Optim Theory Appl. 2019;180(3):925-948.

[9] Ghobeity A, Mitsos A. Optimal time-dependent operation of seawater reverse osmosis. Desalination. 2010;263:76-88.

[10] Nahmmacher P, Schmid E, Hirth L, Knopf B. Carpe diem: A novel approach to select representative days for long-term power system modeling. Energy. 2016;112:430-442.

[11] Poncelet K, Höschle H, Delarue E, Virag A, D'haeseleer W. Selecting representative days for capturing the implications of integrating intermittent renewables in generation expansion planning problems. IEEE Trans Pow Syst. 2017;32:1936-1948.

[12] Bahl B, Lützow J, Shu D, Hollermann DE, Lampe M, Hennen M, Bardow A. Rigorous synthesis of energy systems by decomposition via time-series aggregation. Comput Chem Eng. 2018;112:70-81.

[13] Baumgärtner N, Bahl B, Hennen M, Bardow A. RiSES3:Rigorous Synthesis of Energy Supply and Storage Systems via time-series relaxation and aggregation. Comput Chem Eng. 2019;127:127-139.

[14] Baumgärtner N, Shu D, Bahl B, Hennen M, Hollermann DE, Bardow A. DeLoop: Decomposition based Long-term operational optimization of energy systems with time-coupling constraints. Energy. 2020;198:117272.

[15] Pineda S, Morales JM. Chronological time-period clustering for optimal capacity expansion planning with storage. IEEE Trans Pow Syst. 2018;33:7162-7170.

[16] Palys MJ, Daoutidis P. Using hydrogen and ammonia for renewable energy storage: A geographically comprehensive techno-economic study. Comput Chem Eng. 2020;136:106785.

[17] Schäfer P, Schweidtmann AM, Lenz PHA, Markgraf HMC, Mitsos A. Wavelet-based grid-adaptation for nonlinear scheduling subject to time-variable electricity prices. Comput Chem Eng. 2020;132:106598.

[18] Mitsos A, Chachuat B, Barton P. McCormick-based relaxations of algorithms. SIAM J Optim. 2009;20:573-601.

[19] Schlegel M, Stockmann K, Binder T, Marquardt W. Dynamic optimization using adaptive control vector parameterization. Comput Chem Eng. 2005;29:1731-751.

[20] Schäfer P, Schweidtmann AM, Mitsos A. Nonlinear scheduling with time-variable electricity prices using sensitivity-based truncations of wavelet transforms. Under review.


This paper has an Extended Abstract file available; you must purchase the conference proceedings to access it.


Do you already own this?



AIChE Pro Members $150.00
AIChE Emeritus Members $105.00
AIChE Graduate Student Members Free
AIChE Undergraduate Student Members Free
AIChE Explorer Members $225.00
Non-Members $225.00