Method BinPacking

examples/bin-packing.cpp:423–497

Actual model

  };
  /// Actual model
  BinPacking(const InstanceOptions& opt)
    : IntMinimizeScript(opt),
      spec(opt.instance()),
      load(*this, spec.upper(), 0, spec.capacity()),
      bin(*this, spec.items(), 0, spec.upper()-1),
      bins(*this, spec.lower(), spec.upper()) {
    // Number of items
    int n = bin.size();
    // Number of bins
    int m = load.size();

    // Size of all items
    int s = 0;
    for (int i=0; i<n; i++)
      s += spec.size(i);

    // Array of sizes
    IntArgs sizes(n);
    for (int i=0; i<n; i++)
      sizes[i] = spec.size(i);

    switch (opt.model()) {
    case MODEL_NAIVE:
      {
        // All loads must add up to all item sizes
        linear(*this, load, IRT_EQ, s);

        // Load must be equal to packed items
        BoolVarArgs _x(*this, n*m, 0, 1);
        Matrix<BoolVarArgs> x(_x, n, m);

        for (int i=0; i<n; i++)
          channel(*this, x.col(i), bin[i]);

        for (int j=0; j<m; j++)
          linear(*this, sizes, x.row(j), IRT_EQ, load[j]);
      }
      break;
    case MODEL_PACKING:
      binpacking(*this, load, bin, sizes);
      break;
    }

    // Break symmetries, only if not using CBDF
    if (opt.branching() != BRANCH_CDBF)
      for (int i=1; i<n; i++)
        if (spec.size(i-1) == spec.size(i))
          rel(*this, bin[i-1] <= bin[i]);

    // Pack items that require a bin for sure! (wlog)
    {
      int i = 0;
      // These items all need a bin due to their own size
      for (; (i < n) && (i < m) && (spec.size(i) * 2 > spec.capacity()); i++)
        rel(*this, bin[i] == i);
      // Check if the next item cannot fit to position i-1
      if ((i < n) && (i < m) && (i > 0) &&
          (spec.size(i-1) + spec.size(i) > spec.capacity()))