Adding quantity-per-item constraint to knapsack algorithm

295 views Asked by At

I am working knapsack problem. With online solution available i have done this so far

        private void main()
        {
        var random = new Random();
        var products = new List<Product>();
        products.Add(new Product("Coil1", 0, 0, 5.6));
        products.Add(new Product("Coil2", 0, 0, 5.91));
        products.Add(new Product("Coil3", 0, 0, 5));
        products.Add(new Product("Coil4", 0, 0, 5));
        products.Add(new Product("Coil5", 0, 0, 5));
        products.Add(new Product("Coil6", 0, 0, 5));
        products.Add(new Product("Coil7", 0, 0, 5));
        products.Add(new Product("Coil8", 0, 0, 5));
        products.Add(new Product("Coil9", 0, 0, 5.92));
        products.Add(new Product("Coil10", 0, 0, 15));

        var clock = new Stopwatch();
        clock.Start();
        var solution = Profit.OptimizedList(products, 7);
        clock.Stop();
        Console.WriteLine("Time (ms): " + clock.ElapsedMilliseconds);
        foreach (var product in solution)
        {
            if (product.Value > 0)
            {
                Console.WriteLine(product.Key.Name + ": " + product.Value + " : Weight - " + product.Key.Weight);
            }
        }
     }


     public class Profit
       {
         public static IDictionary<Product, int> OptimizedList(IEnumerable<Product> products, double maxWeight)
         {
        //SOLVER INITIALIZE
        var solver = SolverContext.GetContext();
        solver.ClearModel();
        var model = solver.CreateModel();

        var decisions = products.Select(
           it => new Decision(Domain.IntegerNonnegative, it.Name));
        model.AddDecisions(decisions.ToArray());

        //GOAL
        var objective = new SumTermBuilder(decisions.Count());
        foreach (var product in products)
        {
            var productDecision = model.Decisions.First(
               it => it.Name == product.Name);
            objective.Add(productDecision * product.Weight);
        }
        model.AddGoal("Profit", GoalKind.Maximize, objective.ToTerm());


        //CONTRAINT 2
        var weightComponents = new SumTermBuilder(decisions.Count());
        foreach (var product in products)
        {
            var productDecision = model.Decisions.First(
               it => it.Name == product.Name);
            weightComponents.Add(productDecision * product.Weight);
        }

        var weightConstraint = weightComponents.ToTerm() <= maxWeight;
        model.AddConstraint("Weight", weightConstraint);


        //SOLVE
        var solution = solver.Solve();

        var orders = new Dictionary<Product, int>();
        if (solution.Quality == SolverQuality.Optimal)
        {
            foreach (var product in products)
            {
                var productDecision = model.Decisions.First(it => it.Name == product.Name);
                orders.Add(product, (int)productDecision.ToDouble());
            }
        }

        return orders;
    }
}

public class Product
{
    public Product(string name, double cost, double price, double weight)
    {
        this.Name = name;
        this.Cost = cost;
        this.Price = price;
        this.Weight = weight;
    }

    public string Name { get; private set; }
    public double Cost { get; private set; }
    public double Price { get; private set; }
    public double Weight { get; private set; }
    public double Margin
    {
        get { return this.Price - this.Cost; }
    }
}

Now i want to add a contraint that, only one quantity per item is allowed. I created a contraint like this,

        //CONTRAINT 1
        var CountComponents = new SumTermBuilder(decisions.Count());
        foreach (var product in products)
        {
            var productDecision = model.Decisions.First(
               it => it.Name == product.Name);
            CountComponents.Add(productDecision);
        }

        var CountConstraint = CountComponents.ToTerm() <= 1;
        model.AddConstraint("Count", CountConstraint);

but it is taking only one item in total (0-1 Knapsack problem).

How to add contraint so that only specified quantity per item is allowed in the optimization?

0

There are 0 answers