#187 decomposition merge2 - [merged] #256

Closed spine-o-bot closed 3 years ago

In GitLab by @DillonJ on Nov 19, 2020, 09:58

_Merges #187_decompositionmerge2 -> master

Overview

This merge request implements a decomposed bi-level structure to SpineOpt. The general approach is discussed in #187.

At a high level - this MR introduces a second, higher level master problem which has full view of the entire model horizon. The master problem optimizes the investment decision variables and passes them as fix_values to the sub-problem. The sub-problem here is the current SpineOpt model. It is an iterative approach where dual values from the sub-problem inform the master problem regarding the impact of the capacity decision variables on operating costs. This information is added to the master problem in the form of benders cuts.

This MR also contains the following changes :

Changes to temporal_structure.jl to ensure independent temporal structures for multiple problems
Calculation of duals by a final LP model solve where the integer variables are relaxed and fixed
Output of constraint duals and variable bound duals
Model dependent output reports
run_spineopt() has been updated to allow specification of an LP and MIP solver.

Implementation Notes

Choice of the high-level solution algorithm is dictated by a new model_type method parameter. model_type=:spineopt_operations is the default value. A database with a single model by default will run as normal, according to the current algorithm. This allows investments to be determined based on the conventional algorithm without decomposition. To utilize the bi-level decomposed structure one must :
- Create a second model in the database where model_type=:spineopt_master
- Define the model__temporal_block, model__stochastic_structure, model__default_temporal_block and model__default_stochastic_structure relationship. Since currently, only investments are solved in the master problem, the temporal and stochastic structures will primarily relate to investment decisions. However, the dual information passed back to the master problem from the sub-problem will be at the resolution of the units_on variable in the sub-problem. In future, this may be important.
Ideally, the temporal and stochastic structures for investments should be consistent between the master and sub-problems (master and operations models respectively). However, as information is exchanged between the two models using timeseries parameters, this is not strictly necessary.
A maximum number of high-level Benders iterations can be specified by setting the model parameter max_iterations.
In each Benders iteration, the master problem solution yields a lower bound on the total objective which the sub-problem yields an upper bound. Convergence of the Benders algorithm is decided by the relative gap between these two values. This relative gap is set by the model parameter max_gap

Internal Data Structure

Some values, such as the marginal values and investment decisions depend on the high-level benders iteration as an index. A new object class called benders_iteration is thus created in preprocess_data_structure
A relationship unit__benders_iteration is defined to hold the unit investment decisions in each iteration: units_invested_bi(unit=u, benders_iteration=bi) and the marginal value of the units_on constraint which tells the master problem the marginal decrease in costs possible via the addition of a new unit of type u: units_available_mv(unit=u, benders_iteration=bi)

High-Level Algorithm

The high-level algorithm works as follows:

Model initialisation (preprocess_data_structure, generate temporal structures etc.)
For each benders_iteration
- Solve master problem
- Process master-problem solution:
  - set units_invested_bi(unit=u, benders_iteration=bi) equal to a timeseries representing the investment variables solution from the master problem
- Rewind and update operations problem
- Solve operations problem loop
- Process operations sub-problem
  - set units_available_mw(unit=u, benders_iteration=bi) equal to a timeseries representing the marginal value of the units_on bound constraint
- Test for convergence
- Update master problem
  - Add Benders cuts constraints (constraint_mp_units_invested_cuts)
Next benders iteration

Dual Calculation

The optimize_model!() function has been updated to optionally include an additional step for the calculation of duals. 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 (see here for example). 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.

This additional relaxed LP solve is done as follows:

add_varialbe!() stores the list of integer and binary variables in m.ext[:integer_variables]
the fix_value for integer variables is set to the last MIP solution value
the integer constraints on the integer variables are unset()
A final LP is solved
required dual values are saved
integer constraints on integer variables are set()

This final fixed LP solve is trigged by specifying calculate_duals=true in the call to

optimize_model!()

Reporting dual values:

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 (e.g. units_available). So to report the marginal value of units_available we add an output object called "constraint_units_available".

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 units_on reduced_cost 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.

Finally, if any constraint duals or reduced_cost values are requested via a report, calculate_duals is set to true and the final fixed LP solve is triggered.

SpineOpt Template

These are the changes to the template:

