[Scip] Recommended language for QP with quadratic and cubic constraints

Stefan Vigerske stefan at math.hu-berlin.de
Mon Feb 24 15:01:06 CET 2014 

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
>>>
>>>
>>>
>>>
>>
>
>
>

More information about the Scip mailing list