Harnessing Inferior Solutions For Superior Outcomes: Obtaining Robust Solutions From Quantum Algorithms
Pascal Halffmann Steve Lenk Michael Trebing














All authors contributed equally to this research.
pascal.halffmann@itwm.fraunhofer.de
0000-0002-3462-4941

[1]
michael.trebingn@itwm.fraunhofer.de

  Department of Financial Mathematics, Fraunhofer Institute for Industrial Mathematics ITWM
  Fraunhofer Platz 1
  Kaiserslautern
  Germany
  67663




  Department of Cognitive Energy Systems, Fraunhofer IOSB
  Am Vogelherd 50
  Ilmenau
  Germany
steve.lenk@iosb-ast.fraunhofer.de















In the rapidly advancing domain of quantum optimization, the confluence of quantum algorithms such as Quantum Annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA) with robust optimization methodologies presents a cutting-edge frontier. Although it seems natural to apply quantum algorithms when facing uncertainty, this has barely been approached. 

In this paper we adapt the aforementioned quantum optimization techniques to tackle robust optimization problems. By leveraging the inherent stochasticity of quantum annealing and adjusting the parameters and evaluation functions within QAOA, we present two innovative methods for obtaining robust optimal solutions. These heuristics are applied on two use cases within the energy sector: the unit commitment problem, which is central to the scheduling of power plant operations, and the optimization of charging electric vehicles (EVs) including electricity from photovoltaic (PV) to minimize costs. These examples highlight not only the potential of quantum optimization methods to enhance decision-making in energy management but also the practical relevance of the young field of quantum computing in general. Through careful adaptation of quantum algorithms, we lay the foundation for exploring ways to achieve more reliable and efficient solutions in complex optimization scenarios that occur in the real-world.







<ccs2012>
<concept>
<concept_id>10002950.10003624.10003625.10003630</concept_id>
<concept_desc>Mathematics of computing Combinatorial optimization</concept_desc>
<concept_significance>500</concept_significance>
</concept>
<concept>
<concept_id>10002950.10003705.10003707</concept_id>
<concept_desc>Mathematics of computing Solvers</concept_desc>
<concept_significance>500</concept_significance>
</concept>
<concept>
<concept_id>10002944.10011122.10002947</concept_id>
<concept_desc>General and reference General conference proceedings</concept_desc>
<concept_significance>500</concept_significance>
</concept>
<concept>
<concept_id>10010520.10010521.10010542.10010550</concept_id>
<concept_desc>Computer systems organization Quantum computing</concept_desc>
<concept_significance>500</concept_significance>
</concept>
</ccs2012>


[500]Mathematics of computing Combinatorial optimization
[500]Mathematics of computing Solvers
[500]General and reference General conference proceedings
[500]Computer systems organization Quantum computing






8 April 2024






Harnessing Inferior Solutions For Superior Outcomes: Obtaining Robust Solutions From Quantum Algorithms
    Steve Lenk
    April 29, 2024
=======================================================================================================





§ INTRODUCTION

Robust optimization problems <cit.> are crucial in practical applications due to their ability to account for uncertain parameters inherent in real-world systems, making them indispensable for ensuring reliable and resilient decision-making. However, their complexity and the necessity to find a solution that copes well under multiple, often conflicting, uncertainty scenarios make these problems challenging to solve with conventional optimization techniques.

Quantum computing is heralded for its substantial computational power, which may be able to tackle computationally demanding problems more efficiently than classical computing, particularly in handling stochasticity and navigating complex search spaces. Its inherent characteristics are well-suited to exploring vast solution landscapes and managing the randomness central to robust optimization challenges. So far, only one approach has been postulated that tackles robust optimization with quantum computing. Lim2023 present a quantum version of a well-known classical robust optimization algorithm characterized as online oracle-based meta-algorithm. This algorithm uses an oracle for the deterministic optimization problem in every iteration and the uncertain parameters are updating using online subgradient descent.

