[Scip] Recommended language for QP with quadratic and cubic constraints
Ramón Casero Cañas
rcasero at gmail.com
Mon Feb 24 16:47:44 CET 2014
Thanks! When I say I'm new to these problems, it's not false modesty :)
On 24 February 2014 14:01, Stefan Vigerske <stefan at math.hu-berlin.de> wrote:
> Hi,
>
> every local optimum is per definition also a feasible point, i.e., a point
> that satisfies the constraints (within feasibility tolerances).
>
> Stefan
>
>
> On 02/24/2014 02:53 PM, Ramón Casero Cañas wrote:
>>
>> Sorry, it was my fault. I mistook Ipopt for lpopt ;) Thanks Giacomo
>> for the advice and Stefan for the clarification.
>>
>> IPOPT may actually be just what I need. So if I have a quadratic
>> problem with non-convex constraints, then the problem has local
>> minima, and IPOPT will then find one of those minima, right? But the
>> important part here is: Will any solution it finds fulfil the
>> constraints (if there's a feasible solution)?
>>
>> Whether the minimum it finds is local or global is not so important
>> for my problem. What is really important is that the constraints are
>> fulfilled.
>>
>> At this point, I have been able to write a Matlab function to convert
>> my objective function and constraints to PIP format, pass it to the
>> scip binary and read back the file with the solution.
>>
>> I don't know yet how to pass parameters to the scip binary (I think, I
>> can create an scip.set file for that). With the default options, I
>> think I'm using Ipopt, and that it's trying to maximize rather than
>> minimize my objective function. Working on it, will report back with
>> results when I make it work.
>>
>>
>> Iter Sigma Time (sec)
>> ===================================================
>> 0 3.4026e+01 0.0000e+00
>> SCIP version 3.0.2 [precision: 8 byte] [memory: block] [mode:
>> optimized] [LP solver: SoPlex 1.7.2] [GitHash: 14f3662]
>> Copyright (c) 2002-2013 Konrad-Zuse-Zentrum fuer Informationstechnik
>> Berlin (ZIB)
>>
>> External codes:
>> SoPlex 1.7.2 Linear Programming Solver developed at Zuse
>> Institute Berlin (soplex.zib.de) [GitHash: 9830bec]
>> cppad-20120101.3 Algorithmic Differentiation of C++ algorithms
>> developed by B. Bell (www.coin-or.org/CppAD)
>> ZLIB 1.2.7 General purpose compression library by J.
>> Gailly and M. Adler (zlib.net)
>> GMP 5.1.1 GNU Multiple Precision Arithmetic Library
>> developed by T. Granlund (gmplib.org)
>> ZIMPL 3.3.1 Zuse Institute Mathematical Programming
>> Language developed by T. Koch (zimpl.zib.de)
>> Ipopt 3.11.0 Interior Point Optimizer developed by A.
>> Waechter et.al. (www.coin-or.org/Ipopt)
>>
>> user parameter file <scip.set> not found - using default parameters
>>
>>
>> read problem </tmp/model.pip>
>> ============
>>
>> original problem has 15 variables (0 bin, 0 int, 0 impl, 15 cont) and
>> 15 constraints
>>
>> presolving:
>> (round 1) 0 del vars, 0 del conss, 0 add conss, 1 chg bounds, 0 chg
>> sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
>> presolving (2 rounds):
>> 0 deleted vars, 0 deleted constraints, 0 added constraints, 1
>> tightened bounds, 0 added holes, 0 changed sides, 0 changed
>> coefficients
>> 0 implications, 0 cliques
>> presolved problem has 15 variables (0 bin, 0 int, 0 impl, 15 cont) and
>> 15 constraints
>> 15 constraints of type <quadratic>
>> Presolving Time: 0.00
>>
>> time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons
>> |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
>> 0.0s| 1 | 0 | 10 | - | 234k| 0 | 0 | 15 | 15 |
>> 15 | 16 | 0 | 0 | 0 | 8.042945e+02 | -- | Inf
>>
>>
>> ******************************************************************************
>> This program contains Ipopt, a library for large-scale nonlinear
>> optimization.
>> Ipopt is released as open source code under the Eclipse Public License
>> (EPL).
>> For more information visit http://projects.coin-or.org/Ipopt
>>
>> ******************************************************************************
>>
>> NOTE: You are using Ipopt by default with the MUMPS linear solver.
>> Other linear solvers might be more efficient (see Ipopt
>> documentation).
>>
>>
>> q 0.0s| 1 | 0 | 10 | - | 241k| 0 | 0 | 15 | 15 |
>> 15 | 16 | 0 | 0 | 0 | 8.042945e+02 | 4.927075e+02 | 63.24%
>> 0.0s| 1 | 0 | 16 | - | 244k| 0 | 0 | 15 | 15 |
>> 15 | 20 | 4 | 0 | 0 | 7.110502e+02 | 4.927075e+02 | 44.31%
>> 0.0s| 1 | 0 | 24 | - | 247k| 0 | 0 | 15 | 15 |
>> 15 | 24 | 8 | 0 | 0 | 6.747186e+02 | 4.927075e+02 | 36.94%
>> 0.0s| 1 | 0 | 30 | - | 250k| 0 | 0 | 15 | 15 |
>> 15 | 28 | 12 | 0 | 0 | 6.545543e+02 | 4.927075e+02 | 32.85%
>>
>>
>>
>>
>> Best regards,
>>
>> Ramon.
>>
>> On 23 February 2014 20:37, Stefan Vigerske <stefan at math.hu-berlin.de>
>> wrote:
>>>
>>> Hi,
>>>
>>>
>>> On 02/23/2014 04:50 PM, Ramón Casero Cañas wrote:
>>>>
>>>>
>>>> Thanks for your reply, Giacomo, but isn't lpopt a subsolver for qpopt,
>>>> only for QP with linear constraints, as it says here?
>>>>
>>>> http://tomopt.com/docs/qpopt1-0.pdf
>>>>
>>>> My problem has quadratic and cubic constraints.
>>>
>>>
>>>
>>> He was talking about Ipopt (https://projects.coin-or.org/Ipopt). For your
>>> instances, it would give you local optimal solution.
>>> You probably can just try out Ipopt via the OPTI toolbox.
>>>
>>> For free input formats to SCIP, it's indeed PIP, ZIMPL, and OSiL that
>>> would
>>> be suitable for you. If you want to input model instances, then PIP may
>>> be
>>> the way to go (http://polip.zib.de/pipformat.php). It's very similar to
>>> the
>>> .lp format. If you want to do modeling, then ZIMPL may be the way to go.
>>> In case of polynomial objective/constraints, it should not matter for the
>>> solution algorithm whether you input via PIP or ZIMPL (or OSiL).
>>>
>>> Stefan
>>>
>>>
>>>
>>>>
>>>>
>>>>
>>>>
>>>> On 23 February 2014 14:29, Giacomo Nannicini <giacomo.n at gmail.com>
>>>> wrote:
>>>>>
>>>>>
>>>>> If all of your variables are continuous, a nonlinear solver is most
>>>>> likely the way to go.
>>>>> For example Ipopt. It is open-source and has a Matlab interface.
>>>>>
>>>>> The format in which you describe your problem should not matter, as
>>>>> long as you give exactly the same description.
>>>>>
>>>>> Cheers
>>>>>
>>>>> Giacomo
>>>>>
>>>>> On Sun, Feb 23, 2014 at 9:28 PM, Ramón Casero Cañas <rcasero at gmail.com>
>>>>> wrote:
>>>>>>
>>>>>>
>>>>>> Replying a bit to myself, if I understand this correctly, I need a
>>>>>> language for a mixed-integer program (as my variables are continuous).
>>>>>>
>>>>>> http://scip.zib.de/doc-3.0.2/html/group__FILEREADERS.shtml
>>>>>>
>>>>>> Of these, the only two that from their description above seem capable
>>>>>> of cubic constraints are OSiL, PIP and ZPL.
>>>>>>
>>>>>> As my problem's objective function and constraints are polynomial
>>>>>> (quadratic and cubic, respectively), the simplest option seems to be
>>>>>> the PIP format.
>>>>>>
>>>>>> http://polip.zib.de/pipformat.php
>>>>>>
>>>>>> However, will the language format choice affect the performance of the
>>>>>> SCIP solver, or it doesn't matter whether I formulate my problem in
>>>>>> PIP format vs. e.g. OSiL format?
>>>>>>
>>>>>> Best regards,
>>>>>>
>>>>>> Ramon.
>>>>>>
>>>>>> On 23 February 2014 00:28, Ramón Casero Cañas <rcasero at gmail.com>
>>>>>> wrote:
>>>>>>>
>>>>>>>
>>>>>>> Dear all,
>>>>>>>
>>>>>>> After playing with SCIP indirectly through the otherwise very nice
>>>>>>> Matlab OptiToolbox, I'm struggling with what could be a bug and I
>>>>>>> cannot introduce cubic constraints, so I'm looking into using SCIP
>>>>>>> directly. This way, I could also use it from linux, and tweak
>>>>>>> parameters as Stefan Vigerske recommended and I haven't been able to
>>>>>>> do yet.
>>>>>>>
>>>>>>> I see in the documentation that SCIP accepts many file formats.
>>>>>>>
>>>>>>> http://scip.zib.de/doc-3.0.2/html/group__FILEREADERS.shtml
>>>>>>>
>>>>>>> This field is quite new for me, and I'd like to ask for advice on
>>>>>>> what
>>>>>>> file format would be more convenient / easier to learn in order to
>>>>>>> code a problem that is a quadratic program (objective function x^T *
>>>>>>> H
>>>>>>> * x + b^T * x) with multiple quadratic and cubic constraints.
>>>>>>>
>>>>>>> Best regards,
>>>>>>>
>>>>>>> Ramon.
>>>>>>>
>>>>>>> --
>>>>>>> Dr. Ramón Casero Cañas
>>>>>>>
>>>>>>> Oxford e-Research Centre (OeRC)
>>>>>>> University of Oxford
>>>>>>> 7 Keble Rd
>>>>>>> Oxford OX1 3QG
>>>>>>>
>>>>>>> tlf +44 (0) 1865 610739
>>>>>>> web http://www.cs.ox.ac.uk/people/Ramon.CaseroCanas
>>>>>>> photos http://www.flickr.com/photos/rcasero/
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>> --
>>>>>> Dr. Ramón Casero Cañas
>>>>>>
>>>>>> Oxford e-Research Centre (OeRC)
>>>>>> University of Oxford
>>>>>> 7 Keble Rd
>>>>>> Oxford OX1 3QG
>>>>>>
>>>>>> tlf +44 (0) 1865 610739
>>>>>> web http://www.cs.ox.ac.uk/people/Ramon.CaseroCanas
>>>>>> photos http://www.flickr.com/photos/rcasero/
>>>>>>
>>>>>> _______________________________________________
>>>>>> Scip mailing list
>>>>>> Scip at zib.de
>>>>>> http://listserv.zib.de/mailman/listinfo/scip
>>>>
>>>>
>>>>
>>>>
>>>>
>>>
>>
>>
>>
>
--
Dr. Ramón Casero Cañas
Oxford e-Research Centre (OeRC)
University of Oxford
7 Keble Rd
Oxford OX1 3QG
tlf +44 (0) 1865 610739
web http://www.cs.ox.ac.uk/people/Ramon.CaseroCanas
photos http://www.flickr.com/photos/rcasero/
More information about the Scip
mailing list