Re: [sage-support] Re: Solving quadratic inequalities with Mixed Ineger Linear Programming
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. -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
Re: [sage-support] Re: Solving quadratic inequalities with Mixed Ineger Linear Programming
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. -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
[sage-support] Re: Solving quadratic inequalities with Mixed Ineger Linear Programming
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.
--
To post to this group, send email to sage-support@googlegroups.com
To unsubscribe from this group, send email to
sage-support+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/sage-support
URL: http://www.sagemath.org
Re: Re: [sage-support] Re: Solving quadratic inequalities with Mixed Ineger Linear Programming
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. On Wednesday 30 May 2012, Ruslan Kiyanchuk wrote: 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 nathann.co...@gmail.comwrote: 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-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org Cheers, Martin -- name: Martin Albrecht _pgp: http://pgp.mit.edu:11371/pks/lookup?op=getsearch=0x8EF0DC99 _otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF _www: http://martinralbrecht.wordpress.com/ _jab: martinralbre...@jabber.ccc.de -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
Re: Re: [sage-support] Re: Solving quadratic inequalities with Mixed Ineger Linear Programming
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 -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
Re: Re: [sage-support] Re: Solving quadratic inequalities with Mixed Ineger Linear Programming
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. 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 -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
[sage-support] Re: Solving quadratic inequalities with Mixed Ineger Linear Programming
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-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
Re: [sage-support] Re: Solving quadratic inequalities with Mixed Ineger Linear Programming
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 nathann.co...@gmail.comwrote: 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-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org -- Sincerely, Ruslan Kiyanchuk -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
Re: [sage-support] Re: Solving quadratic inequalities with Mixed Ineger Linear Programming
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 -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
[sage-support] Re: Solving quadratic inequalities with Mixed Ineger Linear Programming
On 2012-05-30, Ruslan Kiianchuk zores...@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? 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 -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
