Problems about reducing the scenario tree size and the number of scenarios in stochastic programming

[Yilin Wang]

Hi everyone,

I am a student from sydney uni, now I confront some major problems
with reducing the scenarios number in my program.

My program is a 24 stages stochastic program, since even with minimum
child branches (2) in each stage, the scenario tree is still
too big to be solved, so I made some contribution probability of
childbraches equal to zero, but I found AIMMS still needs to
calculate these 0 probability scenarios, and the total calcullation
time is still the same.

I am thinking can any one tell me a method that can significantly
reduce the sceanrio tree computing time, or any way that can do
sceanrio reduction in AIMMS. Thanks a lot!!!

By the way, the deterministic model of my model is MIP model and my
solver is CPLEX 12.3.

Regards,

Yilin Wang

[Ovidiu Listes]

Hi Yilin Wang

For generating scenarios, you could use the scenario bundling method
instead of the branching method.
The bundling method will never generate scenarios with 0 probability
in the scenario tree.

If (still) you use the branching method, then the
InitializeChildBranchesCallback should account for 0 chance branches.

In our standard example "Stochastic Programming", one would need to
adjust MyInitializeChildBranchesCallback as


PROCEDURE
identifier : MyInitializeChildBranchesCallback
arguments :
(CurrentStage,Scenario,CurrentChildBranches,CurrentChildBranchName)

DECLARATION SECTION

ELEMENT PARAMETER:
identifier : Scenario
range : AllStochasticScenarios
property : Input ;

ELEMENT PARAMETER:
identifier : CurrentStage
range : Integers
property : Input ;

SET:
identifier : CurrentChildBranches
subset of : Integers
index : cb
property : Output ;

STRING PARAMETER:
identifier : CurrentChildBranchName
index domain : cb
property : Output ;

SET:
identifier : NonEmptyBranches
subset of : StageChildBranches ;

ENDSECTION ;

body :
NonEmptyBranches := { c | BranchChance(c) > 0 };

CurrentChildBranches := { 1 .. card(NonEmptyBranches) };

CurrentChildBranchName(cb) := FormatString( "%e",
element(NonEmptyBranches,ord(cb)) );

ENDPROCEDURE ;

This works as long as the branching is done always with the same
number of branches (at any stage).
If the number of branches should actually depend on the stage, then
MyInitializeChildBranchesCallback should be more sophisticated in
order to reflect that.

Regards
Ovidiu Listes

Senior AIMMS Consultant

[Yilin Wang]

Hi Ovidiu Listes,

Thank you for your help, I really appreciate it. Your method works.

Can you answer me one more question? In my program, the number of
child branches is the same in every stage,
but the probability of each child branch is depended on the stage.
In the model of AIMMS, every child branches have the same
associated probability through the whole 4 stages. How could I control
the probability of each child branch independently in each stage?

Your sincerely,
Yilin Wang

[Marcel Hunting]

Hi,

 

In the procedure MyInitializeStochasticDataCallback of the same standard example "Stochastic Programming", you need to change

 

   RelativeScenarioWeight := BranchChance(CurrentChildBranchElem);

 

into something that depends on the stage, e.g.,

 

   RelativeScenarioWeight := BranchChanceStage(t,CurrentChildBranchElem);

 

were you have to fill BranchChanceStage.

 

Best regards,

 

Marcel Hunting
AIMMS Software Developer