Solving quadratic inequalities with Mixed Ineger Linear Programming

[Ruslan Kiianchuk]

Is it possible to solve quadratic inequalities with MILP? Trying to do so I get an error:

sage: p = MixedIntegerLinearProgram(maximization=False, solver='GLPK')
sage: x = p.new_variable(integer=False)
sage: eq = x[5] * x[0] + x[6] * x[1] + x[7] * x[2] + x[8] * x[3] + x[9] * x[4]; eq
x_1 x_0 +x_3 x_2 +x_5 x_4 +x_7 x_6 +x_9 x_8

sage: p.add_constraint(eq <= 2)
Traceback (most recent call last): File "<stdin>", line 1, in <module> File "_sage_input_160.py", line 10, in <module> exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("cC5hZGRfY29uc3RyYWludChlcSA8PSAyKQ=="),globals())+"\\n"); execfile(os.path.abspath("___code___.py")) File "", line 1, in <module> File "/tmp/tmpAdb8Fi/___code___.py", line 3, in <module> exec compile(u'p.add_constraint(eq <= _sage_const_2 ) File "", line 1, in <module> File "mip.pyx", line 1063, in sage.numerical.mip.MixedIntegerLinearProgram.add_constraint (sage/numerical/mip.c:6240) File "mip.pyx", line 1054, in sage.numerical.mip.MixedIntegerLinearProgram.add_constraint (sage/numerical/mip.c:6123) File "glpk_backend.pyx", line 411, in sage.numerical.backends.glpk_backend.GLPKBackend.add_linear_constraint (sage/numerical/backends/glpk_backend.cpp:3722) AttributeError: LinearFunction instance has no attribute '__float__'

[Nathann Cohen]

Well, no it is not. We would need an interface with quadratic solvers to do that, and all we have now are *linear* solvers. At least through the MILP class.

Nathann

[Ruslan Kiyanchuk]

Thanks. Can you recommend any good tool other than Sage (since it doesn't have such interfaces yet) that would handle quadratic inequalities?

On Wed, May 30, 2012 at 3:32 PM, Nathann Cohen <nathan...@gmail.com> wrote:

Well, no it is not. We would need an interface with quadratic solvers to do that, and all we have now are *linear* solvers. At least through the MILP class.

Nathann

--
To post to this group, send email to sage-s...@googlegroups.com
To unsubscribe from this group, send email to sage-support...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-support
URL: http://www.sagemath.org

--
Sincerely, Ruslan Kiyanchuk

[Nathann Cohen]

> Thanks. Can you recommend any good tool other than Sage (since it doesn't
> have such interfaces yet) that would handle quadratic inequalities?

Well, that's a problem I would be very glad to be able to answer
myself.... But it highly depends on the characteristics of your
equations... CPLEX can solve some instances (it is proprietary,
though) depending on the matrix of constraints, but for general
inequalities I have the same problem you have :-/

Nathann

[Dima Pasechnik]

On 2012-05-30, Ruslan Kiianchuk <zore...@gmail.com> wrote:
> ------=_Part_129_12472377.1338370192511
> Content-Type: text/plain; charset=ISO-8859-1

>
> Is it possible to solve quadratic inequalities with MILP? Trying to do so I
> get an error:

I guess you need to explain what do you mean by "solving".
The solution set is in general infinite.
Do you mean "checking for existence of solutions"?
Or perhaps "finding a representative of each connected component"?
Or "finiding a parametric representation of the solutions"?

[Martin Albrecht]

You can try SCIP which is a constraint integer programming solver and supports
quadratic constraints. I started a Sage interface here:

http://trac.sagemath.org/sage_trac/ticket/10879

From the ticket description:

"""
"SCIP is currently one of the fastest non-commercial mixed integer programming
(MIP) solvers. It is also a framework for Constraint Integer Programming and
branch-cut-and-price. It allows total control of the solution process and the
access of detailed information down to the guts of the solver." --
http://scip.zib.de/

Features interesting to Sage:

- SCIP is pretty fast for Mixed Integer Programming
- SCIP is a Constraint Integer Programming solver and allows non-linear
constraints
- SCIP's source code is available

However, we don't have the right to redistribute the SCIP source code. Thus,
the attached SPKG is empty except for the spkg-install script etc.

To build a SCIP for Sage do:

- download the ZIB Optmisation Suite from
http://zibopt.zib.de/download.php?fname=ziboptsuite-2.0.1.tgz
- place the files scip-2.0.1.tgz and soplex-1.5.0.tgz in the src/ subdirectory
of the attached SPKG
- install the SPKG
- apply the attached patch and sage -b

KNOWN ISSUES

- Sage crashes when SCIP variables are printed with SIGSEGV on OSX. It works
fine under Linux.

- the following doctests fail
sage -t -long -force_lib
devel/sage/doc/en/thematic_tutorials/linear_programming.rst # 1 doctests
failed
sage -t -long -force_lib devel/sage/sage/graphs/digraph.py # 1 doctests
failed
sage -t -long -force_lib devel/sage/sage/numerical/mip.pyx # 3 doctests
failed

- printing of quadratic constraints does not work yet.
"""

The patch probably also bitrotted a bit by now. But I'd be very happy to see
it completed, so I'm happy to help anyone who'd attempt to finish it. Also,
the SCIP developers are happy to help out if we have questions etc.

Cheers,
Martin

--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF
_www: http://martinralbrecht.wordpress.com/
_jab: martinr...@jabber.ccc.de

[Ruslan Kiyanchuk]

You can try SCIP which is a constraint integer programming solver and supports
quadratic constraints. I started a Sage interface here:

Thank you, will try it. Couldn't figure out if the interface to Sage actually exists.

I guess you need to explain what do you mean by "solving".
The solution set is in general infinite.
Do you mean "checking for existence of solutions"?
Or perhaps "finding a representative of each connected component"?
Or "finiding a parametric representation of the solutions"?

The solution set isn't infinite if integers are considered. I know the code sample says integer=False, but I've just tried to get rid of the error :) Checking for existence of solutions might help as well since solving the inequalities is used for generating codes with good correlation properties. But getting the exact variables values satisfying the inequalities is the primary goal.

--
Sincerely, Ruslan Kiyanchuk

[Dima Pasechnik]

On Thursday, 31 May 2012 23:45:36 UTC+2, Ruslan Kiyanchuk wrote:

You can try SCIP which is a constraint integer programming solver and supports
quadratic constraints. I started a Sage interface here:

Thank you, will try it. Couldn't figure out if the interface to Sage actually exists.

I guess you need to explain what do you mean by "solving".
The solution set is in general infinite.
Do you mean "checking for existence of solutions"?
Or perhaps "finding a representative of each connected component"?
Or "finiding a parametric representation of the solutions"?

The solution set isn't infinite if integers are considered. 

that's only if you impose some bound on the sizes of integers you want.

[Slumberland]

I am wondering about this one actually:

On Wednesday, May 30, 2012 6:24:33 AM UTC-7, Dima Pasechnik wrote:

Or "finiding a parametric representation of the solutions"? 

This is (one of )   a (large number) of problems I have been wondering about for awhile.

And maybe finding a representative, but I haven't decided yet that I want to peek at answers to that one, so say I just wanted to know about making a parametric representation.

I am happy to grant in advance arbitrary constraints which illustrate the approach.  For example, lacking any real idea how to handle quadratic inequalities, I will do things like clamp them to equality and work out the system that way, then go back through and... uh... undo the latches on the inequalities one at a time.

But.  um.  So far I have only done that when I can reliably linearize, which isn't really answering the question.

This strikes me as a heck of a tricky problem.

Oh.  is it a lie and write, say,  x{i}x{j} as X{ij}, and pretend to linearize that way?  Does this go anywhere?  Again, I failed to find a general parameterization which was more than an aesthetic change.  Unless, of course, I had enough terms that the pairwise system could be directly solved, and then linearized.

I apologize if these questions are naive.  I'm having a hard time getting the shape of this problem into my head.

[Slumberland]

Is there any reason we shouldn't try to define a workflow in SAGE to tackle this?  I'm making this up, but I think the principal problem is that, for practical evaluation, there really isn't such a thing a general system of quadratic inequalities.  By which I mean, the particular considerations are the heart of the matter.  Suppose we said, "Okay, there is no direct solver, but how can we use SAGE to advance us as far as possible toward a useful representation of such a system?"

I tumbled this problem around in my head for the last day, and I keep thinking that the particularities of the constraints cannot --and should not-- be avoided.  That, as a general rule, seeking a direct solver might be a bit of a misunderstanding.  Like, we need to define our constraints more carefully. Are we sure there are no differential relationships, first of all!

@Nathann/Ruslan -- would it be useful  for either of you if we worked out a multipage Worksheet collecting relevant methods and providing some basic ways to get from one representation to another?

For example, I think whether or not there is any descriptive meaning, for the particular system in question, to considering the constraints as representing the geometric boundaries of conics, and the "solution" to be a multidimensional region of unions and intersections, could be a useful question.  It strikes me there is not one way to parameterize, and it really is going to depend on how we want to represent the relationships among the quadratic terms.  For example, the list Ruslan started with, pairwise components

x{a}x{b}  + x{d}x{e} + ....

... if the other equations continue in this way, does not necessarily represent a unique arrangement of generalized quadratic forms, even if the total system has a finite solution set.

Or does it?  (Afternoon musings not to be trusted!)

I can't get over feeling like the system is simply not adequately described, and that a program which solves it for us is not really tackling the problem. We are at the whim of the form of its output.

But, obviously I could choose a rational parameterization.  Or unhook the quadratics into linear pairs (like Ruslan did).

Is there really one way to solve this?

Can we build a useful tool for handling these problems, in a short period of time, without trying to "crack" the solution to general solution spaces?

And for the love of God tell me if this is ridiculous and naive.  I have no frame of reference for how other people think about math.  I have no one to check with but me, to see if I've gone crazy.

 

[Slumberland]

No.

There's an answer to this question, and the computer is the wrong way to do it.

Let me lay out some assumptions and we can all have a good laugh about it later. Remember when you said "I have the answer" and instead you had drew a picture of a pony? And I'll say no, it was a unicorn.  But for now let me pretend like I know what I'm talking about.  I need a working idea of the problem.

1) The computer is the wrong way to go about it.