In this paper, we present two methods for finding robust optimal solution given an optimization problem with uncertain parameters. The first method simply utilizes the fact that instead of providing one solution, a quantum algorithm such as QA <cit.> is executed multiple times, where each execution returns one sample. As (near-)optimal solution are more likely to occur and robust optimal solutions often are often near-optimal, we harvest the returned set of samples for the best solution given a robustness measure. The second algorithm is an adaption of the first method using QAOA <cit.>. Here, after we have found optimal parameters for QAOA using the expected value of the uncertain parameters, we run the QAOA circuit for each scenario and select the most robust solution.

The paper is organized as follows. In the remainder of this section, we briefly introduce robust optimization and formally describe the two use cases we are considering, that is the unit commitment problem dealing with finding an optimal w.r.t. production schedule of power units subject to satisfying energy demand and energy production constraints and we investigate the problem of finding a cost-optimal charging schedule while utilizing energy coming from photovoltaic power. In Section <ref>, we introduce the quantum annealing approach and in Section <ref>, we present the adjustments made for QAOA. We show an example for both approaches. We close with an outlook on further research in the last section. 



 §.§ Overview on Robust Optimization

Robust optimization deals with optimizing decisions under uncertainty (e.g., uncertain data, model parameters) by finding solutions that are feasible under a range of possible scenarios and are rather immune to variations in the parameters of the optimization problem. In the context of robust optimization, there are two central robustness concepts:

Min-max worst-case robustness focuses on finding the solution that performs best in the worst-case scenario. This concept is formulated as min_x ∈ Xmax_ξ∈Ξ f(x, ξ), where x represents the decision variables within the feasible set X, ξ represents uncertain parameters within their uncertainty set Ξ, and f(x, ξ) represents the objective function that is to be minimized.

Min-max regret robustness aims to minimize the worst-case regret, which is the difference between the outcome of a decision and the best outcome that could have been achieved with perfect information. It is formulated as min_x ∈ Xmax_ξ∈Ξ( f(x, ξ) - f^*(ξ) ), where f^*(ξ) = min_x' ∈ X f(x', ξ) represents the best possible outcome for a given scenario ξ.
Remark that we have not specified the uncertainty set Ξ containing the different scenarios ξ. In general, this set can be a discrete set, an interval for a certain parameter of the optimization problem, or even a more complex set. For our use cases the demands, given for each time step, are identified as uncertain and we have a discrete set of demand scenarios that can occur. For those interested in delving deeper into robust optimization, we refer to BenTal2009RobustOptimization who provide a comprehensive overview and is an excellent starting points. Further, Gabrel2014RecentAdvancesInRobustOptimization review developments in robust optimization, including methodological advances and applications.



 §.§ Overview on the Use Cases



  §.§.§ The Unit Commitment Problem (UCP)

The UCP is tasked with finding a cost-minimal operation schedule for a set of thermal units i∈{1,…,N} to meet a given demand for electricity over a distinct set of time steps t∈{1,… T}. Further, technical properties of both the thermal units and the underlying power grid have to be respected. Take note that there does not exist one single UCP, but several variants are present in the literature. For an overview on different formulations, we refer to Knueven2020. In the remainder of this article, we use the model stated in <cit.>: Each thermal unit i has the following properties: linear, production dependent costs varcost_i and fixed costs startcost_i for starting the unit, minimum and maximum power generation output, mingen_i, maxgen_i, and minimum running time and minimum idle time, minup_i, mindown_i. At each time step t the residual demand rd_t, demand minus supply by renewable energies plus spinning reserve, has to be met. Limitations due to the power grid are omitted. Since quantum algorithms for optimization problems, such as QA, often require the optimization problem written as a Ising Hamiltonian, which has a close resemblance to a Quadratic Unconstrained Optimization Problem (QUBO), we state the QUBO formulation as presented in <cit.>:
[2]
	   ∑_t=1^T ∑_i=1^I (varcost_i·(mingen_i·on_t,i + (∑_k=1^d_i-1 2^k·gen_t,i,k + (d_i+1-2^d_i)·gen_t,i,d_i) .. 
       . ·step_i ). + startcost_i·start_t,i)
	   +A·∑_t=1^T(∑_i=1^I mingen_i·on_t,i + (∑_k=1^d_i-1 2^k·gen_t,i,k + (d_i+1-2^d_i)·gen_t,i,d_i).
       . ·step_i-rd_t)^2
       +A·∑_t=1^T((1-on_t,i)·∑_k=1^d_i gen_t,i,k)
	   +B·∑_t=1^T ∑_i=1^I (on_t,i·(1-on_t-1,i) + 2·start_t,i·(on_t-1,i+1-on_t,i)- start_t,i)
	   + C·∑_t=1^T ∑_i=1^I (start_t,i·minup_i -∑_τ=t^t-1+minup_istart_t,i·on_τ,i)
	   + D·∑_t=1^T ∑_i=1^I (∑_τ=t^t-1+mindown_i(start_t,i+on_t-1,i-on_t,i)·on_τ,i)
	on_t,i, start_t,i,gen_t,i,k∈𝔹,   ∀ t=1,…,T, i=1,…,I, k=1,…,d_i.

