Methods for off-line/on-line optimization under uncertainty

1 Introduction

Dealing with uncertainty in optimization problems is challenging, but also increasingly recognized as necessary to obtain practically relevant results [Powell, 2016]. In many cases, this class of problems features both an off-line "strategic" phase that can be tackled with relative leisure, and an on-line "operational" phase where decisions need to be taken under stringent time constraints. Since optimization under uncertainty is tough, anticipatory methods such as stochastic optimization (see [Shapiro and Philpott, 2007; Birge and Louveaux, 1997; Kall and Wallace, 1994]) have been historically employed for the off-line phase, and simple non-anticipativity heuristics for the on-line phase.

However, on-line algorithms have the ability to exploit additional information as the uncertainty is slowly revealed. With the aim of tapping into this potential, a growing number of works has been addressing on-line problems via techniques originally introduced for stochastic programming, e.g. sampling and the Sample Average Approximation [Shapiro, 2013]. Sampling refers to obtaining realizations (scenarios) of the random variables used to model the uncertainty;

by solving deterministic optimization problems over multiple scenarios and by computing averages, it is possible to enrich an on-line algorithm with some degree of anticipation. These developments lead to the EXPECTATION [Chang et al., 2000], CONSENSUS [Bent and Van Hentenryck, 2004b] and REGRET [Bent and Van Hentenryck, 2004a] algorithms, and to more advanced methods such as AMSAA [Hentenryck and Bent, 2009; Mercier and Van Hentenryck, 2008]. All such methods are well discussed in [Hentenryck and Bent, 2009].

Intuitively, by integrating off-line and on-line decision making, it should be possible to obtain even better results, as it is often the case when a complex problem is partitioned. This paper aims at introducing two such methods that are applicable when: 1) the uncertainty is exogenous; 2) there exists a heuristic for the on-line phase with certain properties. In practice, each method alters either the off-line or the on-line component of the solution process, so that the two play better together. We believe our techniques represent a significant step toward integrated off-line/on-line optimization.

We instantiate our approaches on two case studies: 1) an energy system management problem, where load shifts are planned off-line and power flows must be controlled on-line; and 2) a Vehicle Routing Problem where customers are assigned off-line, but the routes can be chosen on-line. We show how the two methods strike radically different trade-offs in terms of off-line and on-line complexity, but they achieve solutions of similar (high) quality.

2 Formalization

We consider multi-stage optimization problems under uncertainty, where the first stage (indexed with 0) involves off-line decisions, and all subsequent n stages involve on-line decisions. We will start by describing a baseline solution approach, and then improve it by: 1) adding anticipation to the on-line solver through a systematic procedure; and 2) making the off-line solver aware of the on-line heuristic, and capable of controlling its parameters so as to steer its behavior. Generally, a simple heuristic may always choose the action with minimum "cost", i.e. the parameters may be either the costs themselves or constants used for score computation. The first method is closely related to existing on-line anticipatory algorithms; the second relies on the mixed nature of the problem.

Formally, let y represent the off-line decisions; let xk represent the on-line decisions for stage k; let sk (resp. ξ k ) represent the system state (resp. the uncertainty) revealed at the beginning (resp. the end) of stage k. All variables are assumed to be vectors, they can be either continuous or discrete, and have either finite or infinite domain.

Baseline on-line heuristic: We assume the availability of an on-line heuristic that can be modeled as a parametric convex (and therefore efficient) optimization problem:

where f is the cost function with parameter vector αk , while e and g are the constraint functions (with vector output). We assume the optimization problem to be convex, which means that f and g must be convex and e to be linear. Typically, the convexity requirement will prevent xk from being integer, but there are important exceptions (e.g. the one in Section 3.2).

We will assume that F(y, xk , sk ) is the actual cost incurred at stage k for taking decisions xk , which may not be the same as the objective function f of the heuristic. The transition from the state in stage k to the state in stage k + 1 is defined by means of a transition function T , i.e.:

where it can be seen that the effect of the uncertainty (i.e. the random variable) is encoded in the state.

Flattened Problem: Let Ω be a set of scenarios ω from the sample space of ξ = (ξ 0 , . . . ξn-1 ). Given a single scenario ω, it is possible to collapse the instantiations of PH for each stage to obtain a flattened (on-line) problem:

