bacp.cpp

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Guido Tack <tack@gecode.org>
 *
 *  Contributing authors:
 *     Mikael Lagerkvist <lagerkvist@gecode.org>
 *
 *  Copyright:
 *     Guido Tack, 2006
 *     Mikael Lagerkvist, 2010
 *
 *  Last modified:
 *     $Date: 2011-09-19 14:02:26 +0200 (Mon, 19 Sep 2011) $ by $Author: schulte $
 *     $Revision: 12400 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  Permission is hereby granted, free of charge, to any person obtaining
 *  a copy of this software and associated documentation files (the
 *  "Software"), to deal in the Software without restriction, including
 *  without limitation the rights to use, copy, modify, merge, publish,
 *  distribute, sublicense, and/or sell copies of the Software, and to
 *  permit persons to whom the Software is furnished to do so, subject to
 *  the following conditions:
 *
 *  The above copyright notice and this permission notice shall be
 *  included in all copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */

#include <gecode/driver.hh>
#include <gecode/int.hh>
#include <gecode/minimodel.hh>
#include <gecode/int/branch.hh>

#include <map>
#include <string>
#include <list>
#include <vector>

using namespace Gecode;

class Course {
public:
  const char* name; 
  int credit;       
};

class Curriculum {
public:
  int p;
  int a;
  int b;
  int c;
  int d;

  const Course *courses;
  const char **prereqs;
};

namespace {

  extern const Curriculum curriculum[];
  extern const unsigned int n_examples;

}

class BACP : public MinimizeScript {
protected:
  const Curriculum curr;

  IntVarArray l;
  IntVar u;
  IntVarArray q;

  IntVarArray x;
public:
  enum {
    BRANCHING_NAIVE,    
    BRANCHING_LOAD,     
    BRANCHING_LOAD_REV, 
  };

  BACP(const SizeOptions& opt) : curr(curriculum[opt.size()]) {
    std::map<std::string, int> courseMap; // Map names to course numbers
    int maxCredit = 0;
    int numberOfCourses = 0;
    for (const Course* co=curr.courses; co->name != 0; co++) {
      courseMap[co->name] = numberOfCourses++;
      maxCredit += co->credit;
    }

    int p = curr.p;
    int a = curr.a;
    int b = curr.b;
    int c = curr.c;
    int d = curr.d;

    l = IntVarArray(*this, p, a, b);
    u = IntVar(*this, 0, maxCredit);
    q = IntVarArray(*this, p, c, d);
    x = IntVarArray(*this, numberOfCourses, 0, p-1);

    for (int j=0; j<p; j++) {
      BoolVarArgs xij(*this, numberOfCourses, 0, 1);
      IntArgs t(numberOfCourses);
      for (int i=0; i<numberOfCourses; i++) {
        rel(*this, (x[i]==j) == xij[i]);
        t[i] = curr.courses[i].credit;
      }
      // sum over all t*(xi==j) is load of period i
      linear(*this, t, xij, IRT_EQ, l[j]);
      // sum over all (xi==j) is number of courses in period i
      linear(*this, xij, IRT_EQ, q[j]);
    }

    // Precedence
    for (const char** prereq = curr.prereqs; *prereq != 0; prereq+=2)
      rel(*this, x[courseMap[*prereq]] < x[courseMap[*(prereq+1)]]);

    // Optimization criterion: minimize u
    max(*this, l, u);

    // Redundant constraints
    linear(*this, l, IRT_EQ, maxCredit);
    linear(*this, q, IRT_EQ, numberOfCourses);

    if (opt.branching() == BRANCHING_NAIVE) {
      branch(*this, x, INT_VAR_SIZE_MIN, INT_VAL_MIN);
    } else {
      Int::Branch::BySizeMin varsel(*this, VarBranchOptions::def);
      ViewArray<Int::IntView> xv(*this, IntVarArgs(x));
      if (opt.branching() == BRANCHING_LOAD) {
        ValBestLoad<true> valsel(*this, ValBranchOptions::def);
        ViewValBrancher<Int::Branch::BySizeMin, ValBestLoad<true> >
          ::post(*this,xv,varsel,valsel);
      } else { 
        ValBestLoad<false> valsel(*this, ValBranchOptions::def);
        ViewValBrancher<Int::Branch::BySizeMin, ValBestLoad<false> >
          ::post(*this,xv,varsel,valsel);
      }
    }
  }
    
