Decision Optimization

 View Only
  • 1.  Warmstarting in a moving horizon context with Cplex C API

    Posted Mon June 01, 2020 10:27 AM
    Hello,

    I have a MILP which I want to solve on a horizon T = {1,...,N}. Since the problem would be too large, I intend to solve it with a moving horizon approach. What I do is solve the MILP (lets call it P1) on the shorter horizon T1 = {1,...,k} of length k, k < N, then shift the horizon by l, l < k, and solve the MILP for T2 = {l,...,l+k} (P2), and so on until I reach the end of the horizon T. My total solution will then be fused together from all the subsolutions: Indices 1 to l would be from the solution P1, indices l+1 to 2l would be from P2 and so on.

    Now to my problem: I would like to warmstart the next problem with the solution of the previous problem. Lets say I have the solution of P1. Since the horizons of P1 and P2 overlap on the indices l to k, I would like to take the solution of P1 and warmstart P2 on these indices. For example if the shift is only 1, then the overlap is very large and probably would give a huge improvement in computation time when warmstarting. What I did for now is write out the solution with CPXXsolwrite(). But how can I now use this to warmstart the next problem? Would I need to shift manually all the variables in that file? Or is there an easier way to do what I described above?

    Would be happy for any advice for this.

    Best regards,
    Duc
    #DecisionOptimization


  • 2.  RE: Warmstarting in a moving horizon context with Cplex C API

    IBM Champion
    Posted Mon June 01, 2020 01:48 PM
    A rigorous answer may depend on exactly how the model is to be used. In many rolling horizon applications, I believe the policy is to freeze decisions from the previous solution. Certainly, barring a time machine, you would freeze decisions that have already passed. So presumably in your second run (starting at time l) the model parameters related to starting conditions would be computed to reflect the state of the system at time l in the first solution. That leaves decisions in the overlap period (time l to time k). It would be reasonable to fix those variables to their values in the previous solution (by setting lower bound = upper bound = value) and let the presolver eliminate them. Alternatively, if you wanted to allow the solver to change those solutions, you could create a MIP start using CPXXaddmipstarts, specifying values for just the variables in the overlap and setting effort level 3 (having CPLEX solve a "subMIP" to fill in the remaining variable values). Whether the time spent completing the partial solution was worth the effort (versus just letting CPLEX start from scratch) would be an empirical question.

    I would not try to use the solution you wrote, since that solution will either contain values for variables that do not exist in the second model or will have an index mismatch (e.g., x[19] in the solution should now be x[15]), depending on how you write your model.

    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------



  • 3.  RE: Warmstarting in a moving horizon context with Cplex C API

    Posted Wed June 03, 2020 10:36 AM
    Thank you for you advice. I will try out the option with CPXXaddmipstarts.
    I figured that it would be hard to use the solution I wrote.


    ------------------------------
    Do Duc Le
    ------------------------------



  • 4.  RE: Warmstarting in a moving horizon context with Cplex C API

    Posted Thu July 09, 2020 08:29 AM
    Hi,

    it has been a while, but I have another question about the implementation. What I have been doing is to create a new cplex env and cplex lp for each subproblem. That way all the internal information about the previos iteration is lost. Does it make sense to just "update" the lp in each step instead of creating a whole new env and lp (by updating I can imagine to introduce new variables for the new timepoints and fixing the variables for the old timepoints outside of the overlap, or maybe some other more clever way)? Can cplex then somehow use the internal information from the previous iteration, e.g. cuts so far or other things, or does it not make any difference?

    ------------------------------
    Do Duc Le
    ------------------------------



  • 5.  RE: Warmstarting in a moving horizon context with Cplex C API

    IBM Champion
    Posted Fri July 10, 2020 11:30 AM
    When you say "lp" I assume you mean MILP. If you modify the previous MILP, CPLEX will start fresh. Previous cuts, bound tightening etc. might not be valid in the revised model. I think the main consideration would be whether building each MILP model takes significant time and, if so, whether modifying the previous model is faster or slower than building a new model (which is an empirical question).

    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------



  • 6.  RE: Warmstarting in a moving horizon context with Cplex C API

    Posted Tue July 14, 2020 05:27 AM
    Yes, i meant MILP. Thank you very much for the info.

    ------------------------------
    Do Duc Le
    ------------------------------