Knapsack¶

/********** Knapsack.cs **********/

using System;
using System.IO;
using System.Collections.Generic;
using localsolver;


public class Knapsack : IDisposable
{
    // Number of items
    int nbItems;

    // Items properties. 
    int[] weights;
    int[] values;

    // Knapsack bound.
    int knapsackBound;
    
    // Solver. 
    LocalSolver localsolver;

    // LS Program variables. 
    LSExpression[] x;

    // Objective.
    LSExpression knapsackValue;

    // Solutions    (items in the knapsack). 
    List<int> solutions;

    public Knapsack ()
    {
        localsolver = new LocalSolver();
    }

    /* Reads 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(' ');
            if (splittedWeights.Length < nbItems) {
                Console.WriteLine("Wrong number of item weights");
                System.Environment.Exit(1);
            }
            for (int i = 0; i < nbItems; i++) weights[i] = int.Parse(splittedWeights[i]);
            
            string[] splittedValues = input.ReadLine().Split(' ');
            if (splittedValues.Length < nbItems) {
                Console.WriteLine("Wrong number of item values");
                System.Environment.Exit(1);
            }
            for (int i = 0; i < nbItems; i++) values[i] = int.Parse(splittedValues[i]);
            
            knapsackBound = int.Parse(input.ReadLine());            
        }
    }

    public void Dispose ()
    {
        localsolver.Dispose();
    }

    void Solve(int limit)
    {
        /* Declares the optimization model. */
        localsolver = new LocalSolver();
        LSModel model = localsolver.GetModel();

        // Decision variables x[i]
        x = new LSExpression[nbItems];
        for (int i = 0; i < nbItems; i++)
        {
            x[i] = model.Bool();
        }

        // weight constraint
        LSExpression 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();
        
        /* Parameterizes the solver. */
        LSPhase phase = localsolver.CreatePhase();
        phase.SetTimeLimit(limit);

        localsolver.Solve();

        solutions = new List<int>();
        for (int i = 0; i < nbItems; ++i)
        {
            if (x[i].GetValue() == 1) solutions.Add(i);
        }
    }

    /* Writes the solution in a file */
    void WriteSolution(string fileName)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            output.WriteLine(knapsackValue.GetValue());
            for (int i = 0; i < solutions.Count; ++i)
                output.Write(solutions[i] + " ");
            output.WriteLine();
        }
    }
    
     public static void Main (string[] args)
    {
        if (args.Length < 1) 
        {
            Console.WriteLine ("Usage: Knapsack inputFile [solFile] [timeLimit]");
            System.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);
        }
    }   
}