  BACP(bool share, BACP& bacp) : MinimizeScript(share,bacp),
    curr(bacp.curr) {
    l.update(*this, share, bacp.l);
    u.update(*this, share, bacp.u);
    x.update(*this, share, bacp.x);
  }
  virtual Space*
  copy(bool share) {
    return new BACP(share,*this);
  }
  virtual IntVar cost(void) const {
    return u;
  }
  virtual void
  print(std::ostream& os) const {
    std::vector<std::list<int> > period(curr.p);
    for (int i=x.size(); i--;)
      period[x[i].val()].push_back(i);

    os << "Solution with load " << u.val() << ":" << std::endl;
    for (int i=0; i<curr.p; i++) {
      os << "\tPeriod "<<i+1<<": ";
      for (std::list<int>::iterator v=period[i].begin();
           v != period[i].end(); ++v) {
        os << curr.courses[*v].name << " ";
      }
      os << std::endl;
    }
    os << std::endl;
  }

  template <bool minimize>
  class ValBestLoad : public ValSelBase<Int::IntView,int> {
  public:
    ValBestLoad(void) {}

    ValBestLoad(Space& home, const ValBranchOptions& vbo)
      : ValSelBase<Int::IntView,int>(home,vbo) {}

    int val(Space& home, Int::IntView x) const {
      BACP& b = static_cast<BACP&>(home);
      Int::ViewValues<Int::IntView> values(x);
      int val = -1;
      int best = minimize ? Int::Limits::max+1 : Int::Limits::min-1;
      while (values()) {
        if (minimize 
            ? b.l[values.val()].min() < best
            : b.l[values.val()].min() > best) {
          val  = values.val();
          best = b.l[val].min();
        }
        ++values;
      }
      assert(val != -1);
      return val;
    }

    ModEvent tell(Space& home, unsigned int a, Int::IntView x, int n) {
      return (a == 0) ? x.eq(home,n) : x.gr(home,n);
    }
  };
};

int
main(int argc, char* argv[]) {
  SizeOptions opt("BACP");
  opt.branching(BACP::BRANCHING_NAIVE);
  opt.branching(BACP::BRANCHING_NAIVE,"naive");
  opt.branching(BACP::BRANCHING_LOAD,"load");
  opt.branching(BACP::BRANCHING_LOAD_REV,"load-reverse");
  opt.size(2);
  opt.solutions(0);
  opt.iterations(20);
  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;
  }
  MinimizeScript::run<BACP,BAB,SizeOptions>(opt);
  return 0;
}

namespace {

  const Course courses8[] =
    {
      {"dew100", 1},
      {"fis100", 3},
      {"hcw310", 1},{"iwg101", 2},{"mat190", 4},{"mat192", 4},{"dew101", 1},
      {"fis101", 5},{"iwi131", 3},{"mat191", 4},{"mat193", 4},{"fis102", 5},{"hxwxx1", 1},
      {"iei134", 3},{"iei141", 3},{"mat194", 4},
      {"dewxx0", 1},{"hcw311", 1},{"iei132", 3},{"iei133", 3},{"iei142", 3},{"iei162", 3},
      {"iwn170", 3},{"mat195", 3},{"hxwxx2", 1},{"iei231", 4},{"iei241", 4},{"iei271", 3},{"iei281", 3},{"iwn261", 3},
      {"hfw120", 2},{"iei233", 4},{"iei238", 3},{"iei261", 3},{"iei272", 3},{"iei273", 3},{"iei161", 3},{"iei232", 3},
      {"iei262", 3},{"iei274", 3},{"iwi365", 3},{"iwn270", 3},{"hrw130", 2},{"iei218", 3},{"iei219", 3},{"iei248", 3},
      {0,0}
    };