We have brains and computers don't.  I want a solution to a quadratic system.  I want a quadratic solution.  The assumption that, say 'an arrangement of terms that will 'do' for a first-order system is a well-formed question' is unfounded.  Perhaps, obviously untrue.

2) I need (or would like) a finite number of rational points to define a solution space by a new, more elegantly chosen set of quadratic inequalities. Namely... ellipses.

3) I have to make a series of choices about the solution space and the terms before me.  They can be arranged arbitrarily, in the algebra, but that does not necessarily describe the system in question.  I need to investigate what I mean by the pairings of terms.  Are they really just indistinguishable pairs-among-equals?  If this is really true then I should just say to hell with it and wrap each distinct pair up as a separate variable, and write it as a linear system in n/2 independent variables.  

4) But suppose we  don't really believe it's just a mess of linear equations that accidentally got tangled up.  Say I want to keep the meaning of the quadratic form, but I do not know enough about the system to preference any one arrangement of the terms over another.  

5) this is a convenient way to "define" the general case of the problem.  It's a bit of a lie.   I could fool myself  into thinking I had the THE correct answer for a particular problem when in reality what I mean is that I have used, say, the minimim number of rational points necessary to define the solution space.  There is no reason to assume such a minimization is meaningful in any particular case.  Brushing that aside, however, and embracing abstraction, 

