crew.cc

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Guido Tack <tack@gecode.org>
 *     Christian Schulte <schulte@gecode.org>
 *
 *  Copyright:
 *     Guido Tack, 2004
 *     Christian Schulte, 2004
 *
 *  Last modified:
 *     $Date: 2008-01-10 10:39:10 +0100 (Thu, 10 Jan 2008) $ by $Author: tack $
 *     $Revision: 5815 $
 *
 *  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/set.hh"
#include "examples/support.hh"

namespace {
  typedef enum {
    Tom, David, Jeremy, Ron,
    Joe, Bill, Fred,
    Bob, Mario, Ed,
    Carol, Janet, Tracy,
    Marilyn, Carolyn, Cathy,
    Inez, Jean, Heather, Juliet
  } Employee;
  const int noOfEmployees = Juliet+1;

  struct Flight {
    int staff;     
    int stewards;  
    int hostesses; 
    int french;    
    int spanish;   
    int german;    
  };

  const char* employeeToName(Employee e);
  extern const int stewards[];
  extern const int noOfStewards;
  extern const int hostesses[];
  extern const int noOfHostesses;
  extern const int spanishSpeaking[];
  extern const int noOfSpanishSpeaking;
  extern const int frenchSpeaking[];
  extern const int noOfFrenchSpeaking;
  extern const int germanSpeaking[];
  extern const int noOfGermanSpeaking;
  extern const Flight requiredCrew[];
  extern const int noOfFlights;
}

class Crew : public Example {
public:
  SetVarArray flight;

  Crew(const Options&) :
    flight(this,noOfFlights,IntSet::empty,0,noOfEmployees-1)
  {
    IntSet stewardsDS(stewards,noOfStewards);
    IntSet hostessesDS(hostesses,noOfHostesses);
    IntSet spanishDS(spanishSpeaking, noOfSpanishSpeaking);
    IntSet frenchDS(frenchSpeaking, noOfFrenchSpeaking);
    IntSet germanDS(germanSpeaking, noOfGermanSpeaking);

    for (int i=0; i<noOfFlights; i++) {
      IntVarArray ia(this,5,0,noOfEmployees-1);
      SetVar team = flight[i];

      int N        = requiredCrew[i].staff;
      int NStew    = requiredCrew[i].stewards;
      int NHost    = requiredCrew[i].hostesses;
      int NFrench  = requiredCrew[i].french;
      int NSpanish = requiredCrew[i].spanish;
      int NGerman  = requiredCrew[i].german;

      cardinality(this, team,N,N);
      SetVar stewardsInFS(this);
      SetVar hostessesInFS(this);
      SetVar spanishInFS(this);
      SetVar frenchInFS(this);
      SetVar germanInFS(this);

      rel(this, team, SOT_INTER, stewardsDS, SRT_EQ, stewardsInFS);
      rel(this, team, SOT_INTER, hostessesDS, SRT_EQ, hostessesInFS);
      rel(this, team, SOT_INTER, spanishDS, SRT_EQ, spanishInFS);
      rel(this, team, SOT_INTER, frenchDS, SRT_EQ, frenchInFS);
      rel(this, team, SOT_INTER, germanDS, SRT_EQ, germanInFS);

      cardinality(this, stewardsInFS, ia[0]);
      cardinality(this, hostessesInFS, ia[1]);
      cardinality(this, spanishInFS, ia[2]);
      cardinality(this, frenchInFS, ia[3]);
      cardinality(this, germanInFS, ia[4]);

      rel(this, ia[0], IRT_GQ, NStew);
      rel(this, ia[1], IRT_GQ, NHost);
      rel(this, ia[2], IRT_GQ, NSpanish);
      rel(this, ia[3], IRT_GQ, NFrench);
      rel(this, ia[4], IRT_GQ, NGerman);

    }

    for (int i=0; i<noOfFlights-2; i++) {
      rel(this, flight[i], SRT_DISJ, flight[i+1]);
      rel(this, flight[i], SRT_DISJ, flight[i+2]);
    }
    rel(this, flight[noOfFlights-2], SRT_DISJ, flight[noOfFlights-1]);

    branch(this, flight, SET_VAR_NONE, SET_VAL_MIN);
  }