where xkω /skω /ξ kω are the on-line decisions/state/realizations for stage k in scenario ω. The only actual adjustment w.r.t. instantiating PHmultiple times is that the true cost F is used rather than the heuristic cost function. Since PF assumes the availability of all ξ kω values, it is effectively a clairvoyant approach, due to the lack of non-anticipativity constraints. In the on-line optimization literature the flattened problem is known as the off-line problem (see [Hentenryck and Bent, 2009]), but we adopt a different name to avoid ambiguity with the actual off-line phase.

Since the on-line problem can be solved with relative ease, the complexity depends heavily on the properties of the state transition function. If T is linear (e.g. in section 3.1), then the flattened problem will be convex and relatively easy to solve. Non-linear transition functions (e.g. section 3.2) are conversely much harder to handle.

Baseline off-line problem: As a baseline to deal with the offline decisions we consider a two-stage stochastic optimization problem obtained by instantiating PF once per scenario:

where the function fo(y) represents the cost that depends directly on the off-line decisions. The remainder of the cost function is given by the Sample Average Approximation of the expected cost of the subsequent stages. The function To(y, ξ 0ω ) determines the initial state for the on-line stages, based on the value of y and on the uncertainty revealed at the end of the off-line stage (i.e. ξ 0ω ). Finally, Y is the feasible space for the off-line decision variables y. We make no special assumption on Y, fo(y), and To(y, ξ 0ω ), meaning that even when the flattened problem is convex the off-line problem may be NP-hard (or worse). Still, the fact that the problem is solved off-line makes its complexity less critical.

The biggest drawback of this approach is that using the flattened problem to estimate the effect of the off-line decision on the future stages is equivalent to assuming the availability of an oracle. In practice, however, an on-line approach can behave much worse than an oracle-powered solver.

Anticipatory On-line Phase: In this context, off-line on-line integration can be obtained by providing the on-line algorithmwith something that resembles an oracle, i.e. by making it anticipatory. A simple approach to achieve this is the one employed for the baseline off-line problem, i.e. instantiating PF for the remaining stages. Formally, let h be the index of the current stage, then we consider:

The off-line decisions are taken using PO. This first approach, nicknamed Boosted On-line OptimizatioN (BOON), improves the accuracy of the on-line component at the expense of its solution time.

PB has the same semantic as the EXPECTATION algorithm, which obtains the same results by enumerating the feasible decisions for the current stage, and evaluating their expected cost by solving the flattened problem on each scenario individually. Since each scenario is considered in isolation, EXPECTATION is arguably much more efficient than BOON whenever the current stage decisions can be enumerated reasonably fast. The same argument applies to the REGRET algorithm, an efficient approximation of EXPECTATION.

However, when the decision space is not enumerable (e.g. for continuous xk variables, as in section 3.1), EXPECTATION, REGRET (and even CONSENSUS and AMSAA) cannot be applied directly, while our method is still viable. Moreover, when each on-line stage requires to take multiple decisions, enumeration may be expensive and associating an expected cost to each decision in isolation leads to underestimations if the costs are not additive (e.g. as done in [Awasthi and Sandholm, 2009]).

On-line Aware Off-line Phase: An alternative integration approach consists in making the off-line solver aware of the on-line heuristic. Moreover, we can allow the off-line phase to adjust the heuristic parameters so as to steer its behavior.

We start by observing that, since the on-line heuristic problem PH is convex, any local minimum must be a global minimum. Local minima can be characterized in terms of the Karush-Kuhn-Tucker optimality conditions [Winston, 2004], which for PH in a given scenario ω are given by:

where, for sake of readability, f(y, xkω , skω ; αk) has been shortened to f, the i-th component (out of |e|) of e(y, xkω , skω ) to ei, and the i-th component (out of |g|) of g(y, xkω , skω ) to gi. The λkω,i and µkω,i variables represent dual multipliers. Eq. (8) corresponds to the gradient cancellation condition, Eq. (9) to complementary slackness, Eq. (10) to dual feasibility (λkω,i is free), and Eq. (1), (2) to primal feasibility. Note that here we use the heuristic cost, parameterized in αk .

