Decomposition

Decomposition approaches take advantage of certain problem structures to separate them into multiple related problems which are each more easily solved. Decomposition also allows us to do the inverse, which is to combine independent problems into a single problem, where each can be solved separately but with communication between them (e.g. investments and operations problems)

Decomposition thus allows us to do a number of things

• Solve larger problems which are otherwise intractable
• Include more detail in problems which otherwise need to be simplified
• Combine related problems (e.g. investments/operations) in a more scientific way (rather than ad-hoc).
• Employ parallel computing methods to solve multiple problems simultaneously.

High-level Decomposition Algorithm

The high-level algorithm is described below. For a more detailed description please see Benders decomposition

• Model initialisation (preprocessdatastructure, generate temporal structures etc.)
• For each Benders iteration
  • Solve the master problem. In the first iteration, investments are fixed to benders_starting_units_invested, benders_starting_connections_invested and benders_starting_storages_invested where defined.
  • Fix the investment decisions (units_invested_available, connections_invested_available and storages_invested_available) in the operations sub problem
  • Solve the operations sub problem, rolling over all optimisation windows
  • Save the sub problem objective value and the reduced costs of the fixed investment variables, i.e. the marginal value of one more unit, connection or storage
  • Compute the Benders gap and test for convergence
  • Add a Benders cut to the master problem
  • Next Benders iteration

The algorithm stops when the gap is below decomposition_max_gap and at least decomposition_min_iterations have been done, or when decomposition_max_iterations is reached. The Benders gap is $2 (z_{upper} - z_{lower}) / (z_{upper} + z_{lower})$, where $z_{lower}$ is the master problem objective value and $z_{upper}$ is the sub problem objective value plus the investment costs.

Duals and reduced costs calculation for decomposition

The marginal values above are computed as the reduced costs of relevant optimisation variables. However, the dual solution to a MIP problem is not well defined. The standard approach to obtaining marginal values from a MIP model is to relax the integer variables, fix them to their last solution value and re-solve the problem as an LP. This is the standard approach in energy system modelling to obtain energy prices. However, although this is the standard approach, it does need to be used with caution. The main hazard associated with inferring duals in this way is that the impact on costs of an investment may be overstated. However, since these duals are used in Benders decomposition to obtain a lower bound on costs (i.e. the maximum potential value from an investment), this is ok and can be "corrected" in the next iteration. And finally, the benders gap will tell us how close our decomposed problem is to the optimal global solution.

In Benders decomposition, if the operations sub problem has integer variables, the reduced costs for the Benders cuts are computed from an LP copy of the sub problem where only the investment variables are fixed. The other integer variables, such as units_on, are relaxed but not fixed.

Reporting dual values and reduced costs

To report the dual of a constraint, one can add an output item with the corresponding constraint name (e.g. constraint_nodal_balance) and add that to a report. This will cause the corresponding constraint's relaxed problem marginal value will be reported in the output DB. When adding a constraint name as an output we need to preface the actual constraint name with constraint_ to avoid ambiguity with variable names. So to report the marginal value of constraint_units_available we add an output object with the same name.

To report the reduced cost for a variable which is the marginal value of the associated active bound or fix constraints on that variable, one can add an output object with the variable name prepended by bound_. So, to report the unitson reducedcost value, one would create an output item called bound_units_on. If added to a report, this will cause the reduced cost of units_on in the final fixed LP to be written to the output DB.

Using Decomposition

Assuming one has set up a conventional investments problem as described in Investment Optimization the following additional steps are required to utilise the decomposition framework:

• Set the model_type parameter for your model to spineopt_benders.
• Optionally adjust decomposition_max_gap (default 0.05, i.e. a relative Benders gap of 5%) and decomposition_max_iterations (default 10). A suitable number of iterations depends on the size and nature of the problem.
• Optionally set decomposition_min_iterations and starting investments for the first iteration (benders_starting_units_invested etc.).

Once the above is set, all investment decisions in the model are automatically decomposed and optimised in a Benders master problem. This behaviour may change in the future to allow some investment decisions to be optimised in the operations problem and some optimised in the master problem as desired.

Reporting results

With Benders decomposition, investment costs are part of the master problem and operating costs part of the sub problem. SpineOpt combines them in the reported results, so e.g. the total_costs output includes both.

The solution_stats output also includes the final benders_objective_lower_bound, benders_objective_upper_bound, benders_gap and benders_iteration_count.

By default, results are only written once the algorithm has finished. To write the results of every iteration, set benders_iterations_reporting_active to true.