main page modules namespaces classes files
Gecode home

search for 

packing.cc

Go to the documentation of this file.

/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.org>
 *     Mikael Lagerkvist <lagerkvist@gecode.org>
 *
 *  Copyright:
 *     Christian Schulte, 2003
 *     Mikael Lagerkvist, 2005
 *
 *  Last modified:
 *     $Date: 2006-08-04 16:06:52 +0200 (Fri, 04 Aug 2006) $ by $Author: schulte $
 *     $Revision: 3517 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  See the file "LICENSE" for information on usage and
 *  redistribution of this file, and for a
 *     DISCLAIMER OF ALL WARRANTIES.
 *
 */

#include "examples/support.hh"
#include "gecode/minimodel.hh"

//@
class PackingSpec {
public:
  int x; int y;
  int n; const int* s;
  PackingSpec(int x0, int y0, const int s0[]) :
    x(x0), y(y0), s(s0) {
    int i = 0;
    while (s[i]) i++;
    n = i;
  }
};

static const int s0_s[] = {2,2,2,2,0};
static const PackingSpec s0(4,4,s0_s);

static const int s1_s[] = {3,2,2,1,1,1,0};
static const PackingSpec s1(5,4,s1_s);

static const int s2_s[] = {6,4,4,4,2,2,2,2,0};
static PackingSpec s2(10,10,s2_s);

static const int s3_s[] = {9,8,8,7,5,4,4,4,4,4,3,3,3,2,2,1,1,0};
static const PackingSpec s3(20,20,s3_s);

static const int s4_s[] = {18,15,14,10,9,8,7,4,1,0};
static const PackingSpec s4(32,33,s4_s);

static const int s5_s[] = {25,24,23,22,19,17,11,6,5,3,0};
static const PackingSpec s5(65,47,s5_s);

static const int s6_s[] = {50,42,37,35,33,29,27,25,24,19,18,
                           17,16,15,11,9,8,7,6,4,2,0};
static const PackingSpec s6(112,112,s6_s);

static const int s7_s[] = {81,64,56,55,51,43,39,38,35,33,31,30,29,20,
                           18,16,14,9,8,5,4,3,2,1,0};
static const PackingSpec s7(175,175,s7_s);

static const PackingSpec* specs[] = {&s0,&s1,&s2,&s3,&s4,&s5,&s6,&s7};
static const unsigned int n_examples = sizeof(specs) / sizeof(PackingSpec*);

class Packing : public Example {
protected:
  const PackingSpec& s;
  IntVarArray x;
  IntVarArray y;
public:
  Packing(const Options& opt)
    : s(*specs[opt.size]),
      x(this,s.n,0,s.x-1), y(this,s.n,0,s.y-1) {

    // Restrict position according to square size
    for (int i=s.n; i--; ) {
      rel(this, x[i], IRT_LQ, s.x-s.s[i]);
      rel(this, y[i], IRT_LQ, s.y-s.s[i]);
    }

    // Squares do not overlap
    for (int i=0; i<s.n; i++)
      for (int j=i+1; j<s.n; j++)
        post(this, tt(~(x[j]-x[i] >= s.s[i]) || ~(x[i]-x[j] >= s.s[j]) ||
                      ~(y[j]-y[i] >= s.s[i]) || ~(y[i]-y[j] >= s.s[j])));

    /*
     * Symmetry breaking
     *
     */
    for (int i=s.n-1; i--; )
      if (s.s[i] == s.s[i+1])
        rel(this, x[i], IRT_LQ, x[i+1]);

    /*
     * Capacity constraints
     *
     */
    if (opt.naive) {
      IntArgs sa(s.n,s.s);
      BoolVarArgs b(s.n);
      for (int cx=0; cx<s.x; cx++) {
        for (int i=0; i<s.n; i++) {
          BoolVar b_cx(this,0,1);
          dom(this, x[i], cx-s.s[i]+1, cx, b_cx);
          b[i] = b_cx;
        }
        linear(this, sa, b, IRT_EQ, s.y);
      }
      for (int cy=0; cy<s.y; cy++) {
        for (int i=0; i<s.n; i++) {
          BoolVar b_cy(this,0,1);
          dom(this, y[i], cy-s.s[i]+1, cy, b_cy);
          b[i] = b_cy;
        }
        linear(this, sa, b, IRT_EQ, s.x);
      }
    } else {
      IntArgs m(s.n), dh(s.n);
      for (int i = s.n; i--; ) {
        m[i]  = 0;
        dh[i] = s.s[i];
      }
      IntVarArgs e(s.n);
      IntArgs limit(1);
      {
        // x-direction
        for (int i = s.n; i--; ) {
          IntVar ei(this, 0, s.x);
          e[i] = ei;
        }
        limit[0] = s.y;
        cumulatives(this, m, x, dh, e, dh, limit,  true);
        cumulatives(this, m, x, dh, e, dh, limit, false);
      }
      {
        // y-direction
        for (int i = s.n; i--; ) {
          IntVar ei(this, 0, s.y);
          e[i] = ei;
        }
        limit[0] = s.x;
        cumulatives(this, m, y, dh, e, dh, limit,  true);
        cumulatives(this, m, y, dh, e, dh, limit, false);
      }
    }

    branch(this, x, BVAR_MIN_MIN, BVAL_MIN);
    branch(this, y, BVAR_MIN_MIN, BVAL_MIN);
  }

  Packing(bool share, Packing& s) : Example(share,s), s(s.s) {
    x.update(this, share, s.x);
    y.update(this, share, s.y);
  }
  virtual Space*
  copy(bool share) {
    return new Packing(share,*this);
  }
  virtual void
  print(void) {
    std::cout << "\t";
    for (int i=0; i<s.n; i++)
      std::cout << "(" << x[i] << "," << y[i] << ") ";
    std::cout << std::endl;
  }
};

int
main(int argc, char** argv) {
  Options opt("Packing");
  opt.naive = true;
  opt.size  = 7;
  opt.parse(argc,argv);
  if (opt.size >= n_examples) {
    std::cerr << "Error: size must be between 0 and " << n_examples - 1
              << std::endl;
    return 1;
  }
  Example::run<Packing,DFS>(opt);
  return 0;
}

// STATISTICS: example-any