Now, the KKT conditions can be injected as constraints in PO. This will force all xkω variables in the off-line problem to take the values that would be actually assigned by the heuristic. This leads to the following problem:

The decision variables are in this case y, xkω , skω , λkω,i , µkω,i , and crucially αk . The on-line decisions are then taken using the original heuristics, but its behavior will be affected by the "parameter schedule" α1 , . . . αn produced by solving PM.

We nicknamed this second appraoch Master Off-line OptimizatioN (MOON): it achieves integration at the cost of offline solution time, because of the additional variables in PM and the presence of non-linearities in Eq. (9).

3 Case Studies

In this section we present our case studies. The first one (an energy management system) was considered in [De Filippo et al., 2017]: since it features continuous on-line decision variables, it is not amenable to existing approaches such as EXPECTATION or REGRET. The second use case (a Vehicle Routing Problem variant) is meant to provide a realistic, dramatically different, example of how the methods can be instantiated: it features discrete on-line decisions, and allows a quality comparison with classical algorithms because in such cases BOON leads to the same results as EXPECTATION (with no solution time restrictions). For simplicity, we will make use of monolithic models: our methods work with any solution approach, provided that the correct problems are solved.

3.1 EnergyManagement System

We consider a Virtual Power Plant management system (see [Morales et al., 2013]) with partially shiftable loads, renewable energy generators, storage systems, and grid-connection. The load shifts must be planned off-line and the energy balance should be maintained on-line. The goal is to decide the minimum-cost energy flows at each on-line stage (see [Clavier et al., 2015]), i.e.: 1) how much energy should be bought; 2) which generators should be used; 3) if the surplus energy (if any) should be either stored or sold to the market.

The uncertainty stems from uncontrollable deviations from the planned shifts and from the presence of Renewable Energy Sources (RES) (see [Palma-Behnke et al., 2011; Bai et al., 2015]). We assume that the RES production forecast is good enough that its error in each stage can be considered an independent random variable.

Baseline Heuristic and Transition Function: Based on the shifts produced by the off-line step, and adjusted to take into account the uncertainty, the on-line heuristic minimizes the operational cost and covers the energy demand by manipulating flows between nodes in g ∈ G. We assume the index 0 refers to the storage system and index 1 to the RES generators. The stages represent periods long enough to treat the corresponding flow decisions as independent. The heuristic can be formulated as an LP model:

where n is the number of on-line stages, and xkg represents the flow from g to the VPP (if positive) or in the reverse direction (if negative). All flows must respect the physical bounds xg and xg. The flow costs ckg correspond to the problem parameters αk in PH. The state variables are the RES energy flow xk1 , the load to be satisfied ˜Lk , and the battery charge γ k . The battery upper limit is Γ and η is the charging efficiency. The off-line decisions do not appear directly in the heuristic model, but they affect instead the state transition function:

where ˆRk and ˆLk are the estimated RES production and load, and ξ kR and ξ kL are the corresponding errors (random variables). We assume that the errors follow roughly a Normal distribution N(0, σ2 ), and that the variance σ2 is such that the 95% confidence interval corresponds to ±20% of the estimated value [Gamou et al., 2002]. The yk variable represents the (off-line planned) shift from the estimated load.

Baseline Off-line Problem: The off-line problem is modeled via Mixed Integer Programming (MILP) and it is given by:

yk ≤ yk ≤ yk ∀k = 1, . . . n (24) where Eq.(17) - (22) define the flattened problem, and Eq. (23) - (24) the feasible space for the off-line variables y. Eq. (23) ensures that the shifts respect a local balance. The initial battery charge γ 0ω is identical for all scenarios.

Instantiating BOON for the VPP: A model for the BOON approach can be obtained by applying in an almost straightforward fashion the definitions from Section 2:

Eq. (20) - (22) ∀k ≥ h, with shω = sh and xhω = xh

Note that P1.3, although potentially large, is a Linear Program and can be solved in polynomial time.

Instantiating MOON for the VPP: We start by formulating the KKT conditions for the on-line heuristic in a single scenario, thus obtaining:

where µkg,ω and ν k g,ω are the multipliers associated to the physical flow bounds, while ˆµkω and ˆ ν kω are associated to the battery capacity bounds. The multiplier λkω is associated to the balancing constraint, i.e. Eq. (11), and can be eliminated with a few algebraic transformations. Injecting the conditions in the off-line model yields:

where the decision variables are yk , xkg,ω , µkg,ω , ν k g,ω , ˆµkω , ˆ ν kω . To those, we add the cost ck0 associated to the flow between the VPP and the storage system (the only parameter that we allow the solver to adjust). Normally, there are neither economic penalties nor incentives for such flow, while there is a profit associated to flows from the VPP to the grid. As a side effect, the naive P1.1 heuristic will always choose to sell the surplus energy. MOON allows the off-line solver to associate a "virtual profit" to storing energy, which enables addressing the original limitation at no on-line computational cost.

3.2 Vehicle Routing Problem

We consider a variant of the Capacitated VRP with uncertain travel times (see [Toth and Vigo, 2002; Bertsimas and Simchi-Levi, 1996; Lee et al., 2012; Tas¸ et al., 2013]). The problem consists in establishing the paths of a set of vehicles to serve a set of customers. All vehicles have a finite capacity, and customers have a known demand and can be visited by a single vehicle. There are n fully connected customers/nodes, with node 0 being the (single) depot.

Customer assignments must be done off-line, while the vehicle routes are chosen on-line. We assume that, whenever a node is reached, its binary "state" becomes known, and with that the (uniform) distributions followed by the travel times of all its outgoing arcs. Formally, this results in bimodally distributed, statistically dependent, travel times. The objective is to minimize the total travel time.

Baseline Heuristic and Transition Function: The on-line heuristic consists in simply picking the outgoing arc with the shortest travel time. This can be modeled also as a simple Integer Program. Let h be the current node, then we have:

where xhj = 1 iff we choose to move from h to j, Vh is the set of nodes that still needs to be visited (and it always include the depot), and the travel times chj are the heuristic parameters. P2.1 does not apparently satisfy our assumptions, due to the integer variables. However, its LP relaxation has always an integer solution, banning degenerate cases (i.e. arcs with the same cost). We can therefore relax the integrality requirement without loss of generality. The transition function is given by:

where h∗ is the index of the next node selected by the heuristic and ξh∗ ,j is the travel time from h∗ to j (a random variable). Note also that in this case the index of the on-line stage is implicitly given by h. We take advantage of this and reduce the notation clutter by moving the ω index to apex position.

Baseline Off-line Problem: We tackle the off-line problem via Mixed Integer Linear Programming, which forbids us to directly embed the non-linear Eq. (34) in the model. In practice, however, the equation states that 1) each vehicle should serve only its assigned customers, and 2) the visit should form a single loop. Both are well known VRP constraints and can be linearized. In particular, we use the model:

where all constraints where an ω apex appears should be posted ∀ω ∈ Ω. All x and y variables are binary, and yki = 1 iff customer i should be visited by vehicle k. We have M = |V |, and V + = V \ {0}. Eq.(36) - (40) define the flattened problem, and Eq. (41) - (42) define the feasible space of the off-line decision variables. For sake of simplicity, we eliminate subloops by keeping track of the visiting order tωki of each node for each vehicle: this is a simple, but not particularly effective method, because it relies on big-Ms and reduces the quality of the LP bound [Miller et al., 1960].

Instantiating BOON for the VRP: The BOON method can be instantiated for each vehicle k separately, by first restricting the focus to the set of nodes Vh, and then by applying the definition from Section 2 and linearizing Eq. (34) in the baseline off-line problem, we get:

where Eq. (44) means that the vehicle path should start from the current node h (and end as usual in the depot).

Instantiating MOON on the VRP: As usual, the first step in the MOON is formulating the KKT conditions for P2.1. In this case after some algebraic transformations, for a given vehicle k, node h, and scenario ω we obtain:

where λωk,h is the multiplier for Eq. (32), and all other multipliers have been eliminated. The main difficulty is again dealing with the set Vh, which is part of the state and should be constructed dynamically in the off-line problem. Here, we handle Vh by introducing fresh variables rω kji such that rω kji = 1 iff node i has been visited when node j is reached. The semantic is enforced via additional non-linear constraints in the off-line model. The latter is given by:

