Overflow problems in CGAL's QP_Solver module

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Overflow problems in CGAL's QP_Solver module

Jean-Philippe Bauchet
Hello,


I am encountering a problem with the module QP_Solver of CGAL 4.9.

I am currently trying to optimize a quadratic function f(X) = 1/2 X^T D X + C^T X under linear constraints AX <= B, but the exact representation mode of each variable x_i of X, makes the program return incorrect results when the number of variables in X (say N) increases, whereas other solvers like IPOPT still return accurate results.

Indeed, due to the use of an exact number type (CGAL::Gpmzf, CGAL::MP_Float) each variable x seems to be computed as x = p / q where p and q are floats : thus there exists m and e such that q = m * 10^e. The problem is, e decreases with the size of X. Beyond a certain threshold for this size, p and q get null and I finally obtain x = 0/0. More details can be found in the attached PDF file. A short runnable code illustrating the problem is also enclosed with this e-mail.

Is there any way to fix this problem ?

Thank you very much for your time, your help and your consideration.

Best regards,


Jean-Philippe Bauchet

mu.dat (3K) Download Attachment
QP_Solver-Report.cpp (8K) Download Attachment
targets.dat (3K) Download Attachment
CGAL_QP.pdf (213K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Overflow problems in CGAL's QP_Solver module

Michael Hoffmann-4
Hi Jean-Philippe,

let me forward you an answer from Bernd Gaertner, see below.

Best regards,
Michael


Thanks for your report. Indeed, the variable values in the solution are of the form p/q, with p and q being of types CGAL::Gpmzf, CGAL::MP_Float. These types, however, are *not* affected by exponent limits such as the types float and double. What happens is just that the output operator for the solution converts them to double in order to display them, and then you may get 0/0. The actual values are nonzero, though. I currently don't know how you can correctly output CGAL::Gpmzf, CGAL::MP_Float; an alternative would be to work with CGAL::Gmpz (long integers) in case your input is (or can be made) integral. Then you get a quotient of CGAL::Gmpz's, and this type has an excat output.


Am 10/01/17 um 15:58 schrieb Hoffmann Michael:

>
>
>> Begin forwarded message:
>>
>> From: Jean-Philippe Bauchet <[hidden email]>
>> Subject: [cgal-discuss] Overflow problems in CGAL's QP_Solver module
>> Date: 10 January 2017 at 15:30:26 GMT+1
>> To: <[hidden email]>
>> Reply-To: <[hidden email]>
>>
>> Hello,
>>
>>
>> I am encountering a problem with the module QP_Solver of CGAL 4.9.
>>
>> I am currently trying to optimize a quadratic function f(X) = 1/2 X^T D X + C^T X under linear constraints AX <= B, but the exact representation mode of each variable x_i of X, makes the program return incorrect results when the number of variables in X (say N) increases, whereas other solvers like IPOPT still return accurate results.
>>
>> Indeed, due to the use of an exact number type (CGAL::Gpmzf, CGAL::MP_Float) each variable x seems to be computed as x = p / q where p and q are floats : thus there exists m and e such that q = m * 10^e. The problem is, e decreases with the size of X. Beyond a certain threshold for this size, p and q get null and I finally obtain x = 0/0. More details can be found in the attached PDF file. A short runnable code illustrating the problem is also enclosed with this e-mail.
>>
>> Is there any way to fix this problem ?
>>
>> Thank you very much for your time, your help and your consideration.
>>
>> Best regards,
>>
>>
>> Jean-Philippe Bauchet
>

--
Prof. Bernd Gärtner
Department of Computer Science
ETH Zürich
CAB G31-1
8092 Zürich
Switzerland
+41 44 632 70 26

[hidden email]
http://people.inf.ethz.ch/gaertner/

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