2
$\begingroup$

I'm writing a convex minimization model with a quadratic objective function and linear constraints in C#.

I set CPLEX to solve the problem with the barrier algorithm. The interesting thing is when I look at the log file to follow the process of solving, I see the problem is solved in some iterations first, then again the cycle of solving starts and objectives of primal and dual problem in each iteration are equal to the former solution cycle. The problem is I can't figure out the reason of doubling the solution cycle and how to stop it.

Can anyone help me with that?

$\endgroup$
1
  • 4
    $\begingroup$ Hi @Saba Kiani Welcome to or.stackexchange. I think you would get more and better help if you copy-paste (some of) the engine log that illustrates your problem. $\endgroup$
    – Sune
    Nov 29, 2021 at 10:48

1 Answer 1

5
$\begingroup$

The barrier algorithm is an interior-point method i.e. it starts from a point inside the feasible region and iteratively moves towards the optimal one. This typically results in a solution that does not lie exactly at the vertex but in the interior. This is where you'll see the barrier algorithm terminate in the CPLEX log.

Once the barrier algorithm terminates, CPLEX (like most other solvers) starts a "crossover" phase, by default, where it tries to get a vertex solution (with the accompanied basis) from the barrier solution. It does so by pushing the primal & dual variable values to their bounds and repairing any resulting infeasibilities with simplex. In many cases, the crossover can take a long time to finish (sometimes even longer than the barrier algorithm itself). However, this is not really necessary if you're only concerned with getting the optimal solution to your problem. You can disable it in CPLEX by setting the solutiontype parameter to 2.

Some benefits of crossover (which, I suspect, are the reasons why most solvers enable it by default) are:

  • Once the solver has a vertex solution, it can use it to initiate subsequent simplex solves. This is particularly useful for solving LPs sequentially where the problem changes minimally (Eg. adding or removing a few constraints, changing a few variable bounds, etc.)
  • Without the basis (from the vertex solution), there is no convenient way of querying which variables and constraints are binding in the optimal solution.
  • Many real-world problems have multiple optima and practitioners prefer sparse solutions with variable values set at their bounds. Lots of 0 & 1.
$\endgroup$
3
  • $\begingroup$ But I don''t think there is any crossover for QP, which is the subject of the question. Question is vague as to whether it is continuous QP or MIQP, though. $\endgroup$ Dec 1, 2021 at 1:01
  • 1
    $\begingroup$ CPLEX does have a crossover phase for QPs. Check the log output of the toy example problem qpex here: pastebin. There is a section for "QP crossover" in the log. Doesn't this surely indicate that there is a crossover phase here? $\endgroup$
    – Samarth
    Dec 1, 2021 at 1:58
  • 1
    $\begingroup$ Also, check this old blogpost from Erwin Kalvelagen. $\endgroup$
    – Samarth
    Dec 1, 2021 at 2:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.