Mathematica 9 is now available

Wolfram Library Archive


Courseware Demos MathSource Technical Notes
All Collections Articles Books Conference Proceedings
Title Downloads

Making Change and Finding Repfigits: Balancing a Knapsack
Author

Daniel Lichtblau
Organization: Wolfram Research, Inc.
Conference

ICMS 2006
Conference location

Castro Urdiales, Spain
Description

This work was presented at ICMS, Castro Urdiales, Spain, September 2, 2006. The article is a longer version, containing a code appendix. As there have been some code refinements since then, I include the better Mathematica code and tests in a file KeithNumbers.nb

Abstract:

We will discuss knapsack problems that arise in certain computational number theory settings. A common theme is that the search space for the standard real relaxation is large; in a sense this translates to a poor choice of variables. Lattice reduction methods have been developed in the past few years to improve handling of such problems. We show explicitly how they may be applied to computation of Frobenius instances, Keith numbers (also called "repfigits"), and as a first step in computation of Frobenius numbers.
Subjects

*Mathematics > Algebra > Linear Algebra
*Mathematics > Number Theory
Keywords

integer linear programming, knapsack problems, Keith numbers, Frobenius instance solving, postage-stamp problem, change-making problem, lattice reduction
URL

http://www.icms2006.unican.es
Downloads Download Wolfram CDF Player

Download
ICMS2006_lattice_ilp_talk.pdf (95.3 KB) - PDF Document
Download
lattice_ilp.pdf (94.7 KB) - PDF Document
Download
ICMS2006_lattice_ilp_talk.nb (342 KB) - Mathematica Notebook
Download
KeithNumbers.nb (236.5 KB) - Mathematica Notebook
Download
lattice_ilp.nb (252 KB) - Mathematica Notebook