Integer Linear Programming

[Bjarke Hammersholt Roune]

Hi,

Can I solve integer linear programs in Macaulay 2? Searching the
documentation for "integer program" gave zero hits.

Cheers
Bjarke

[Thomas Kahle]

Bjarke Hammersholt Roune wrote:
> Hi,
>
> Can I solve integer linear programs in Macaulay 2? Searching the
> documentation for "integer program" gave zero hits.

Hi, you could try the function 'zsolve' that comes with 4ti2
(www.4ti2.de). Unfortunately the M2 Package that wraps 4ti2 does not
cover this function, a future version really should !

Cheers
Thomas

>
> Cheers
> Bjarke
>
> --~--~---------~--~----~------------~-------~--~----~
> You received this message because you are subscribed to the Google Groups "Macaulay2" group.
> To post to this group, send email to maca...@googlegroups.com
> To unsubscribe from this group, send email to macaulay2+...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/macaulay2?hl=en
> -~----------~----~----~----~------~----~------~--~---

--
Thomas Kahle

The fundamental theorem of algebra is open source. Like any other
mathematical theorem it can be applied free of charge and everybody
has access to its proof and can convince himself how it works. Why
should software be any different?

[Bjarke Hammersholt Roune]

Thanks for the suggestion. I'm trying to stay within M2 for this, and
I'm not looking for something efficient (yet), so I may end up
implementing some grotesquely inefficient ILP solver in M2, depending
on how much trouble that turns out to be.

On that note, can I solve plain old linear programs without integer
constraints in M2?

Cheers
Bjarke

On Apr 23, 8:18 pm, Thomas Kahle <tom...@gmx.de> wrote:
> Bjarke Hammersholt Roune wrote:
> > Hi,
>
> > Can I solve integer linear programs in Macaulay 2? Searching the
> > documentation for "integer program" gave zero hits.
>
> Hi, you could try the function 'zsolve' that comes with 4ti2
> (www.4ti2.de). Unfortunately the M2 Package that wraps 4ti2 does not
> cover this function, a future version really should !
>
> Cheers
> Thomas
>
>
>
> > Cheers
> > Bjarke
>
> > >

> --
> Thomas Kahle
>
> The fundamental theorem of algebra is open source. Like any other
> mathematical theorem it can be applied free of charge and everybody
> has access to its proof and can convince himself how it works. Why
> should software be any different?
>

>  signature.asc
> < 1KViewDownload

[Thomas Kahle]

Bjarke Hammersholt Roune wrote:
> Thanks for the suggestion. I'm trying to stay within M2 for this, and
> I'm not looking for something efficient (yet), so I may end up
> implementing some grotesquely inefficient ILP solver in M2, depending
> on how much trouble that turns out to be.
>
> On that note, can I solve plain old linear programs without integer
> constraints in M2?

Sorry for advertising another program again :)
There is a preliminary interface to polymake (which can solve linear
programs). However, it seems very preliminary :
http://www.math.uiuc.edu/Macaulay2/doc/Macaulay2-1.2/share/doc/Macaulay2/Polymake/html/

But, I'd be also interested what is the state of the art in
{integer,linear} programming in M2?

cheers
Thomas

>
> Cheers
> Bjarke
>
> On Apr 23, 8:18 pm, Thomas Kahle <tom...@gmx.de> wrote:
>> Bjarke Hammersholt Roune wrote:
>>> Hi,
>>> Can I solve integer linear programs in Macaulay 2? Searching the
>>> documentation for "integer program" gave zero hits.
>> Hi, you could try the function 'zsolve' that comes with 4ti2
>> (www.4ti2.de). Unfortunately the M2 Package that wraps 4ti2 does not
>> cover this function, a future version really should !
>>
>> Cheers
>> Thomas
>>
>>
>>
>>> Cheers
>>> Bjarke
>> --
>> Thomas Kahle
>>
>> The fundamental theorem of algebra is open source. Like any other
>> mathematical theorem it can be applied free of charge and everybody
>> has access to its proof and can convince himself how it works. Why
>> should software be any different?
>>
>> signature.asc
>> < 1KViewDownload
>

> --~--~---------~--~----~------------~-------~--~----~
> You received this message because you are subscribed to the Google Groups "Macaulay2" group.
> To post to this group, send email to maca...@googlegroups.com
> To unsubscribe from this group, send email to macaulay2+...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/macaulay2?hl=en
> -~----------~----~----~----~------~----~------~--~---

[dec...@math.uni-sb.de]

Singular has an implementation of various Groebner
basis algoritms for ILP which you might want to check.
Regards, Wolfram Decker

[Wolfram Decker]

Singular has an implementation of various Groebner
basis algoritms for ILP which you might want to check.
Regards, Wolfram Decker

On 25 Apr., 14:23, Thomas Kahle <tom...@gmx.de> wrote:
> Bjarke Hammersholt Roune wrote:
> > Thanks for the suggestion. I'm trying to stay within M2 for this, and
> > I'm not looking for something efficient (yet), so I may end up
> > implementing some grotesquely inefficient ILP solver in M2, depending
> > on how much trouble that turns out to be.
>
> > On that note, can I solve plain old linear programs without integer
> > constraints in M2?
>
> Sorry for advertising another program again :)
> There is a preliminary interface to polymake (which can solve linear

> programs). However, it seems very preliminary :http://www.math.uiuc.edu/Macaulay2/doc/Macaulay2-1.2/share/doc/Macaul...

> < 1 KBAnzeigenHerunterladen

[Bjarke Hammersholt Roune]

I did end up coding a linear program Simplex algorithm in M2 code,
which I can send to anyone who might be interested. It needs more
sophistication and a bit more testing to be used in something serious.

Cheers
Bjarke

[Thomas Kahle]

-------- Original-Nachricht --------
> Datum: Tue, 26 May 2009 04:19:33 -0700 (PDT)
> Von: Bjarke Hammersholt Roune <bjarke...@gmail.com>
> An: Macaulay2 <maca...@googlegroups.com>
> Betreff: [Macaulay2] Re: Integer Linear Programming

>
> I did end up coding a linear program Simplex algorithm in M2 code,
> which I can send to anyone who might be interested. It needs more
> sophistication and a bit more testing to be used in something serious.

Hi Bjarke,
myself and Edwin O'Shea (cc) might be interested in doing some testing for this. We get our linear programs out of M2 anyways and polymake seems to be horribly broken currently.
Would you share your achievements ?

Thanks
Thomas

>
> Cheers
> Bjarke
>
>

[Bjarke Hammersholt Roune]

Hi Thomas,

I've put the code I've got up at

http://www.broune.com/simplex.m2

It isn't very fast, but I believe it works, and there are some tests
to add some confidence that this is the case.

Cheers
Bjarke

PS. The file also contains some simple code for integer linear
programming, which turned out to be so slow as to be unusable for me.
I've left it in since it has tests too, and it uses the linear
programming code as a sub-algorithm, so that acts as a test of the
linear programming in addition to the direct tests.

On 9 Jul., 00:13, "Thomas Kahle" <tom...@gmx.de> wrote:
> -------- Original-Nachricht --------
>
> > Datum: Tue, 26 May 2009 04:19:33 -0700 (PDT)

> > Von: Bjarke Hammersholt Roune <bjarke.ro...@gmail.com>