Re: Re: List-Selection

*To*: mathgroup at smc.vnet.net*Subject*: [mg20241] Re: [mg20060] Re: [mg20021] List-Selection*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Fri, 8 Oct 1999 18:30:17 -0400*Organization*: Wolfram Research, Inc.*References*: <7t8msm$m8n$1@dragonfly.wolfram.com>*Sender*: owner-wri-mathgroup at wolfram.com

Andrzej Kozlowski wrote: > > This is very interesting. Its well outside my area of expertise but one > thing has intrigued me particularly. Mathematica indeed has no > IntegerProgramming function. However, I remember from reading Cox, Little > and O'Shea's "Using Algebraic Geometry" that Groebner basis can be used to > do just that. I think they say that the built in Groebner basis in > Mathematica is not flexible enough to do that, but I think they were only > familiar with Mathematica 2. The main point seemed to be the ability to > specify suitably weighted monomial orders, which I think can be done in > Mathematica 4.0. Can this really be done? Could we hope to solve this > problem using Groebner basis? I don't think I could try to answer this > without a great deal of work but I think this should be something Daniel > Lichtblau could tell us. > -- > Andrzej Kozlowski > Toyama International University > JAPAN > http://sigma.tuins.ac.jp > http://eri2.tuins.ac.jp > > ... One can use Groebner bases to do this sort of integer programming, although to be honest I do not recall all the details. I still have not read that text though I understand it is quite good. David Cox at least was reasonably familiar with version 3 of Mathematica. He had previously given some useful input into the redesign back when I was starting the project, maybe early 1993 or so. As a minor issue, the comment regarding term orders on p.373 of the book (where they discuss Groebner bases and integer programming) is not really correct. One can specify the desired term order via a weight matrix. To this end, one would need to write a small module to compute the weight matrix from the specifications given on p.367. My suspicion is that any attempt to handle serious integer programming problems that way will mire down in the GroebnerBasis internals. I also believe related but faster methods have been developed that are specialized to the types of polynomial systems that arise in this technology (toric ideals). Actually we have a new kernel person here, Birk Huber, who knows alot more about this than I do (he's out of town today, hence cannot defend himself from being volunteered). Daniel Lichtblau Wolfram Research