Here we have three sets of decision variables on_t,i, gen_t,i and start_t,i, t∈{1,… T}, i∈{1,…,N}. The binary variable on_t,i observes whether unit i is running at time t. The variables start_t,i∈ [0,1] track the starting of power units. Further, we have used a logarithmic encoding of the power generation output by using binary variables gen_t,i,k for each time step t, each power unit i. For a certain stepsize step_i for each power unit i we have k=1,…,d_i⌊log_2((maxgen_i-mingen_i)/step_i)⌋ + 1.


  §.§.§ Minimize costs of EV fleet charging under uncertainties in PV generation
 
Analogously to <cit.>, we describe the problem of minimizing the costs of EV fleet charging, where we want to minimize the grid usage, which costs money, and maximize the local and forecasted PV consumption, which earns less money per kW/h than grid usage costs.  However, since day-ahead forecasts for the solar radiation, which directly influence the solar power generation, are rather inaccurate, we include uncertainties through the standard deviation σ_t in mean solar power μ_t. The PV power generation E_t^pd includes implicitly the energy demand of the site. The maximal allowed charging power j_t is included to represent the number of EVs to be charged. Through some trivial assumptions we have set the maximal charging power per EV to 1. We restrict the charging power to be in the limits of j_t^min and j_t^max. Further, we want to charge overall at least E^min and not more than E^max. In summary, the optimization problem to minimize the cost for charging an EV fleet is equal to
[2]
	C(j_t)𝔼[∑_t (j_t - E_t^pd)^2]
	j_t^min≤j_t≤j_t^max,∀ t=1,…,T,
    E^min≤∑_t=1^T j_t≤E^max,
	j_t∈𝔹∀ t=1,…,T.

Here, the expectation value 𝔼[.] is taken over the stochastic variations of the problem instances, i.e. the PV system variations. By assuming a Gaussian distributed PV energy E_t^pd the expectation value can be calculated explicitly. Together by assuming a uniform distribution of the PV power between the limits E_t^pd,lo and E_t^pd,up, we can rewrite the problem as stated in <cit.> as follows:

    min_j ∑_t ( j_t^2 - C_t j_t + D_t)

with appropriately chosen coefficients C_t and D_t. From this form we can see, that stochastic variations in the presented forms do not imply an increased complexity in comparison to the deterministic approach above. However, in practice, a two-step approach is often used to consider uncertainties in optimization, in which the expectation value of the uncertainty is used in the first step and in the second the probability of the approach or respective scenarios are included. Including the probability distribution would require an analytical derivation of the target function, which is often not easily achievable. Thus, scenario approaches employing  Monte Carlo simulations to select respective scenarios are most often used. Classically, this approach is computational intense since it requires the solution of the optimization program for each scenario and a postprocessing step to find the stochastic solution.























































    


 §.§ Overview on Stochastic Optimization Measures