model_report: relationship which determines which reports are written for which model
model_type: Method parameter using new parameter list model_type_list. Used to control model-specific functionality in SpineOpt. Current possible values are :spineopt_operations and :spineopt_master. The default value is:spineopt_operations` so if a user does nothing, current functionality is retained
max_gap(model=anything) - used currently for master problem convergence criterion but we can use it in future to set the optimality gap for the regular (operations) model.
max_iterations(model=anything) - used currently for master problem convergence criterion. Perhaps it can be used in future to set the max iterations for the regular (operations) model.
is_active : universal parameter defined on all object classes, to be used as features with the object_activity_control tool. When this tool filter is active, any object with is_active==true is logically excluded from the model.
object_activity_control tool. See above
*/is_active features. See above

In GitLab by @DillonJ on Nov 19, 2020, 10:00

changed the description

In GitLab by @DillonJ on Nov 19, 2020, 10:01

changed the description

In GitLab by @DillonJ on Nov 19, 2020, 10:02

changed the description

In GitLab by @DillonJ on Nov 19, 2020, 10:03

changed the description

In GitLab by @DillonJ on Nov 19, 2020, 10:07

added 1 commit

050c9f34 - Removes some obsolete files and

Compare with previous version

In GitLab by @DillonJ on Nov 19, 2020, 10:22

added 1 commit

1103d907 - Fixed error in call to `reset_temporal_structure()`

Compare with previous version

In GitLab by @DillonJ on Nov 19, 2020, 11:01

changed the description

In GitLab by @DillonJ on Nov 19, 2020, 14:40

added 37 commits

1103d907...b0620ece - 35 commits from branch master
cc08cfe3 - Merge branch 'master' of https://gitlab.vtt.fi/spine/model.git into #187_decomposition_merge_3
8f891c8a - Removed extraneous file

Compare with previous version

In GitLab by @DillonJ on Nov 19, 2020, 14:42

OK - so here's where we are now :

Test Summary: | Pass  Total
test set      |  941    941

In GitLab by @manuelma on Nov 19, 2020, 16:05

Which branch should I checkout? I'm trying #187_decomposition_merge2 to no luck (plenty of No model of type spineopt_operations defined when running tests)???

In GitLab by @DillonJ on Nov 19, 2020, 16:10

Hi Manuel - yes it should be this one.

Do you have the latest SpineInterface? ;-)

In GitLab by @manuelma on Nov 19, 2020, 16:11

Which SpineInterface commit do I need?

Edit: Nevermind, I got it now.

In GitLab by @manuelma on Nov 19, 2020, 16:17

What's this?

In GitLab by @manuelma on Nov 19, 2020, 16:19

What's j, k, and current_bi? Where's current_bi defined in the global scope?

In GitLab by @manuelma on Nov 19, 2020, 16:21

Is the object_activity_control needed for decomposition to work?

In GitLab by @manuelma on Nov 19, 2020, 16:27

added 2 commits

d2ac9feb - 1 commit from branch master
cd4a6d0e - Merge branch 'master' into #187_decomposition_merge2

Compare with previous version

In GitLab by @manuelma on Nov 19, 2020, 16:31

What's the purpose of the t argument here?

In GitLab by @DillonJ on Nov 19, 2020, 16:31

This does two things

Originally there outputs which was not model dependent. I replaced this with m.ext[:outputs] which is model dependent. It's a list of outputs, so all things that need to be saved
It works out if there are any bound* or constraint* outputs which would require the calculation of duals

In GitLab by @DillonJ on Nov 19, 2020, 16:33

No - but I wanted an easy way to test with and without the master model. This was hard otherwise.

In GitLab by @DillonJ on Nov 19, 2020, 16:34

If there's no t index, you have problems with the output and reporting functionality. In the end I never used this function actually. I think it could be removed.

In GitLab by @manuelma on Nov 19, 2020, 16:34

Thanks for the explanation! So any output that starts with the string bound_ or constraint_ need the duals be calculated? Is this robust?

Edit: by robust I mean, isn't there another way to 'mark' the fact that a variable needs to recalculate the duals other than using the name?

In GitLab by @manuelma on Nov 19, 2020, 16:37

added 1 commit

467f8a99 - Fix run_spineopt signature to be compatible with latest masters

Compare with previous version

In GitLab by @manuelma on Nov 19, 2020, 16:39

Ok, thanks for the explanation. I'll check if it's called and if not I will remove it.

In GitLab by @manuelma on Nov 19, 2020, 16:40

changed this line in version 7 of the diff

In GitLab by @manuelma on Nov 19, 2020, 16:40

added 1 commit

71e632f9 - Get rid of unused `trivial_index` function

Compare with previous version

In GitLab by @manuelma on Nov 19, 2020, 16:41

Nice.

In GitLab by @manuelma on Nov 19, 2020, 16:41

mentioned in commit 0a1e673311206c3c641ab3a77ffd1031cdb76fe5

In GitLab by @manuelma on Nov 19, 2020, 16:55

I just merged this into master. Thanks for the awesome job @DillonJ. I also went through the code and it feels very powerful. It might be that I just got to press the green button, but I'm feeling really excited about all this, such a promising tool, done with so limited resources.

spine-tools / SpineOpt.jl