Top
Back: Buchberger algorithm
Forward: Relevant References
FastBack: Toric ideals
FastForward: Non-commutative algebra
Up: Toric ideals and integer programming
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

C.6.4 Integer programming

  • (1) Compute the toric ideal I(A) using one of the algorithms in the previous section.
  • (2) Compute the reduced Groebner basis G(c) of I(A) w.r.t. .
  • (3) Reduce modulo G(c) using the Hironaka division algorithm. If the result of this reduction is , then is an optimal solution of the given instance.

If no initial solution is known, we are nevertheless able to solve the problem with similar techniques. For this purpose we replace our instance by an extended instance with the matrix used in the Conti-Traverso algorithm. Indeed, the Conti-Traverso algorithm offers the possibility to verify solvability of a given instance and to find an initial solution in the case of existence (but none of the other algorithms does!). Details can be found in see [CoTr91] and see [The99].

An implementation of the above algorithm and some examples can be found in intprog_lib.

In general, classical methods for solving IP instances like Branch-and-Bound methods seem to be faster than the methods using toric ideals. But the latter have one great advantage: If one wants to solve various instances that differ only by the vector , one has to perform steps (1) and (2) above only once. As the running time of step (3) is very short, solving all the instances is not much harder than solving one single instance.

For a detailed discussion see see [The99].


Top Back: Buchberger algorithm Forward: Relevant References FastBack: Toric ideals FastForward: Non-commutative algebra Up: Toric ideals and integer programming Top: Singular Manual Contents: Table of Contents Index: Index About: About this document
            User manual for Singular version 3-1-6, Dec 2012, generated by texi2html.