CGAL users discussion list

[Oren Ben-Kiki <>]

Thanks for the explanations. I guess CGAL is not for me.

I looked at the solvers listed in http://www.numerical.rl.ac.uk/people/nimg/qp/qp.html and didn't find a perfect match for my needs. I'll see if http://plato.asu.edu/sub/nlores.html#QP-problem lists something better.

I can't really give up the open-source requirement, as this is part of an open-source project.

I did notice CVXOPT is very close to what I need, but it seems to be Python-only (calling internal C libraries like BLAS and others to do the heavy lifting). I'm not certain I want to convert the wrapper program from C++ to Python, but perhaps that would be the best approach...

Thanks,

Oren.

On Mon, Oct 2, 2017 at 4:30 PM, Hoffmann Michael <> wrote:

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.



--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss