MathGroup Archive 1999

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: Importing 16-bit TIFF files with 4.0
  • Next by Date: Re: Importing 16-bit TIFF files with 4.0
  • Previous by thread: Re: Re: Re: List-Selection
  • Next by thread: Re: Mathematica programming language