Originally posted by: jmogali

Hi all, I would like some advice to efficiently resolve QP problems (part of Bundle methods) using CPLEX. Between iterations, a new affine constraint gets added, and the QP objective is changed. Currently, Currently, I use remove and add to modify the objective, and simply invoke cplex.solve() at each iteration, however the performance is slow for my project requirements. I request the members of the community to give me suggestions to speed things up. Also, I have the following questions-:

1. Does cplex automatically warm start from the previous iteration optimum, or should I explicitly use cplex.setStart() method ? Since the primal variables in my problem are unchanging, I tried warm starting using setStart only for those variables but it did not yield any performance gains. Do the members think any more parameters need to be initialized or is this the best I can do for my problem (considering the objective changes between iterations) ?

2. Does anyone have any algorithmic insights as to how Bundle methods are best implemented in practice ? It would be great if you could direct me to an efficient implementation of Bundle methods (apart from http://www.math.chalmers.se/Math/Research/Optimization/reports/masters/Reine_exjobb.pdf).

Thanks,

Jayanth

PS -: I apologize for re-posting in the CPLEX optimizers forum as well.

Originally posted by: RWunderling

I assume you are using QP Simplex to solve your models.  If so, by default CPLEX will attempt to warm-start the optimization after modifying the objective.
If reoptimization is too slow, have you tried solving each model from scratch using QP Barrier?

Roland

Originally posted by: jmogali

Hi Roland, 

                      Thank you for your reply. Well actually, when I posted this question I used Barrier optimization. More recently, I switched to Simplex primal, and the gains over the barrier method has been very limited in terms of time and that too only for a few problems, while in most cases Barrier method from scratch performs better. I have 3 questions to ask,

1. Firstly I dont think Cplex is automatically warm starting from the previous basis (note that I include one new constraint and change the objective between iterations). I say so because, when I included setBasisStatuses() by using the basis from the previous iteration from getBasisStatuses(), it performs faster. However when I do this, I sometimes get warning messages such as "Slack removed by singularity" or "Advanced basis is singular". I know that CPLEX is able to recover from these initializations, so my question is, is there a better way to initialize basis so as to avoid these errors and more generally are there other things I can do for warm starting QP simplex? I read in another post that when such a case happens it may be expensive for CPLEX to fix it,  

2. Perhaps, I have made a mistake in the way I am using getBasisStatuses() and setBasisStatuses(). Below is how I implemented it, 

   iter= 0;

    while(true)

    {

          con.add(//the new constraint of the form <=)

          //Update model with new objective and constraint

          if(iteration > 0)
          {
             rstat.add(IloCplex::AtLower); 
            cplex.setBasisStatuses(cstat, var , rstat , con);
         }

         bool solved = cplex.solve();

         cplex.getBasisStatuses(cstat, var , rstat , con);

         iter++;

     }

Am I correctly using getBasisStatuses() and setBasisStatuses() or do any other flags indicating to cplex need to be set ?  

3. I am perfect illiterate about the simplex algorithm to solve a QP, so pardon me for the following question. Since the problem here is a QP, the optimum can lie in the interior of the feasible set or lie on a face of the constraint polyhedron (in my case it is guaranteed to lie on some face), in such a case I may not get a non-singular basis every time for the solution (by basis, i am assuming it has the same meaning as that for simplex LP , may be non-singular if the minimum lies on face of dimension > 0). If what I said made sense, do you think there is a better way to approach this problem with or without CPLEX?

Thanks a lot in advance,

Jayanth