Too long execution time for a Dantzig-Wolfe decomposition method master problem

GAMS
1

Hi All,

I’m now trying to solve a large Variational Inequality problem. And I solve it by two ways, using PATH solver solve it directly and use Dantzig-Wolfe method to solve it in a decomposition way. And when I implement the second way in GAMS, I found the time to solve it is relatively short, but the execution time for the master problem will be much slower, which cause the DW method much solver compared to PATH solver in total. I am wondering if there is a method to solve this problem？

I attach the solver part of the log file:

The first is from PATH solver:

MODEL STATISTICS

BLOCKS OF EQUATIONS           3     SINGLE EQUATIONS       21,839
BLOCKS OF VARIABLES           5     SINGLE VARIABLES       62,774
NON ZERO ELEMENTS       184,155     NON LINEAR N-Z         81,840
DERIVATIVE POOL              20     CONSTANT POOL              46
CODE LENGTH             368,310


----    395 Solve Fini gasEnEquil    0.073     1.634 SECS     31 MB  184155
GENERATION TIME      =        0.800 SECONDS     31 MB  26.1.0 rf2b37b9 DEX-DEG


EXECUTION TIME       =        1.634 SECONDS     31 MB  26.1.0 rf2b37b9 DEX-DEG
----    395 GAMS Fini                0.029     0.029 SECS     31 MB 
----      1 InitE                    0.001     0.001 SECS     14 MB 
----      1 ExecInit                 0.000     0.001 SECS     14 MB 
----    395 Solve Alg  gasEnEquil    0.000     0.001 SECS     14 MB 
GAMS 26.1.0  rf2b37b9 Released Feb  2, 2019 DEX-DEG x86 64bit/Mac OS X                                                                                                                                                              04/26/19 12:59:06 Page 1857
G e n e r a l   A l g e b r a i c   M o d e l i n g   S y s t e m
Solution Report     SOLVE gasEnEquil Using EMP From line 395


               S O L V E      S U M M A R Y

     MODEL   gasEnEquil          
     TYPE    EMP                 
     SOLVER  JAMS                FROM LINE  395

**** SOLVER STATUS     1 Normal Completion         
**** MODEL STATUS      2 Locally Optimal           

 RESOURCE USAGE, LIMIT       2375.177      1000.000
 ITERATION COUNT, LIMIT     26615    2000000000
 EVALUATION ERRORS              0             0

JAMS 1.0         26.1.0 rf2b37b9 Released Feb 02, 2019 DEG x86 64bit/Mac OS X 

JAMS - Solver for Extended Mathematical Programs (EMP)
------------------------------------------------------

--- Using Option File
Reading parameter(s) from "/Users/jiajieshen/Dropbox/optimization/FProject_1/MyTest_v3/simpleModel/simpleModel_test/DWgas_mP_v2_l_LS2/jams.opt"
>>  *filename gasEnEnquil.gms
>>  *dict gasEnEnquil.txt
>>  subsolver path
>>  subsolveropt 1
Finished reading from "/Users/jiajieshen/Dropbox/optimization/FProject_1/MyTest_v3/simpleModel/simpleModel_test/DWgas_mP_v2_l_LS2/jams.opt"

--- EMP Summary
    Logical Constraints = 0
    Disjunctions        = 0
    Adjusted Constraint = 0
    Flipped Constraints = 0
    Dual Variable Maps  = 0
    Dual Equation Maps  = 0
    VI Functions        = 1364
    QVI Parameters      = 0
    Equilibrium Agent   = 16
    Bilevel Followers   = 0

--- The model /Users/jiajieshen/Dropbox/optimization/FProject_1/MyTest_v3/simpleModel/simpleModel_test/DWgas_mP_v2_l_LS2/225a/emp.dat will be solved by GAMS
---
--- Returning from GAMS step
83204 row/cols, 265860 non-zeros, 0.00% dense.

and one iteration of my master problem will be:

MODEL STATISTICS

BLOCKS OF EQUATIONS           3     SINGLE EQUATIONS        1,468
BLOCKS OF VARIABLES           3     SINGLE VARIABLES        1,468
NON ZERO ELEMENTS       282,391     NON LINEAR N-Z              0
DERIVATIVE POOL              20     CONSTANT POOL              16
CODE LENGTH                   0


GENERATION TIME      =        0.294 SECONDS    607 MB  26.1.0 rf2b37b9 DEX-DEG


EXECUTION TIME       =      131.764 SECONDS    607 MB  26.1.0 rf2b37b9 DEX-DEG
               L O O P S          FOR/WHILE 102

GAMS 26.1.0  rf2b37b9 Released Feb  2, 2019 DEX-DEG x86 64bit/Mac OS X                                                                                                                                                            04/26/19 12:40:01 Page 234037
the main file for Dantzig-Wolfe algorithm for equilibrium
Solution Report     SOLVE gasEnMaster Using MCP From line 767


               S O L V E      S U M M A R Y

     MODEL   gasEnMaster         
     TYPE    MCP                 
     SOLVER  PATH                FROM LINE  767

**** SOLVER STATUS     1 Normal Completion         
**** MODEL STATUS      1 Optimal                   

 RESOURCE USAGE, LIMIT          0.735      1000.000
 ITERATION COUNT, LIMIT       618    2000000000
 EVALUATION ERRORS              0             0
1468 row/cols, 282391 non-zeros, 13.10% dense.

You can see that my master problem size is smaller than the original problem, only the nonzero part is more than the original problem: (282,391 vs 184,155), however, the execution time is much larger(131.764 seconds vs 1.634 seconds) and the memory is much larger(607 MB vs 31 MB). And the master problem solving time is much faster (Resource usage: 0.735 vs 2375.177).

So I think the execution time can be improved in some way. Does anyone has experience on that?

Thanks

2

Hi,

You are comparing the execution time of a single solve approach (EMP) to your manual implementation of an iterative method (DW) where the second lst excerpt shows that the execution time of 131.764 SECONDS was reached at iteration 102. Hence, this execution time involves 102 times generating a model plus reading its solution plus performing whatever steps you have implemented in your loop logic. I don’t say that you cannot speed things up but to me it seems that you comparing apples and oranges.
In case you are not aware of what execution time/phase actually means, the following links might be helpful:
https://www.gams.com/latest/docs/UG_GamsCall.html#UG_GamsCall_TwoPass
https://support.gams.com/gams:what_is_the_meaning_of_compilation_time_generation_time_and_execution_time?s[]=stepsum

If you would like to know in detail how execution is spent, you might want to look into profiling: https://www.gams.com/latest/docs/UG_GamsCall.html#GAMSAOprofile
In the GAMS documentation, there is also a tutorial on reducing (and analyzing) execution time: https://www.gams.com/latest/docs/UG_ExecErrPerformance.html#UG_ExecErrPerformance_ReducingGAMSExecutionTime

I hope this helps!

Fred

PS It is recommended to not run GAMS in synchronized folders such as dropbox (https://support.gams.com/gams:can_i_use_dropbox_with_gams)

3

Hi Fred,

Thanks. This answer helps me a lot.