/multi-constraint-knapsack-problem

A genetic algorithm based multi-constraint knapsack problem solver

Primary LanguageJava

Multi-Constraint Knapsack Solver

A genetic algorithm based multi-constraint knapsack problem solver

Compilation

$ javac Main.java

Usage

$ java Main -i <Input file name> 
            -o <Output file name> 
            -p <Population size> 
            -g <Number of generations> 
            -m <Mutation rate> 
            -c <Cross over rate>

Default Parameters

POPULATION_SIZE = 200
NUM_OF_GENERATIONS = 250000
MUTATION_RATE = 0.05
CROSS_OVER_RATE = 0.5
INPUT_FILE = input.txt
OUTPUT_FILE = output.txt

Input Format

Inputs will always be given as a text file. Input file format, using 10 columns, whenever possible, should be as follows:

π‘š 𝑛 //<m := #knapsacks> <n := #items>
𝑣1 𝑣2 ... 𝑣𝑛 //<n values of items>
π‘Š1 π‘Š2 ... π‘Šπ‘š //<m knapsack capacities>
𝑀1,1 𝑀2,1 ... 𝑀𝑛,1 //<nxm matrix of constraints>
𝑀1,2 𝑀2,2 ... 𝑀𝑛,2
................
𝑀1,π‘š 𝑀2,π‘š ... 𝑀𝑛,π‘š

Output Format

Output is a text file including following:

Total_Value 
π‘₯1 
π‘₯2
.
.
.
π‘₯𝑛

First line is Total_Value which is the sum of the values of the included items (Σ𝑣𝑖π‘₯𝑖). Next lines include zeros and ones

Contributors