0-1 Knapsack

For an introductive description of the 0-1 knapsack problem see  Wolfram and  Wikipedia pages or the freely available book  Knapsack Problems by S.Martello and P.Toth.

The sample code uses METSlib to try to solve the one-dimensional 0-1 knapsack problem with three different algorithms (LS, SA and TS). This algorithms are suboptimal, but Tabu Search in particular can solve very large instances of the problem with values very close to the global optimum using far less memory and time than an exact solution.

In AMPL (and in GNU MathProg) the 0-1 Knapsack problem can be solved with this script.

GLPK supports the GNU MathProg language, which is a subset of the AMPL language.

The  GLPK (GNU Linear Programming Kit) package is intended for solving large-scale linear programming (LP), mixed integer programming (MIP), and other related problems. It is a set of routines written in ANSI C and organized in the form of a callable library.

You can solve knapsack problems with the GLPK solver and the knapsack.mod model.

 .../knapsack/glpk/$ glpsol -m knapsack.mod -d nf500.dat -y nf500.sol

To search and write the globally optimal solution for the nf500.dat problem in the nf500.sol file.

Once you have compiled and installed mestlib and than compiled the knapsack sample you can also search suboptimal solutions with mestlib this way:

../knapsack/$ ./src/search glpk/nf500

That writes some files (nf500-tabu.sol, nf500-tabu.log, nf500-ls.sol, nf500-ls.log, nf500-sa.sol, nf500-sa.log) in the glpk/ folder. This files will contain the tabu search, local search and simulated annealing solutions and logs. You can the use the scripts in the plot/ folder to plot some graphs of the search process.