CPLEX solver for quadratic problems with barrier algorithm

Question

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?

Answer 1

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.

• If your problem has a single optimal solution, the barrier solution will be somewhere close to the vertex but inside the feasible region. Such a solution will have many variable values like 0.00001, 0.99999, etc.
• If your problem has multiple optimal solutions, the barrier solution will be somewhere close to the center of this multiple optima but inside the feasible region. Such a solution will have many variable values between their bounds.

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.