6) I want to throw lassos around the minimum elements of the solution space.    I want to rewrite the system without "solving" the quadratics, but by first arranging it into a series of ellipses which I will say define different overlapping regions.  Then I have bounded the solution space in the most flexible and economic geometric way.  I think.  I mean.  It seems like it.  The ellipse seems like a magical little tool.  It defines a fully bounded 2-d section of space, and simultaneously describes the relative scale of its geometric proportion within the plane chosen.

  Then I go hunting for how to slide those ellipses along the cones, among the various dimensions, until O can get them all to share points.  The solution can be unlatched.  We have to hunt it, and make it give its cookies away.

Now, suppose we have enough dimensions that there is no necessary way to do this?  That fact, by itself contributes even more descriptive information about our system.  Information crucial to understanding its structure, and which we will lack, holding a computer printout to a system of equations.  I am not sure how to proceed from here but in the worst-case scenario maybe we could define a klunky, parametric form that forces us to make some assumptions about how the terms fit together, and start hunting for asymptotes.

??

I don't think I'll make it that far before having to revise everything I just wrote.

I need to figure out just how quickly the number of possible conic arrangements expands as the system increases in size.  I am making the assumption that it will always be possible to sort out possible asymptotes, brute force some boundary points if we have to, but there is no necessary reason for that to be true.

In any case, I think the human manipulation of the terms into a solvable form is really what this is about.

Thoughts?

And. please. Seriously.  I need to know if I'm reasoning like a child.

[Slumberland]

Corrections:

1)I need all the conic sections if I'm going to use them at all. 

xy        +  zw  +   uv   >=    4

   xz -zv           -     uw  <= 12

....etc

could be arbitrarily ... unnatural... to express as ellipses.  Not sure why I thought I could get around that.

2) rational points is just a test.  Not sure if it provides useful information in a general context.  Unless I choose a rational parameterization.

3) the sign is very important to me.  Which boundary conditions most immediately limit the solution space?

4) "sliding along cones" is pretend.  The operation has to be a multidimensional transform, otherwise the problem is already solved and there is no "sliding" to do.  I have a mental picture of how I want this to work but I am no longer convinced it is a logical one.

5) not sure where n/2 came from.    n(n-1)/2

Using the Who's Going to Stop Me Theorem, I can always write the system as a series of linear equations in n(n-1)/2 unknowns.

That's not what I want. The vectors giving my unknown parameters is a collection of indivdiual terms factored out of the desired form.  I lock myself out of a quadratic solution system.  But it might be a useful test?

I'll try some things in SAGE, figure out how to define some parts of the process; cases.   But if no one else is interested (or if my maths aren't strong enough for you) I'll leave it at that for now.  Not really a priority.