Besides the robustness concepts above, we utilize the following stochastic optimization measures. In particular, we use 

To calculate the quality measures for our stochastic optimization approach <cit.>, the expected value solution 

    EV=min_j_t^μ C(j_t^μ,μ_t)=min_j_t^μ∑_t (j_t^μ-μ_t)^2
 
needs to be computed. 
Since this is the first step of the two-step approach, no additional computation is necessary.
To verify the quality of the solution using the expected value of the PV generation, the expected value of using the expected value solution is used

    EEV=𝔼[C(j_t^μ,E_t,s^pd)]=∑_s 𝒫_s ∑_t (j_t^μ-E_t,s^pd)^2  .
 
The recourse problem, also known as here & now solution, represents the second step of the two-step approach and is equal to

    RP=min_j_t^RP∑_s 𝒫_s ∑_t (j_t^RP-E_t,s^pd)^2  .
 
The so-called value of stochastic solution represents the extra costs the expected value solution would cause

    VSS = EEV - RP  .

To verify the recourse problem, the wait & see solution, also known as solution of perfect information, has to be additionally calculated

    WS=𝔼[min_j_t,sC(j_t,s,E_t,s^pd)]=∑_s 𝒫_s min_j_t,s∑_t (j_t,s-E_t,s^pd)^2  .
 
The expected value of perfect information <cit.> determines the costs using the here & now solution compared to the wait & see solution

    EVPI = RP-WS  .

The two measures of goodness VSS and EVPI allow for the estimation of the usefulness of the expected value solution, i.e. , the first step and the recourse problem solution, i.e., the second step compared to the case of perfect information.


Check if redundant with Pascal's part...

For the verification of the robustness of the found solutions, strict robustness, also called absolute robust decision <cit.> and minimal maximum regret <cit.> or robust deviation decision <cit.> are used.
For our use case, strict robustness is calculated by

    SR = min_j_t^SRsup_s C(j_t^SR,E_t,s^pd)=min_j_t^SRmax_s ∑_t ( j_t^SR-E_t,s^pd)^2

and the minimal regret is given by

    MR    = min_j_t^MRsup_s ( ∑_t ( j_t^MR - E_t,s^pd)^2 - Opt(s) )  ,

where the optimal solution of a certain scenario s is given by

    Opt(s) = min_j_t^s∑_t (j_t^s-E_t,s^pd)^2  .






§ SOLUTION HARVESTING FOR QUANTUM ANNEALING

QA is a quantum algorithm for solving QUBO problems and seen as the quantum version of simulated annealing. So, given a QUBO, this is transformed in a so-called Hamiltonian H_P, an operator corresponding to the total energy of a quantum mechanical system. Finding the minimal solution to a QUBO is equivalent to having an Hamiltonian in its state of lowest energy, the ground state. The approach of QA is based on adiabatic evolution: starting from a simpler Hamiltonian H_I already in its ground state, we look at the time dependant system H(t)=t· H_P + (T-t)· H_I for t∈[0,T]. Now, if we move slowly through time, the system remains at the ground state and at time T, we obtain with high probability the ground state of H_P. Since this system is inherently stochastic and susceptible to outside influences, the experiment has to be rerun several times (so-called shots) to obtain a set of samples and increasing the probability of obtaining the optimal solution. 

Now, our approach is fairly straight forward: the sample set returned by QA does not only contain the optimal solution but also inferior solutions, in particular near-optimal solutions. Thus, instead of writing a robust optimization problem as a QUBO, which would require many qubits and may not be solvable with today's quantum hardware, we use the corresponding deterministic problem with the expected values of the uncertain parameters as input and search the stochastic output for the most robust solution given a robustness concept. Since robust optimal solutions are not far off of the optimal solutions for the individual scenarios, it is likely that the sample set of QA also contain a robust optimal or robust near-optimal solution. In total, we exploit the stochasticity of the output of QA for finding robust solutions. This is a two step approach: In the first step, we build the QUBO corresponding to the deterministic variant of the robust optimization problem, where we use the expected values of the uncertain parameters, and we apply QA obtaining a set of samples. Next, in the postprocessing of QA, we rank the solutions by their robustness, either their worst-case robustness value or regret robustness value. The best robust solution is then returned.

