Solving a small model iteratively slows down solution time as the number of iterations progress

Answered

Hari Krishna Achuthan Parthasarathy

• November 24, 2023 00:20

I have a small program in AMPL which is basically implementing benders' decomp. I am trying to solve a small model with a number of constraints and variables which do not change over the course of the iterations. I have two loops inside which i call to solve this small model. The first few iterations are fast but as time progresses, it slows down. I understand that gurobi has warm start features but I don't know if that is the reason why as time progress the code slows down. I dont do any background operations when I run the code and I do not change any large parameter or data structures between iterations. Is warm start the issue here ? if so please do let me know if i can somehow introduce a solver reset statement in ampl or do suggest what other problems might be the cause

Related to

• Bender's
• AMPL

0

• 

  Robert Fourer

  • November 24, 2023 15:48

  

  

  I wouldn't expect that warmstarting would slow down Gurobi's solution process. But you can try turning off warmstarting by setting "option reset_initial_guesses 1;" in AMPL.

  It is possible that the subproblems are simply becoming harder as Benders cuts are added. As a quick check on this, you could look at the number of iterations Gurobi reports that it needed to solve each subproblem, to see if it is tending to increase from one Benders step to the next.

  0
• 

  Hari Krishna Achuthan Parthasarathy

  • November 25, 2023 19:41

  

  

  

  I did try setting  "option reset_initial_guesses 1;". It did not create much of a change. I do not know if this setting is working or not but yes I did try it.

   

  My code is developed such that I generate multiple cuts by solving the subproblem for many iterations (around 24 X 21 times) before I apply the cuts to the master problems. The master problem solves fast which is not the problem.

  My problem structure is like this:

  Loop A (1 to 5):

      solve master;

       Loop B (1 to 24):

         update some values;

          Loop C (1 to 30):

                solve the subproblem;

                 generate cuts;

            end

           end

   apply cuts;

  end

   

  It is sub problem solving which is slowing down. The first lets say 10 iterations of Loop B are fast but slow down after that. Loop A then iterates, after which Loop B is still slower.

  That is why I thought maybe solver caching is causing the program to slow down. As far as I can see there are no memory leaks. Do let me know if i can check other avenues.

  0
• 

  Robert Fourer

  • November 26, 2023 15:40

  

  

  The reset_initial_guesses setting works, but if it does not make a big difference, then you can conclude that the slower solves are likely not due to warm starts. Here are some additional checks that you can perform, to learn more about the possible causes:

  1. Add "option show_stats 1;" at the beginning. Then for each solve, you will see a summary like the following:

  Presolve eliminates 1920 constraints.
  Substitution eliminates 4 variables.
  Adjusted problem:
  19200 variables, all linear
  2592 constraints, all linear; 47840 nonzeros
        1920 equality constraints
        672 inequality constraints
  1 linear objective; 19200 nonzeros.

  Check whether there is any increase in the the size of the "adjusted problem" that is sent to Gurobi. (Note that even if your subproblems originally have the same numbers of variables and constraints, AMPL's presolve phase may reduce and simplify some of them more than others.)

  2. Add "display _solve_elapsed_time;" after the subproblem "solve;" statement, to see whether Gurobi is taking an increasing amount of time to find each solution.

  3. Examine AMPL's solve result messages for Gurobi, which will look like this:

  Gurobi 10.0.3: optimal solution; objective 125714168.2
  1281 simplex iterations
  22 barrier iterations

  Check whether the number of iterations is increasing significantly, which would indicate that the subproblems are becoming harder.

  4. Add "option gurobi_options 'outlev=1';" -- or if you are already setting a gurobi_options string, add outlev=1 to it. This will produce a detailed log of every Gurobi solve, which is valuable for difficult situations and for getting help from Gurobi support. (I have listed this last because it will produce a huge amount of output, so it's worth trying the simpler suggestions first.)

  0

Please sign in to leave a comment.