|
|
|
|
|
|
 |
 |
|
Frobenius Numbers by Lattice Points: Applications of Integer Optimization to a Classic Computational Problem
|
|
|
|
|
|
| Organization: | Macalester College |
| Organization: | Wolfram Research, Inc. |
|
|
|
|
|
|
2006 Wolfram Technology Conference
|
|
|
|
|
|
Champaign IL
|
|
|
|
|
|
The Frobenius number a of a finite set of positive integers is the least integer that is not representable as a nonnegative combination of entries in a. For example, Chicken McNuggets® come in serving sizes of 6, 9, and 20. One cannot buy 43 McNuggets, but any larger target is representable. Thus a. Finding the Frobenius number, and solving Frobenius instances (finding a solution to a in nonnegative integers a) are closely related to more general problems in integer optimization. For example, minimizing a subject to the constraints that this quantity is nonnegative and each entry of a is nonnegative will solve the instance problem, since the target a is representable iff 0 is the minimum.
In this talk we will show how a study of a certain lattice of integer vectors leads to a geometric object—the fundamental domain—that encodes enough information to find the Frobenius number. Getting this information about the domain requires developing several algorithms, many of which have had an impact on some of Mathematica’s kernel functions, such as a and a. Letting a be the number of integers in a, we can find a (with rare exceptions) when a, but with no restriction on the size of the entries in a. The algorithm seems to have complexity that, when a is fixed, is close to quadratic on average. The previous best algorithm for this problem was polynomial-time in the input size, but with polynomial degree a. Here is an example with a (in Mathematica 5.2). Needs["NumberTheory`"] A = {10000000001, 20100000000, 30000000017, 40000000039, 50999000101}; g = FrobeniusF[A] 529710001010385 FrobeniusInstance[A, g + 100] {122, 900, 3, 8, 10000} The main points are best illustrated when a. Letting a be the integers a, there is a natural map a given by a. The kernel of a is the lattice a consisting of triples a such that a is divisible by a. The classic relationship a raises the question of finding a geometric form for a; by this we mean choosing a representative vector for each equivalence class. We do this in a natural way, and call the resulting set of a vectors , for fundamental domain; it sets in the first octant and includes the origin. There is then a tiling of a induced by translating copies of by vectors in a. Here is picture of the domain—the gray cubes—when a. The trick then is to capture concisely the geometric structure of the domain, so that it can be easily described even when it has a entries. We do this by getting the elbows of , by which we mean vectors a that are not in , but such that subtracting 1 in any nonzero coordinate yields a point that is in ; these are the nine tetrahedra in the diagram. It follows that is obtained by deleting the cones defined by all the elbows. Having the elbows in hand allows us to get the corners of , and one of the corners yields the Frobenius number of a.
Our algorithm for doing this is complicated, with many steps. But it appears that, when n is fixed, the average complexity is close to quadratic. Other consequences of our work are a very fast algorithm when a (it can handle million-digit inputs) and some new theoretical results about the Frobenius number of special sequences. An important part of our algorithm involves solving linear Diophantine equations to give important information about the domain . Such problems are also of importance in their own right, with applications in computational number theory, operations research, and elsewhere. A particular application, closely related to the problem at hand, is solving a specific Frobenius instance: Given our set a and a target value a, we find a nonnegative a that solves a. We will discuss how this is done efficiently in Mathematica, and mention how similar Diophantine equations relate to finding Frobenius numbers.
|
|
|
|
|
|
|
|
|
|
|
|
Frobenius numbers, integer linear programming, lattices
|
|
|
 |
|
|
| Frobenius Numbers.nb (3.3 MB) - Mathematica Notebook [for Mathematica 5.2] | | TechConf2006_ilp_talk_v5.nb (935.4 KB) - Mathematica Notebook [for Mathematica 5.2] |
|
|
|
|
|
|
|
| | | | | |
|
For the newest resources, visit Wolfram Repositories and Archives »