  const char* prereqs8[] =
    {
    "dew101","dew100",
    "fis101","fis100",
    "fis101","mat192",
    "mat191","mat190",
    "mat193","mat190",
    "mat193","mat192",
    "fis102","fis101",
    "fis102","mat193",
    "iei134","iwi131",
    "iei141","iwi131",
    "mat194","mat191 ",
    "mat194","mat193",
    "dewxx0","dew101",
    "hcw311","hcw310",
    "iei132","iei134",
    "iei133","iei134",
    "iei142","iei141",
    "mat195","mat194",
    "iei231","iei134",
    "iei241","iei142",
    "iei271","iei162",
    "iei281","mat195",
    "iei233","iei231",
    "iei238","iei231",
    "iei261","iwn261",
    "iei272","iei271",
    "iei273","iei271",
    "iei273","iei271",
    "iei161","iwn261",
    "iei161","iwn261",
    "iei232","iei273",
    "iei232","iei273",
    "iei262","iwn261",
    "iei274","iei273",
    "iei274","iei273",
    "iei219","iei232",
    "iei248","iei233",
    "iei248","iei233",
    0,0
    };

  const Course courses10[] = {
  {"dew100",1},
  {"fis100",3},
  {"hrwxx1",2},
  {"iwg101",2},
  {"mat021",5},
  {"qui010",3},
  {"dew101",1},
  {"fis110",5},
  {"hrwxx2",2},
  {"iwi131",3},
  {"mat022",5},
  {"dewxx0",1},
  {"fis120",4},
  {"hcw310",1},
  {"hrwxx3",2},
  {"ili134",4},
  {"ili151",3},
  {"mat023",4},
  {"hcw311",1},
  {"ili135",4},
  {"ili153",3},
  {"ili260",3},
  {"iwn261",3},
  {"mat024",4},
  {"fis130",4},
  {"ili239",4},
  {"ili245",4},
  {"ili253",4},
  {"fis140",4},
  {"ili236",4},
  {"ili243",4},
  {"ili270",3},
  {"ili280",4},
  {"ici344",4},
  {"ili263",3},
  {"ili332",4},
  {"ili355",4},
  {"iwn170",3},
  {"icdxx1",3},
  {"ili362",3},
  {"iwn270",3},
  {"icdxx2",3},
  {0,0}
  };

  const char* prereqs10[] = {
  "dew101","dew100",
  "fis110","fis100",
  "fis110","mat021",
  "mat022","mat021",
  "dewxx0","dew101",
  "fis120","fis110",
  "fis120","mat022",
  "ili134","iwi131",
  "ili151","iwi131",
  "mat023","mat022",
  "hcw311","hcw310",
  "ili135","ili134",
  "ili153","ili134",
  "ili153","ili151",
  "mat024","mat023",
  "fis130","fis110",
  "fis130","mat022",
  "ili239","ili135",
  "ili245","ili153",
  "ili253","ili153",
  "fis140","fis120",
  "fis140","fis130",
  "ili236","ili239",
  "ili243","ili245",
  "ili270","ili260",
  "ili270","iwn261",
  "ili280","mat024",
  "ici344","ili243",
  "ili263","ili260",
  "ili263","iwn261",
  "ili332","ili236",
  "ili355","ili153",
  "ili355","ili280",
  "ili362","ili263",
  0,0
  };