The decision variables are yki, xωkij , λωki , rω kji , plus the "virtual travel times" cij, i.e. the parameters for the on-line heuristic. The constraints on the rω kji variables enforce the transitive property on the set of visited nodes. Bounding the virtual travel times is necessary to prevent the solver from building degenerate parameterizations for P2.1 on purpose, which would trivially satisfy all KKT constraints and make the approach boil down to the baseline off-line solver.

4 Experiments

We performed an experimentation to compare the solution quality and run times of our methods. As references for comparison we use the baseline approaches, plus an optimal solver operating under perfect information. Additionally, on the VRP, BOON obtains the same solution quality as EXPECTATION, which gives a third term of comparison.

Experimental Setup: Our methods are evaluated over different uncertainty realizations, obtained by sampling the random variables for the loads and RES generation in the VPP model, and for the travel times in the VRP model. We consider a sample of 100 realizations for each of the six different instances of each problem. We then run each approach on each relization and measure the cost and run time. The scenarios in our models, conversely, are not sampled, but programmatically chosen: for the VPP we consider four "extreme" scenarios where (resp.) the load and the RES generation are at low/high values. For the VRP, each scenario corresponds to the mean travel times in one mode of the distribution. The VPP has 24 on-line stages, while in the VRP the number depends on how many customers are assigned to each vehicle.

We solve our LPs and MILPs using Gurobi, while for the non-linear problems we use BARON via the GAMS modeling system on the Neos server for optimization. The time limit is 100 seconds for the VPP, and 500 seconds for the VRP. For the VPP, we use data from two public datasets to define problem instances for a residential [Espinosa and Ochoa, 2015] and industrial plant 1 . For the VRP we use modified versions of classical instances 2 , by including problems from 10 to 30 customers with one depot and different numbers of vehicles.

Discussion: In Table 1 and Table 2 we show the average costs and run time over the 100 input realizations for each approach for the VPP use case. On-line times refer to the sum of the stages. The baseline model (being an LP) appears to be rather efficient in terms of computation time, but yields solutions of limited quality. The BOON method comes much closer to the oracle solver, at the cost of a higher, but still reasonable, on-line run time. The MOON method incurs substantially larger off-line solution times, but it manages to either beat or match the BOON solution quality by making use of the original, straightforward, on-line heuristic.

Table 3 and 4 report the same results for the VRP. Here the on-line times are summed over all the vehicles. The original on-line heuristic is very efficient, but coupled with the baseline off-line model it does not come close to the oracle quality. The off-line model (a Mixed Integer Linear Program) takes also considerably more time to be solved. BOON, which in this case yields the same results as EXPECTATION with no time limit, yields substantially better solutions, but, being also MILP-based, it takes non-negligible time during the on-line phase. The MOON results follow the same trend as the VPP: the solution quality either matches or beats that of BOON, at the cost of a higher off-line computation time, though the gap wrt the baseline is now much smaller.

5 Conclusion

This paper makes a first step toward generic integrated offline/on-line optimization. We propose two alternative approaches, based on the idea of making the off-line and on-line solvers operate synergistically. In the BOON method this is done by providing the on-line solver with the approximation of an oracle. In the MOON method, we instead make the offline solver aware of the limitations of the on-line one, and capable of controlling its behavior by adjusting parameters. In general, our approaches work best for problems with numeric on-line decisions, but important classes of on-line heuristics are also covered (e.g. argmin of parametric scores).

1 https://data.lab.fiware.org/dataset/

2 http://myweb.uiowa.edu/bthoa/TSPTWBenchmarkDataSets.htm

Both techniques yield substantially improved solutions: BOON matches the quality level of EXPECTATION, but it is applicable under more general assumptions. Unfortunately, the method is also less efficient. MOON often manages to beat BOON (and therefore EXPECTATION) in terms of solution quality. While this comes at the price of a substantially increased off-line computation time, the method achieves these results by using naive and very efficient on-line heuristics.

We believe there is room for improving the efficiency of our methods (similarly to how EXPECTATION was improved in REGRET), and achieving this goal is part of our current research directions. We also plan to apply our approaches to different problems, such as resource allocation and scheduling with Simple Temporal Networks under Uncertainty.