CGAL users discussion list

["Hoffmann Michael" <>]

Here are some answers from Bernd Gaertner 
<>:

> I am writing a program that needs to solve many related quadratic 
> minimization problems with linear constraints. Essentially the program 
> constructs an initial (sparse) problem and incrementally adds new variables 
> and constraints to it, calling CGAL::solve_quadratic_program at each step. 
> The expected number of steps is large (thousands of solver calls).
> 
> If it matters, my problem is of the form minimize(sum w_i * x_i^2), where 
> w_i >= 0, subject to x_i >= 0, and some linear constraints A * X 
> </<=/=/>/>= B (where A is very sparse). The size of the problem starts 
> small and scales up to hundreds, possibly thousands of variables and 
> constraints.

It is important to understand that CGAL's solver is designed to compute the 
exact solution. Technically, you can work with inexact number types, but the 
code will not be robust then and most likely crash / compute the wrong 
solution in a large number of cases. And if you are working with exact 
numbers, with thousands of variables and constraints (sparse or not), 
performance will be extremely poor, since the rational numbers that come up 
in the computations and results have a high number of digits in their 
numerators and denominators. 

> Each next step's solution values for most of the variables shared with the 
> previous step, would be identical or very close to the previous solution's 
> values. It would therefore seems useful to provide an initial guess for 
> these variables, to speed up computing the new solution.
> 
> Looking at the API I don't see a way to provide such an initial guess. 
> Searching found 
> https://stackoverflow.com/questions/43380565/give-an-initial-guess-to-the-quadratic-programming-solver-of-cgal
>  which has gone unanswered for 5 years, which doesn't look promising...
> 
> So, I guess there is no way to provide such an initial guess? Is this 
> something that can be faked somehow? Is there some alternative approach I 
> could use?

Indeed, there is no way to specify an initial solution. You would have to 
patch the code to achieve this, and from what I remember, this would be 
nontrivial in the current design. 

> In addition - I love the fact CGAL allows me to specify iterators to 
> provide the very sparse matrix A, since writing my own iterator makes it 
> easy to describe an A' = extension of A without copying all the data of A.
> 
> However... does the internal solver benefit at all from sparseness? The 
> iterator API hints that the solver treats the problem as dense (that is, 
> the iterators return every element, even the zero ones, instead of 
> returning the next non-zero element). Unless the solver does something 
> smart with the returned zero values?

It doesn't, I'm afraid. So internally, the problem is indeed dense, even if 
the specification is sparse. We have an experimental package dealing with the 
sparse case efficiently, but it is not finished and never made it into the 
release. 

> So, would I be better off using a sparse solver instead?

Yes.

> Looking around I saw IPOPT which is a more general NPL solver, but seems to 
> benefit directly from sparseness, and allows for an initial guess. But it 
> seems there's no easy way to "extend" an existing problem with additional 
> variables and constraints. Also, being a general NPL solver, it probably 
> will be less efficient for simple QP problems than a dedicated QP solver...?
> 
> I don't suppose there's such a thing as a:
> A. Dedicated QP solver,
> B. Which allows providing one's own iterators (to allow extending problem 
> instances),
> C. Benefits from sparseness,
> D. Allows specifying an initial guess,
> E. Is open-source…

As far as performance is concerned, I can tell you right away that for your 
scenario, the CGAL solver is not suitable. Did you check the links available 
from here: https://neos-guide.org/content/quadratic-programming#software ?

If you want to give up E, CPLEX might be an option. It comes as a callable 
library, so I would assume that with this, you can achieve B.