  const Course courses12[] = {
  {"dew100",1},
  {"fis100",3},
  {"hcw310",1},
  {"iwg101",2},
  {"mat111",4},
  {"mat121",4},
  {"dew101",1},
  {"fis110",5},
  {"iwi131",3},
  {"mat112",4},
  {"mat122",4},
  {"dewxx0",1},
  {"fis120",4},
  {"hcw311",1},
  {"hxwxx1",1},
  {"ili142",4},
  {"mat113",4},
  {"mat123",4},
  {"fis130",4},
  {"ili134",4},
  {"ili151",3},
  {"iwm185",3},
  {"mat124",4},
  {"fis140",4},
  {"hxwxx2",1},
  {"ile260",3},
  {"ili260",3},
  {"iwn170",3},
  {"qui104",3},
  {"ili231",3},
  {"ili243",4},
  {"ili252",4},
  {"ili273",3},
  {"mat210",4},
  {"mat260",4},
  {"ild208",3},
  {"ili221",4},
  {"ili274",3},
  {"ili281",3},
  {"iwn270",3},
  {"mat270",4},
  {"hrw150",2},
  {"ili238",4},
  {"ili242",3},
  {"ili275",3},
  {"ili355",4},
  {"hrw110",2},
  {"ici393",4},
  {"ili237",4},
  {"ili334",4},
  {"ili363",3},
  {"iwn261",3},
  {"hrw100",2},
  {"ici382",4},
  {"ili331",4},
  {"ili362",3},
  {"ili381",3},
  {"iln230",3},
  {"ici313",2},
  {"ici315",2},
  {"ici332",3},
  {"ici344",4},
  {"icn336",3},
  {"iwi365",3},
  {"ici314",2},
  {"ici367",2},
  {0,0}
  };

  const char* prereqs12[] = {
  "dew101","dew100",
  "fis110","fis100",
  "fis110","mat121",
  "mat112","mat111",
  "mat122","mat111",
  "mat122","mat121",
  "dewxx0","dew101",
  "fis120","fis110",
  "fis120","mat122",
  "hcw311","hcw310",
  "ili142","iwi131",
  "mat113","mat112",
  "mat113","mat122",
  "mat123","mat112",
  "mat123","mat122",
  "fis130","fis110",
  "fis130","mat122",
  "ili134","iwi131",
  "ili151","mat112",
  "mat124","mat113",
  "mat124","mat123",
  "fis140","fis120",
  "fis140","fis130",
  "ile260","fis120",
  "ile260","mat124",
  "ili231","iwi131",
  "ili252","iwi131",
  "ili273","ili260",
  "mat210","mat113",
  "mat260","iwi131",
  "mat260","mat113",
  "mat260","mat123",
  "ili221","ili134",
  "ili221","ili231",
  "ili221","mat260",
  "ili274","ili273",
  "ili281","mat260",
  "mat270","iwi131",
  "mat270","mat113",
  "mat270","mat123",
  "ili238","ili134",
  "ili242","ili142",
  "ili275","ili274",
  "ili355","ili221",
  "hrw110","hrw150",
  "ici393","mat210",
  "ici393","mat260",
  "ili237","ili231",
  "ili237","ili252",
  "ili334","ili238",
  "ili363","ili273",
  "hrw100","hrw110",
  "ici382","ili334",
  "ili331","ili238",
  "ili331","ili274",
  "ili362","ili363",
  "ili381","ili281",
  "ili381","mat210",
  "iln230","iwn170",
  "ici313","ili331",
  "ici332","ici393",
  "ici332","ili331",
  "ici344","ili243",
  "icn336","ici393",
  "ici314","ici313",
  0,0
  };

  const Curriculum curriculum[]=
    { { 8, 10, 24, 2, 10,
        courses8, prereqs8
      },
      { 10, 10, 24, 2, 10,
        courses10, prereqs10
      },
      { 12, 10, 24, 2, 10,
        courses12, prereqs12
      }
    };

  const unsigned int n_examples = sizeof(curriculum) / sizeof(Curriculum);

}

// STATISTICS: example-any