We apply this approach to the unit commitment problem as described in Section <ref>. Here, the residual demand is considered as uncertain, since both the demand for energy and the supply of renewable energies is subject to fluctuations. Thus, given a set of scenarios for the residual demand in each time step, we use the expected residual demand in each time step to build our deterministic QUBO. Remark that it can occur that the produced amount of energy does not satisfy the demand, therefore we utilize the objective function value of the QUBO instead of the linear program  Nevertheless, we filter out solutions that do not satisfy the power unit properties such as minimum running and idle time. For testing, we apply this approach using the D-Wave Advantage System JUPSI in Jülich, Germany and compare it with solving the min-max regret robust optimization problem via Gurobi. We test this on an instance with 2 power plants and 12 time steps and 25 scenarios for the demand, see Figure <ref>. Clearly, while we are not able to find the robust optimal solution, the feasible solutions obtained with D-Wave are close to the robust optimal solution returned by Gurobi.




§ QAOA-BASED ROBUST OPTIMIZATION

In this section, we adapt the approach of Section <ref> to QAOA and provide a new variant. QAOA is a hybrid-classical algorithm described as an variational algorithm. This iteratively executes a parameterized quantum circuit and optimizes the parameters using the measurement of the circuits by a classical optimization routine. It is closely connected to QA mimicking the traversing from the initial to the problem Hamiltonian by using two blocks of parameterized circuits, one for the problem Hamiltonian and one so-called mixer. In contrast to QA, QAOA provides us with the parameters and the building blocks with more control and variability.

We start similar as for QA and we employ QAOA on the problem with expected values of the uncertain parameters. For finding the optimal parameters, we follow along the grid search-based method presented in <cit.>. At the end, we have found optimal parameters for the two building blocks of QAOA. Now, clearly we could resume as for QA and in a postprocessing step harvest the samples output by QAOA for the best robust solution. However, here we introduce a novel variant. For each scenario, we adjust the problem Hamiltonian and thus the QAOA parameterized circuit slightly. We execute this circuit using the parameters obtained in the first step. For each scenario we obtain a sample set and over all samples of each set, we search for the most robust solution, given a robustness concept. This approach includes the set of the scenarios and not just the expected value of the uncertain parameters. Further, it is also possible to be applied in the realm of stochastic optimization: If probabilities of the scenarios are known or these are themselves sampled from a probability distribution, the probability can be used to determine the sample size for each scenario. Then, the samples and their frequency can be used to calculate stochastic measures like expectation value or expected value of perfect information <cit.>.


In the following we sketch a quantum-based approach in which sampling of the quantum circuit is used to include stochastic aspects of the problem formulation in the Quantum Approximate Optimization Algorithm (QAOA) similar to classical two-step approaches <cit.>.


The QAOA is a variational quantum algorithm where free parameters of the parameterized quantum circuit (PQC) need to be determined by a classical optimization routine.
The proposed approach would employ the standard QAOA procedure to determine the optimal parameters for the PQC  using the cost function with the expectation value of the uncertainty, i. e., 𝔼[E^pd_t]=μ_t 
in Eq. (<ref>).
Thus, the first step is equal to the expected value solution EV introduced in sec. <ref>.


In the second step, the cost Hamiltonian of the PQC  are  changed based on the chosen uncertainty scenario.
The uncertainty scenario s consists of a special set of values of E_t,s^pd ∀ t and the respective probability 𝒫_s. 
Specifically, the sampling of the  PQC with the optimized parameters is modified by using different scenario-based values of the PV power, E_t,s^pd.
We assume the variance in E_t,s^pd to be small and with it the changes in the cost Hamiltonian.
A slightly different approach can be used alternatively, where the required conditional gates or the possibility to change the phase angle of R_zz-gate during the sampling are removed.
Based on the probability distribution, a few different scenarios s can be selected and the number of samples of a certain scenario is given by the respective probability 𝒫_s.
Thus, each scenario-based quantum circuit is sampled n_s-times and all scenario-based samples are summed up to provide the probability distribution of the quantum states including the probability of the uncertainty.



