flatzinc.hh

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Guido Tack <tack@gecode.dev>
 *
 *  Contributing authors:
 *     Gabriel Hjort Blindell <gabriel.hjort.blindell@gmail.com>
 *
 *  Copyright:
 *     Guido Tack, 2007-2012
 *     Gabriel Hjort Blindell, 2012
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.dev
 *
 *  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.
 *
 */
 
#ifndef GECODE_FLATZINC_HH
#define GECODE_FLATZINC_HH
 
#include <iostream>
 
#include <gecode/kernel.hh>
#include <gecode/int.hh>
#ifdef GECODE_HAS_SET_VARS
#include <gecode/set.hh>
#endif
#ifdef GECODE_HAS_FLOAT_VARS
#include <gecode/float.hh>
#endif
#include <map>
 
/*
 * Support for DLLs under Windows
 *
 */
 
#if !defined(GECODE_STATIC_LIBS) && \
    (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
 
#ifdef GECODE_BUILD_FLATZINC
#define GECODE_FLATZINC_EXPORT __declspec( dllexport )
#else
#define GECODE_FLATZINC_EXPORT __declspec( dllimport )
#endif
 
#else
 
#ifdef GECODE_GCC_HAS_CLASS_VISIBILITY
 
#define GECODE_FLATZINC_EXPORT __attribute__ ((visibility("default")))
 
#else
 
#define GECODE_FLATZINC_EXPORT
 
#endif
#endif
 
// Configure auto-linking
#ifndef GECODE_BUILD_FLATZINC
#define GECODE_LIBRARY_NAME "FlatZinc"
#include <gecode/support/auto-link.hpp>
#endif
 
#include <gecode/driver.hh>
 
#include <gecode/flatzinc/conexpr.hh>
#include <gecode/flatzinc/ast.hh>
#include <gecode/flatzinc/varspec.hh>

 
namespace Gecode { namespace FlatZinc {

  class GECODE_FLATZINC_EXPORT Printer {
  private:
    std::vector<std::string> iv_names;
    std::vector<std::string> bv_names;
#ifdef GECODE_HAS_FLOAT_VARS
    std::vector<std::string> fv_names;
#endif
#ifdef GECODE_HAS_SET_VARS
    std::vector<std::string> sv_names;
#endif
    AST::Array* _output;
    void printElem(std::ostream& out,
                   AST::Node* ai,
                   const Gecode::IntVarArray& iv,
                   const Gecode::BoolVarArray& bv
#ifdef GECODE_HAS_SET_VARS
                   ,
                   const Gecode::SetVarArray& sv
#endif
#ifdef GECODE_HAS_FLOAT_VARS
                  ,
                  const Gecode::FloatVarArray& fv
#endif
                   ) const;
    void printElemDiff(std::ostream& out,
                       AST::Node* ai,
                       const Gecode::IntVarArray& iv1,
                       const Gecode::IntVarArray& iv2,
                       const Gecode::BoolVarArray& bv1,
                       const Gecode::BoolVarArray& bv2
#ifdef GECODE_HAS_SET_VARS
                       ,
                       const Gecode::SetVarArray& sv1,
                       const Gecode::SetVarArray& sv2
#endif
#ifdef GECODE_HAS_FLOAT_VARS
                       ,
                       const Gecode::FloatVarArray& fv1,
                       const Gecode::FloatVarArray& fv2
#endif
                       ) const;
  public:
    Printer(void) : _output(nullptr) {}
    void init(AST::Array* output);
 
    void print(std::ostream& out,
               const Gecode::IntVarArray& iv,
               const Gecode::BoolVarArray& bv
#ifdef GECODE_HAS_SET_VARS
               ,
               const Gecode::SetVarArray& sv
#endif
#ifdef GECODE_HAS_FLOAT_VARS
               ,
               const Gecode::FloatVarArray& fv
#endif
               ) const;
 
    void printDiff(std::ostream& out,
               const Gecode::IntVarArray& iv1, const Gecode::IntVarArray& iv2,
               const Gecode::BoolVarArray& bv1, const Gecode::BoolVarArray& bv2
#ifdef GECODE_HAS_SET_VARS
               ,
               const Gecode::SetVarArray& sv1, const Gecode::SetVarArray& sv2
#endif
#ifdef GECODE_HAS_FLOAT_VARS
               ,
               const Gecode::FloatVarArray& fv1,
               const Gecode::FloatVarArray& fv2
#endif
               ) const;
 
 
    ~Printer(void);
 
    void addIntVarName(const std::string& n);
    const std::string& intVarName(int i) const { return iv_names[i]; }
    void addBoolVarName(const std::string& n);
    const std::string& boolVarName(int i) const { return bv_names[i]; }
#ifdef GECODE_HAS_FLOAT_VARS
    void addFloatVarName(const std::string& n);
    const std::string& floatVarName(int i) const { return fv_names[i]; }
#endif
#ifdef GECODE_HAS_SET_VARS
    void addSetVarName(const std::string& n);
    const std::string& setVarName(int i) const { return sv_names[i]; }
#endif
 
    void shrinkElement(AST::Node* node,
                       std::map<int,int>& iv, std::map<int,int>& bv,
                       std::map<int,int>& sv, std::map<int,int>& fv);
 
    void shrinkArrays(Space& home,
                      int& optVar, bool optVarIsInt,
                      Gecode::IntVarArray& iv,
                      Gecode::BoolVarArray& bv
#ifdef GECODE_HAS_SET_VARS
                      ,
                      Gecode::SetVarArray& sv
#endif
#ifdef GECODE_HAS_FLOAT_VARS
                      ,
                      Gecode::FloatVarArray& fv
#endif
                     );
 
  private:
    Printer(const Printer&);
    Printer& operator=(const Printer&);
  };

  class FlatZincOptions : public Gecode::BaseOptions {
  protected:

      Gecode::Driver::IntOption         _solutions; 
      Gecode::Driver::BoolOption        _allSolutions; 
      Gecode::Driver::DoubleOption      _threads;   
      Gecode::Driver::BoolOption        _free; 
      Gecode::Driver::DoubleOption      _decay;       
      Gecode::Driver::UnsignedIntOption _c_d;       
      Gecode::Driver::UnsignedIntOption _a_d;       
      Gecode::Driver::UnsignedLongLongIntOption _node;      
      Gecode::Driver::UnsignedLongLongIntOption _fail;      
      Gecode::Driver::DoubleOption _time;      
      Gecode::Driver::DoubleOption _time_limit;  
      Gecode::Driver::IntOption         _seed;      
      Gecode::Driver::StringOption      _restart;   
      Gecode::Driver::DoubleOption      _r_base;    
      Gecode::Driver::UnsignedIntOption _r_scale;   
      Gecode::Driver::UnsignedLongLongIntOption _r_limit; 
      Gecode::Driver::BoolOption        _nogoods;   
      Gecode::Driver::UnsignedIntOption _nogoods_limit; 
      Gecode::Driver::BoolOption        _interrupt; 
      Gecode::Driver::DoubleOption      _step;        


      Gecode::Driver::StringOption      _mode;       
      Gecode::Driver::BoolOption        _stat;       
      Gecode::Driver::StringValueOption _output;     
 
#ifdef GECODE_HAS_CPPROFILER
      Gecode::Driver::ProfilerOption    _profiler; 
#endif

  public:
    FlatZincOptions(const char* s)
    : Gecode::BaseOptions(s),
      _solutions("n","number of solutions (0 = all, -1 = one/best)",-1),
      _allSolutions("a", "return all solutions (equal to -n 0)"),
      _threads("p","number of threads (0 = #processing units)",
               Gecode::Search::Config::threads),
      _free("f", "free search, no need to follow search-specification"),
      _decay("decay","decay factor",0.99),
      _c_d("c-d","recomputation commit distance",Gecode::Search::Config::c_d),
      _a_d("a-d","recomputation adaption distance",Gecode::Search::Config::a_d),
      _node("node","node cutoff (0 = none, solution mode)"),
      _fail("fail","failure cutoff (0 = none, solution mode)"),
      _time("time","time (in ms) cutoff (0 = none, solution mode)"),
      _time_limit("t","time (in ms) cutoff (0 = none, solution mode)"),
      _seed("r","random seed",0),
      _restart("restart","restart sequence type",RM_NONE),
      _r_base("restart-base","base for geometric restart sequence",1.5),
      _r_scale("restart-scale","scale factor for restart sequence",250),
      _r_limit("restart-limit","restart cutoff (0 = none, solution mode)"),
      _nogoods("nogoods","whether to use no-goods from restarts",false),
      _nogoods_limit("nogoods-limit","depth limit for no-good extraction",
                     Search::Config::nogoods_limit),
      _interrupt("interrupt","whether to catch Ctrl-C (true) or not (false)",
                 true),
      _step("step","step distance for float optimization",0.0),
      _mode("mode","how to execute script",Gecode::SM_SOLUTION),
      _stat("s","emit statistics"),
      _output("o","file to send output to")
 
#ifdef GECODE_HAS_CPPROFILER
      ,
      _profiler("cp-profiler", "use this execution id and port (comma separated) with CP-profiler")
#endif
    {
      _mode.add(Gecode::SM_SOLUTION, "solution");
      _mode.add(Gecode::SM_STAT, "stat");
      _mode.add(Gecode::SM_GIST, "gist");
      _restart.add(RM_NONE,"none");
      _restart.add(RM_CONSTANT,"constant");
      _restart.add(RM_LINEAR,"linear");
      _restart.add(RM_LUBY,"luby");
      _restart.add(RM_GEOMETRIC,"geometric");
 
      add(_solutions); add(_threads); add(_c_d); add(_a_d);
      add(_allSolutions);
      add(_free);
      add(_decay);
      add(_node); add(_fail); add(_time); add(_time_limit); add(_interrupt);
      add(_seed);
      add(_step);
      add(_restart); add(_r_base); add(_r_scale); add(_r_limit);
      add(_nogoods); add(_nogoods_limit);
      add(_mode); add(_stat);
      add(_output);
#ifdef GECODE_HAS_CPPROFILER
      add(_profiler);
#endif
    }
 
    void parse(int& argc, char* argv[]) {
      Gecode::BaseOptions::parse(argc,argv);
      if (_allSolutions.value() && _solutions.value()==-1) {
        _solutions.value(0);
      }
      if (_time_limit.value()) {
        _time.value(_time_limit.value());
      }
      if (_stat.value() && (_mode.value() == Gecode::SM_SOLUTION))
        _mode.value(Gecode::SM_STAT);
    }
 
    virtual void help(void) {
      std::cerr << "Gecode FlatZinc interpreter" << std::endl
                << " - FlatZinc text interface"
                << std::endl << std::endl;
      Gecode::BaseOptions::help();
    }
 
    int solutions(void) const { return _solutions.value(); }
    bool allSolutions(void) const { return _allSolutions.value(); }
    double threads(void) const { return _threads.value(); }
    bool free(void) const { return _free.value(); }
    unsigned int c_d(void) const { return _c_d.value(); }
    unsigned int a_d(void) const { return _a_d.value(); }
    unsigned long long int node(void) const { return _node.value(); }
    unsigned long long int fail(void) const { return _fail.value(); }
    double time(void) const { return _time.value(); }
    int seed(void) const { return _seed.value(); }
    double step(void) const { return _step.value(); }
    const char* output(void) const { return _output.value(); }
 
    Gecode::ScriptMode mode(void) const {
      return static_cast<Gecode::ScriptMode>(_mode.value());
    }
 
    double decay(void) const { return _decay.value(); }
    RestartMode restart(void) const {
      return static_cast<RestartMode>(_restart.value());
    }
    void restart(RestartMode rm) {
      _restart.value(rm);
    }
    double restart_base(void) const { return _r_base.value(); }
    void restart_base(double d) { _r_base.value(d); }
    unsigned int restart_scale(void) const { return _r_scale.value(); }
    void restart_scale(int i) { _r_scale.value(i); }
    unsigned long long int restart_limit(void) const { return _r_limit.value(); }
    bool nogoods(void) const { return _nogoods.value(); }
    unsigned int nogoods_limit(void) const { return _nogoods_limit.value(); }
    bool interrupt(void) const { return _interrupt.value(); }
 
#ifdef GECODE_HAS_CPPROFILER
 
    int profiler_id(void) const { return _profiler.execution_id(); }
    unsigned int profiler_port(void) const { return _profiler.port(); }
    bool profiler_info(void) const { return true; }
 
#endif
 
    void allSolutions(bool b) { _allSolutions.value(b); }
  };
 
  class BranchInformation : public SharedHandle {
  public:
    BranchInformation(void);
    BranchInformation(const BranchInformation& bi);
    void init(void);
    void add(BrancherGroup bg,
             const std::string& rel0,
             const std::string& rel1,
             const std::vector<std::string>& n);
    void print(const Brancher& b,
               unsigned int a, int i, int n, std::ostream& o) const;
#ifdef GECODE_HAS_FLOAT_VARS
    void print(const Brancher& b,
               unsigned int a, int i, const FloatNumBranch& nl,
               std::ostream& o) const;
#endif
    BranchInformation& operator =(const BranchInformation&) = default;
  };

  GECODE_FLATZINC_EXPORT
  extern Rnd defrnd;
 
  class FlatZincSpaceInitData;
  class BlackBoxAccess;

  class GECODE_FLATZINC_EXPORT FlatZincSpace : public Space {
  public:
    enum Meth {
      SAT, //< Solve as satisfaction problem
      MIN, //< Solve as minimization problem
      MAX  //< Solve as maximization problem
    };
  protected:
    FlatZincSpaceInitData* _initData;
    int intVarCount;
    int boolVarCount;
    int floatVarCount;
    int setVarCount;

    int _optVar;
    bool _optVarIsInt;

    Meth _method;

    unsigned int _lns;

    IntSharedArray _lnsInitialSolution;

    Rnd _random;

    AST::Array* _solveAnnotations;

    FlatZincSpace(FlatZincSpace&);
  private:
    friend class BlackBoxAccess;
    template<template<class> class Engine>
    void
    runEngine(std::ostream& out, const Printer& p,
              const FlatZincOptions& opt, Gecode::Support::Timer& t_total);
    template<template<class> class Engine,
             template<class, template<class> class> class Meta>
    void
    runMeta(std::ostream& out, const Printer& p,
            const FlatZincOptions& opt, Gecode::Support::Timer& t_total);
    void
    branchWithPlugin(AST::Node* ann);
  public:
    Gecode::IntVarArray iv;
    Gecode::IntVarArray iv_aux;

    Gecode::IntVarArray iv_lns;
 
    /* === Experimental `on_restart` support === */
    class OnRestartHandle : public SharedHandle {
    protected:
      class OnRestartData : public SharedHandle::Object {
        public:
        bool mark_complete = false;
        std::vector<std::pair<int, int>> uniform_range_int;
#ifdef GECODE_HAS_FLOAT_VARS
        std::vector<std::pair<FloatVal, FloatVal>> uniform_range_float;
#endif
        std::vector<bool> last_val_bool;
        std::vector<int> last_val_int;
#ifdef GECODE_HAS_SET_VARS
        std::vector<IntSet> last_val_set;
#endif
#ifdef GECODE_HAS_FLOAT_VARS
        std::vector<FloatVal> last_val_float;
#endif
        int on_restart_iv_sol = 0;
        int on_restart_bv_sol = 0;
        int on_restart_sv_sol = 0;
        int on_restart_fv_sol = 0;
        bool on_restart_status = false;
      };
    public:
      OnRestartHandle() : SharedHandle() {}
      OnRestartHandle(const OnRestartHandle& handle): SharedHandle(handle) {}
      OnRestartHandle& operator =(const OnRestartHandle& handle) {
        return static_cast<OnRestartHandle&>(SharedHandle::operator =(handle));
      }
      virtual ~OnRestartHandle() {};
 
      void init() {
        if (object() == nullptr) {
          object(new OnRestartData());
        }
      }
      bool initialized() const { return object() != nullptr; }
      OnRestartData& operator ()() {
        return *static_cast<OnRestartData*>(object());
      };
    };
    OnRestartHandle restart_data;
    Gecode::IntVarArray on_restart_iv;
    Gecode::BoolVarArray on_restart_bv;
#ifdef GECODE_HAS_SET_VARS
    Gecode::SetVarArray on_restart_sv;
#endif
#ifdef GECODE_HAS_FLOAT_VARS
    Gecode::FloatVarArray on_restart_fv;
#endif
    /* === End `on_restart` === */

    std::vector<bool> iv_introduced;
    int* iv_boolalias;
    Gecode::BoolVarArray bv;
    Gecode::BoolVarArray bv_aux;
    std::vector<bool> bv_introduced;
#ifdef GECODE_HAS_SET_VARS
    Gecode::SetVarArray sv;
    Gecode::SetVarArray sv_aux;
    std::vector<bool> sv_introduced;
#endif
#ifdef GECODE_HAS_FLOAT_VARS
    Gecode::FloatVarArray fv;
    Gecode::FloatVarArray fv_aux;
    std::vector<bool> fv_introduced;
    Gecode::FloatNum step;
#endif
    bool needAuxVars;
    FlatZincSpace(Rnd& random = defrnd);

    ~FlatZincSpace(void);

    void init(int intVars, int boolVars, int setVars, int floatVars);

    void newIntVar(IntVarSpec* vs);
    void aliasBool2Int(int iv, int bv);
    int aliasBool2Int(int iv);
    void newBoolVar(BoolVarSpec* vs);
    void newSetVar(SetVarSpec* vs);
    void newFloatVar(FloatVarSpec* vs);

    void postConstraints(std::vector<ConExpr*>& ces);

    void solve(AST::Array* annotation);
    void minimize(int var, bool isInt, AST::Array* annotation);
    void maximize(int var, bool isInt, AST::Array* annotation);

    void run(std::ostream& out, const Printer& p,
             const FlatZincOptions& opt, Gecode::Support::Timer& t_total);

    void print(std::ostream& out, const Printer& p) const;
#ifdef GECODE_HAS_CPPROFILER
    std::string getDomains(const Printer& p) const;
#endif
    void compare(const Space& s, std::ostream& out) const;
    void compare(const FlatZincSpace& s, std::ostream& out,
                 const Printer& p) const;

    void shrinkArrays(Printer& p);

    Meth method(void) const;

    int optVar(void) const;
    bool optVarIsInt(void) const;

    void createBranchers(Printer& p, AST::Node* ann,
                         FlatZincOptions& opt, bool ignoreUnknown,
                         std::ostream& err = std::cerr);

    AST::Array* solveAnnotations(void) const;

    BranchInformation branchInfo;

    virtual void constrain(const Space& s);
    virtual Gecode::Space* copy(void);
    virtual bool slave(const MetaInfo& mi);



    IntArgs arg2intargs(AST::Node* arg, int offset = 0);
    IntSharedArray arg2intsharedarray(AST::Node* arg, int offset = 0);
    IntArgs arg2boolargs(AST::Node* arg, int offset = 0);
    IntSharedArray arg2boolsharedarray(AST::Node* arg, int offset = 0);
    IntSet arg2intset(AST::Node* n);
    IntSetArgs arg2intsetargs(AST::Node* arg, int offset = 0);
    IntVarArgs arg2intvarargs(AST::Node* arg, int offset = 0);
    BoolVarArgs arg2boolvarargs(AST::Node* arg, int offset = 0, int siv=-1);
    BoolVar arg2BoolVar(AST::Node* n);
    IntVar arg2IntVar(AST::Node* n);
    TupleSet arg2tupleset(const IntArgs& a, int noOfVars);
    bool isBoolArray(AST::Node* b, int& singleInt);
#ifdef GECODE_HAS_SET_VARS
    SetVar arg2SetVar(AST::Node* n);
    SetVarArgs arg2setvarargs(AST::Node* arg, int offset = 0, int doffset = 0,
                              const IntSet& od=IntSet::empty);
#endif
#ifdef GECODE_HAS_FLOAT_VARS
    FloatValArgs arg2floatargs(AST::Node* arg, int offset = 0);
    FloatVar arg2FloatVar(AST::Node* n);
    FloatVarArgs arg2floatvarargs(AST::Node* arg, int offset = 0);
#endif
    IntPropLevel ann2ipl(AST::Node* ann);
    DFA getSharedDFA(DFA& a);
  };

  class GECODE_VTABLE_EXPORT Error {
  private:
    const std::string msg;
  public:
    Error(const std::string& where, const std::string& what)
    : msg(where+": "+what) {}
    Error(const std::string& where, const std::string& what, AST::Array *const ann)
    : msg(make_message(where, what, ann)) {}
    const std::string& toString(void) const { return msg; }
  private:
    static std::string make_message(const std::string &where, const std::string &what, AST::Array *const ann) {
      std::ostringstream result;
      result << where << ": " << what;
 
      std::vector<std::string> names = get_constraint_names(ann);
      if (names.size() > 1) {
        result << " in constraints ";
        for (unsigned int i = 0; i < names.size(); ++i) {
          result << '\"' << names[i] << '\"';
          if (i < names.size() - 1) {
            result << ",";
          }
          result << " ";
        }
      } else if (names.size() == 1) {
        result << " in constraint " << '\"' << names[0] << '\"';
      }
 
      return result.str();
    }
    static std::vector<std::string> get_constraint_names(AST::Array *const ann) {
      std::vector<std::string> result;
      if (ann) {
        for (const auto & i : ann->a) {
          if (i->isArray()) {
            auto nested_result = get_constraint_names(i->getArray());
            result.insert(result.end(), nested_result.begin(), nested_result.end());
          } else if (i->isCall("mzn_constraint_name")) {
            result.emplace_back(i->getCall()->args->getString());
          }
        }
      }
      return result;
    }
  };

  GECODE_FLATZINC_EXPORT
  FlatZincSpace* parse(const std::string& fileName,
                       Printer& p, std::ostream& err = std::cerr,
                       FlatZincSpace* fzs=nullptr, Rnd& rnd=defrnd);

  GECODE_FLATZINC_EXPORT
  FlatZincSpace* parse(std::istream& is,
                       Printer& p, std::ostream& err = std::cerr,
                       FlatZincSpace* fzs=nullptr, Rnd& rnd=defrnd);
 
}}
 
#endif
 
// STATISTICS: flatzinc-any