Knapsack¶
Principles learned¶
Create a generic model that uses data
Read an instance from a file
Write the solution in a file
Problem¶
The knapsack problem is defined as follows: given a set of items, each with a weight and a value, determine a subset of items in such a way that their total weight is less than a given bound and their total value is as large as possible. This problem is hard to solve in theory.
Download the exampleProgram¶
Note that the way to model is exactly the same than in integer programming: for each item, a 0-1 decision variable is defined which is equal to 1 if the item belongs to the knapsack and 0 otherwise.
Knapsack instances involving millions of objects can be tackled using Hexaly Optimizer .
- Execution:
- hexaly knapsack.hxm inFileName=instances/kp_100_1.in [hxTimeLimit=] [solFileName=]
use io;
/* Read instance data */
function input() {
local usage = "Usage: hexaly knapsack.hxm "
+ "inFileName=inputFile [solFileName=outputFile] [hxTimeLimit=timeLimit]";
if (inFileName == nil) throw usage;
local inFile = io.openRead(inFileName);
nbItems = inFile.readInt();
weights[i in 0...nbItems] = inFile.readInt();
prices[i in 0...nbItems] = inFile.readInt();
knapsackBound = inFile.readInt();
}
/* Declare the optimization model */
function model() {
// Decision variables x[i]
x[i in 0...nbItems] <- bool();
// Weight constraint
knapsackWeight <- sum[i in 0...nbItems](weights[i] * x[i]);
constraint knapsackWeight <= knapsackBound;
// Maximize value
knapsackValue <- sum[i in 0...nbItems](prices[i] * x[i]);
maximize knapsackValue;
}
/* Parametrize the solver */
function param() {
if (hxTimeLimit == nil) hxTimeLimit = 20;
}
/* Write the solution in a file */
function output() {
if (solFileName == nil) return;
local solFile = io.openWrite(solFileName);
solFile.println(knapsackValue.value);
for [i in 0...nbItems : x[i].value == 1]
solFile.print(i + " ");
solFile.println();
}
- Execution (Windows)
- set PYTHONPATH=%HX_HOME%\bin\pythonpython knapsack.py instances\kp_100_1.in
- Execution (Linux)
- export PYTHONPATH=/opt/hexaly_13_0/bin/pythonpython knapsack.py instances/kp_100_1.in
import hexaly.optimizer
import sys
if len(sys.argv) < 2:
print("Usage: python knapsack.py inputFile [outputFile] [timeLimit]")
sys.exit(1)
def read_integers(filename):
with open(filename) as f:
return [int(elem) for elem in f.read().split()]
with hexaly.optimizer.HexalyOptimizer() as optimizer:
#
# Read instance data
#
file_it = iter(read_integers(sys.argv[1]))
# Number of items
nb_items = next(file_it)
# Items properties
weights = [next(file_it) for i in range(nb_items)]
values = [next(file_it) for i in range(nb_items)]
# Knapsack bound
knapsack_bound = next(file_it)
#
# Declare the optimization model
#
model = optimizer.model
# Decision variables x[i]
x = [model.bool() for i in range(nb_items)]
# Weight constraint
knapsack_weight = model.sum(x[i] * weights[i] for i in range(nb_items))
model.constraint(knapsack_weight <= knapsack_bound)
# Maximize value
knapsack_value = model.sum(x[i] * values[i] for i in range(nb_items))
model.maximize(knapsack_value)
model.close()
# Parameterize the optimizer
if len(sys.argv) >= 4:
optimizer.param.time_limit = int(sys.argv[3])
else:
optimizer.param.time_limit = 20
optimizer.solve()
#
# Write the solution in a file
#
if len(sys.argv) >= 3:
with open(sys.argv[2], 'w') as f:
f.write("%d\n" % knapsack_value.value)
for i in range(nb_items):
if x[i].value != 1:
continue
f.write("%d " % i)
f.write("\n")
- Compilation / Execution (Windows)
- cl /EHsc knapsack.cpp -I%HX_HOME%\include /link %HX_HOME%\bin\hexaly130.libknapsack instances\kp_100_1.in
- Compilation / Execution (Linux)
- g++ knapsack.cpp -I/opt/hexaly_13_0/include -lhexaly130 -lpthread -o knapsack./knapsack instances/kp_100_1.in
#include "optimizer/hexalyoptimizer.h"
#include <fstream>
#include <iostream>
#include <vector>
using namespace hexaly;
using namespace std;
class Knapsack {
public:
// Number of items
int nbItems;
// Items properties
vector<int> weights;
vector<int> values;
// Knapsack bound
int knapsackBound;
// Hexaly Optimizer
HexalyOptimizer optimizer;
// Decision variables
vector<HxExpression> x;
// Objective
HxExpression knapsackValue;
/* Read instance data */
void readInstance(const string& fileName) {
ifstream infile;
infile.exceptions(ifstream::failbit | ifstream::badbit);
infile.open(fileName.c_str());
infile >> nbItems;
weights.resize(nbItems);
for (int i = 0; i < nbItems; ++i)
infile >> weights[i];
values.resize(nbItems);
for (int i = 0; i < nbItems; ++i)
infile >> values[i];
infile >> knapsackBound;
}
void solve(int limit) {
// Declare the optimization model
HxModel model = optimizer.getModel();
// Decision variables x[i]
x.resize(nbItems);
for (int i = 0; i < nbItems; ++i) {
x[i] = model.boolVar();
}
// Weight constraint
HxExpression knapsackWeight = model.sum();
for (int i = 0; i < nbItems; ++i) {
HxExpression itemWeight = x[i] * weights[i];
knapsackWeight.addOperand(itemWeight);
}
model.constraint(knapsackWeight <= knapsackBound);
// Maximize value
knapsackValue = model.sum();
for (int i = 0; i < nbItems; ++i) {
HxExpression itemValue = x[i] * values[i];
knapsackValue.addOperand(itemValue);
}
model.maximize(knapsackValue);
model.close();
// Parametrize the optimizer
optimizer.getParam().setTimeLimit(limit);
optimizer.solve();
}
/* Write the solution in a file */
void writeSolution(const string& fileName) {
ofstream outfile;
outfile.exceptions(ofstream::failbit | ofstream::badbit);
outfile.open(fileName.c_str());
outfile << knapsackValue.getValue() << endl;
for (int i = 0; i < nbItems; ++i) {
if (x[i].getValue() == 1)
outfile << i << " ";
}
outfile << endl;
}
};
int main(int argc, char** argv) {
if (argc < 2) {
cerr << "Usage: knapsack inputFile [outputFile] [timeLimit]" << endl;
return 1;
}
const char* instanceFile = argv[1];
const char* solFile = argc > 2 ? argv[2] : NULL;
const char* strTimeLimit = argc > 3 ? argv[3] : "20";
try {
Knapsack model;
model.readInstance(instanceFile);
model.solve(atoi(strTimeLimit));
if (solFile != NULL)
model.writeSolution(solFile);
return 0;
} catch (const exception& e) {
cerr << "An error occurred: " << e.what() << endl;
return 1;
}
}
- Compilation / Execution (Windows)
- copy %HX_HOME%\bin\Hexaly.NET.dll .csc Knapsack.cs /reference:Hexaly.NET.dllKnapsack instances\kp_100_1.in
using System;
using System.IO;
using System.Collections.Generic;
using Hexaly.Optimizer;
public class Knapsack : IDisposable
{
// Number of items
int nbItems;
// Items properties
int[] weights;
int[] values;
// Knapsack bound
int knapsackBound;
// Hexaly Optimizer
HexalyOptimizer optimizer;
// Hexaly Program variables
HxExpression[] x;
// Objective
HxExpression knapsackValue;
public Knapsack()
{
optimizer = new HexalyOptimizer();
}
/* Read instance data */
void ReadInstance(string fileName)
{
using (StreamReader input = new StreamReader(fileName))
{
nbItems = int.Parse(input.ReadLine());
weights = new int[nbItems];
values = new int[nbItems];
string[] splittedWeights = input.ReadLine().Split(' ');
for (int i = 0; i < nbItems; ++i)
weights[i] = int.Parse(splittedWeights[i]);
string[] splittedValues = input.ReadLine().Split(' ');
for (int i = 0; i < nbItems; ++i)
values[i] = int.Parse(splittedValues[i]);
knapsackBound = int.Parse(input.ReadLine());
}
}
public void Dispose()
{
if (optimizer != null)
optimizer.Dispose();
}
void Solve(int limit)
{
// Declare the optimization model
HxModel model = optimizer.GetModel();
// Decision variables x[i]
x = new HxExpression[nbItems];
for (int i = 0; i < nbItems; ++i)
x[i] = model.Bool();
// Weight constraint
HxExpression knapsackWeight = model.Sum();
for (int i = 0; i < nbItems; ++i)
knapsackWeight.AddOperand(x[i] * weights[i]);
model.Constraint(knapsackWeight <= knapsackBound);
// Maximize value
knapsackValue = model.Sum();
for (int i = 0; i < nbItems; ++i)
knapsackValue.AddOperand(x[i] * values[i]);
model.Maximize(knapsackValue);
model.Close();
// Parametrize the optimizer
optimizer.GetParam().SetTimeLimit(limit);
optimizer.Solve();
}
/* Write the solution in a file */
void WriteSolution(string fileName)
{
using (StreamWriter output = new StreamWriter(fileName))
{
output.WriteLine(knapsackValue.GetValue());
for (int i = 0; i < nbItems; ++i)
{
if (x[i].GetValue() == 1)
output.Write(i + " ");
}
output.WriteLine();
}
}
public static void Main(string[] args)
{
if (args.Length < 1)
{
Console.WriteLine("Usage: Knapsack inputFile [solFile] [timeLimit]");
Environment.Exit(1);
}
string instanceFile = args[0];
string outputFile = args.Length > 1 ? args[1] : null;
string strTimeLimit = args.Length > 2 ? args[2] : "20";
using (Knapsack model = new Knapsack())
{
model.ReadInstance(instanceFile);
model.Solve(int.Parse(strTimeLimit));
if (outputFile != null)
model.WriteSolution(outputFile);
}
}
}
- Compilation / Execution (Windows)
- javac Knapsack.java -cp %HX_HOME%\bin\hexaly.jarjava -cp %HX_HOME%\bin\hexaly.jar;. Knapsack instances\kp_100_1.in
- Compilation / Execution (Linux)
- javac Knapsack.java -cp /opt/hexaly_13_0/bin/hexaly.jarjava -cp /opt/hexaly_13_0/bin/hexaly.jar:. Knapsack instances/kp_100_1.in
import java.util.*;
import java.io.*;
import com.hexaly.optimizer.*;
public class Knapsack {
// Number of items
private int nbItems;
// Items properties
private int[] weights;
private int[] values;
// Knapsack bound
private int knapsackBound;
// Hexaly Optimizer
private final HexalyOptimizer optimizer;
// Hexaly Program variables
private HxExpression[] x;
// Objective
private HxExpression knapsackValue;
private Knapsack(HexalyOptimizer optimizer) {
this.optimizer = optimizer;
}
/* Read instance data */
private void readInstance(String fileName) throws IOException {
try (Scanner input = new Scanner(new File(fileName))) {
nbItems = input.nextInt();
weights = new int[nbItems];
for (int i = 0; i < nbItems; ++i) {
weights[i] = input.nextInt();
}
values = new int[nbItems];
for (int i = 0; i < nbItems; ++i) {
values[i] = input.nextInt();
}
knapsackBound = input.nextInt();
}
}
private void solve(int limit) {
// Declare the optimization model
HxModel model = optimizer.getModel();
// Decision variables x[i]
x = new HxExpression[nbItems];
for (int i = 0; i < nbItems; ++i) {
x[i] = model.boolVar();
}
// Weight constraint
HxExpression knapsackWeight = model.sum();
for (int i = 0; i < nbItems; ++i) {
HxExpression itemWeight = model.prod(x[i], weights[i]);
knapsackWeight.addOperand(itemWeight);
}
model.constraint(model.leq(knapsackWeight, knapsackBound));
// Maximize value
knapsackValue = model.sum();
for (int i = 0; i < nbItems; ++i) {
HxExpression itemValue = model.prod(x[i], values[i]);
knapsackValue.addOperand(itemValue);
}
model.maximize(knapsackValue);
model.close();
// Parametrize the optimizer
optimizer.getParam().setTimeLimit(limit);
optimizer.solve();
}
/* Write the solution in a file */
private void writeSolution(String fileName) throws IOException {
try (PrintWriter output = new PrintWriter(fileName)) {
output.println(knapsackValue.getValue());
for (int i = 0; i < nbItems; ++i)
if (x[i].getValue() == 1)
output.print(i + " ");
output.println();
}
}
public static void main(String[] args) {
if (args.length < 1) {
System.err.println("Usage: java Knapsack inputFile [outputFile] [timeLimit]");
System.exit(1);
}
String instanceFile = args[0];
String outputFile = args.length > 1 ? args[1] : null;
String strTimeLimit = args.length > 2 ? args[2] : "20";
try (HexalyOptimizer optimizer = new HexalyOptimizer()) {
Knapsack model = new Knapsack(optimizer);
model.readInstance(instanceFile);
model.solve(Integer.parseInt(strTimeLimit));
if (outputFile != null) {
model.writeSolution(outputFile);
}
} catch (Exception ex) {
System.err.println(ex);
ex.printStackTrace();
System.exit(1);
}
}
}