This method is applied to the EV charging scheduling problem of sec. <ref>, where the production of PV is considered as uncertain e.g., due to clouds reducing sunshine. As the uncertainty is already in the objective function, we do not have to make any alterations. We are considering a problem with two time steps and 25 scenarios for the PV supply. The distribution of the 25 scenarios is given in Figure <ref>. We execute the circuits using a quantum simulator and no real hardware. For the first step, Figure <ref> shows corresponding energy landscape we traverse in our search for the optimal parameters for QAOA. After executing QAOA for each scenario, we are considering the min-max regret robustness here as well. In our small experiment, we obtain the same charging schedule as a classical algorithm can provide with a min-max regret of 1.9. 


    

The input parameter for a problem with two time steps are given in tab together with the numerical values for the charging schedules obtained using a classical brute force ansatz j_bf and the 1^st step j_1, where both using the expectation value μ of the PV power, and the 2^nd step of the two-step approach including the 25 scenarios j_2.

The distribution of the 25 scenarios and the energy expectation value landscape are visualized in figs. <ref> and <ref>, respecitvely.




    

It can be seen from tab. <ref>, that the brute-force algorithm produces two states with equal costs, i. e., j_bf⊂[1,1],[1,2], whereas the state with the highest probability 𝒫 (see tab. <ref> for both, the 1^st and the 2^nd step, is equal to j_1=j_2=[1,2] and, thus, derived values like expected value of using expectation value solution EEV and the value of the stochastic solution VSS are identical.
Furthermore, it can be seen, that by including the scenarios (2^st step) the probability of this state can be enhanced.
For this example, it can be concluded that a classical brute force ansatz giving all solutions for the expectation value μ of the PV power is worse than the results of the two-step approach, which can be seen on EEV_bf>EEV_1=EEV_2 and, thus, VSS_bf>VSS_1=VSS_2.
Interestingly, even the 1^st step, i. e., using only the expectation value μ calculates the right schedule for this example as can be seen also from VSS_1=VSS_2=0.
However, the increased probability 𝒫_2>𝒫_1 shows the benefit of the 2^nd step. 
In comparison to the wait & see method, all calculation gives worse results as seen by the EVPI value.

For the robust measures, it can be seen, that the same charging schedule j_1=j_2=j_SR=j_RP is found, which indicates a certain robustness of the two-set approach.



§ OUTLOOK

The exemplary results of both experiments are promising for solving robust optimization problems with quantum computing. Further investigations including a well-defined benchmark will verify this hypothesis. Additionally, if the probability is included in the QAOA approach, quantum computing can be used to solve stochastic optimization problems with different stochastic measurements as well. We will pursue this in the future. Additionally, a sensitivity analysis is ongoing to evaluate the limits of the proposed approaches due to the variations of the expectation value landscape for the scenarios.







We acknowledge the funding by Bundesministerium für Wirtschaft und Energie, Germany through the project “EnerQuant” (Grant No. 03EI1025A) and gratefully acknowledge the Jülich Supercomputing Centre (https://www.fzjuelich.de/ias/jsc) for supporting this work by providing computing time on the D-Wave Advantage™ System JUPSI through the Jülich UNified Infrastructure for Quantum computing (JUNIQ) in the project “Robust optimization for the Unit Commitment Problem” (Project No. 28042). P.H. was additionally funded by Bundesministerium für Bildung und Forschung (BMBF), Germany through the project “QuSAA” (Grant No. 13N15695) and S.L. by the European Union under Horizon Europe Programme - Grant Agreement 101080086 — NeQST. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or European Climate, Infrastructure and Environment Executive Agency (CINEA). Neither EU nor granting authority can be held responsible for them.