  virtual void
  print(std::ostream& os) {
    for (int i=0; i<noOfFlights; i++) {
      os << "\tFlight " << i+1 << ":" << std::endl;
      os << "\t\tCrew\tStew.\tHost.\tFrench\tSpanish\tGerman"
         << std::endl << "\t";
      os << "\t" << requiredCrew[i].staff << "\t" << requiredCrew[i].stewards
         << "\t" << requiredCrew[i].hostesses << "\t"
         << requiredCrew[i].spanish
         << "\t" << requiredCrew[i].french << "\t" << requiredCrew[i].german 
         << std::endl;

      os << "\t\tSchedule:" << std::endl << "\t\t";
      if (flight[i].assigned()) {
        for (SetVarGlbValues d(flight[i]);d();++d) {
          os << employeeToName(static_cast<Employee>(d.val())) << " ";
        }
      } else {
        os << "\tRequired: ";
        for (SetVarGlbValues d(flight[i]);d();++d) {
          os << employeeToName(static_cast<Employee>(d.val())) << " ";
        }
        os << std::endl << "\t\t\tPossible: ";
        for (SetVarUnknownValues d(flight[i]);d();++d) {
          os << employeeToName(static_cast<Employee>(d.val())) << " ";
        }
      }
      os << std::endl << std::endl;
    }
  }

  Crew(bool share, Crew& s)
    : Example(share,s) {
    flight.update(this,share,s.flight);
  }
  virtual
  Space *copy(bool share) {
    return new Crew(share,*this);
  }

};

int
main(int argc, char* argv[]) {
  Options o("Crew");
  o.iterations(100);
  o.parse(argc,argv);
  Example::run<Crew,DFS,Options>(o);
  return 0;
}

namespace {
  
  const char*
  employeeToName(Employee e) {
    switch(e) {
    case Tom : return "Tom";
    case David : return "David";
    case Jeremy: return "Jeremy";
    case Ron: return "Ron";
    case Joe: return "Joe";
    case Bill: return "Bill";
    case Fred: return "Fred";
    case Bob: return "Bob";
    case Mario: return "Mario";
    case Ed: return "Ed";
    case Carol: return "Carol";
    case Janet: return "Janet";
    case Tracy: return "Tracy";
    case Marilyn: return "Marilyn";
    case Carolyn: return "Carolyn";
    case Cathy: return "Cathy";
    case Inez: return "Inez";
    case Jean: return "Jean";
    case Heather: return "Heather";
    case Juliet: return "Juliet";
    default: GECODE_NEVER; return "";
    }
  }

  // these have to be sorted!
  const int stewards[] =
    {Tom, David, Jeremy, Ron, Joe, Bill, Fred, Bob, Mario, Ed};
  const int noOfStewards = sizeof(stewards) / sizeof(int);
  const int hostesses[] =
    { Carol, Janet, Tracy, Marilyn, Carolyn, Cathy, Inez,
      Jean, Heather, Juliet };
  const int noOfHostesses = sizeof(hostesses) / sizeof(int);
  const int frenchSpeaking[] =
    { Bill, Inez, Jean, Juliet };
  const int noOfFrenchSpeaking = sizeof(frenchSpeaking) / sizeof(int);
  const int germanSpeaking[] =
    { Tom, Jeremy, Mario, Cathy, Juliet };
  const int noOfGermanSpeaking = sizeof(germanSpeaking) / sizeof(int);
  const int spanishSpeaking[] =
    { Joe, Bill, Fred, Mario, Marilyn, Inez, Heather };
  const int noOfSpanishSpeaking = sizeof(spanishSpeaking) / sizeof(int);

  const Flight requiredCrew[] =
    { {4,1,1,1,1,1},
      {5,1,1,1,1,1},
      {5,1,1,1,1,1},
      {6,2,2,1,1,1},
      {7,3,3,1,1,1},
      {4,1,1,1,1,1},
      {5,1,1,1,1,1},
      {6,1,1,1,1,1},
      {6,2,2,1,1,1},
      {7,3,3,1,1,1} };
  
  const int noOfFlights = sizeof(requiredCrew) / sizeof(Flight);
}

// STATISTICS: example-any