Something went wrong. Try again.
This repository has no description
Something went wrong. Try again.
57 kB · 1659 lines
C++
at develop
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- *//* * Main authors: * Christopher Mears <chris.mears@monash.edu> * * Copyright: * Christopher Mears, 2012 * * 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/kernel.hh>#include <gecode/int.hh>#include <gecode/int/branch.hh>
#ifdef GECODE_HAS_SET_VARS#include <gecode/set.hh>#include <gecode/set/branch.hh>#include <stdarg.h>#endif
#include <gecode/minimodel.hh>
#include "test/test.hh"
#include <vector>
/** * \namespace Test::LDSB * \brief Testing for LDSB */namespace Test { namespace LDSB {
using namespace Gecode;
/// Returns true iff a and b are equal (they have the same size and /// the same elements in the same positions). bool equal(const IntArgs& a, const IntArgs& b) { if (a.size() != b.size()) return false; for (int i = 0 ; i < a.size() ; ++i) if (a[i] != b[i]) return false; return true; }
#ifdef GECODE_HAS_SET_VARS /// Returns true iff a and b are equal (they have the same size and /// the same elements in the same positions). bool equal(const IntSetArgs& a, const IntSetArgs& b) { if (a.size() != b.size()) return false; for (int i = 0 ; i < a.size() ; ++i) { // Compare the two sets a[i] and b[i]. // Perhaps TODO: use Iter::Ranges::equal instead. if (a[i].size() != b[i].size()) return false; IntSetValues x(a[i]); IntSetValues y(b[i]); while (x() && y()) { if (x.val() != y.val()) return false; ++x; ++y; } } return true; }#endif
/** * \brief Checks found solutions against expected solutions * * Iterates through the solutions returned by the search engine and * checks each one against the array of expected solutions. The * order of solutions must be the same. Returns true if the * expected solutions match the found solutions exactly, otherwise * prints an explanation to standard error and returns false. */ template <class T, class VarArgsType> bool check(DFS<T>& e, std::vector<VarArgsType> expected) { int nexpected = expected.size(); for (int i = 0 ; i < nexpected ; ++i) { T* s = e.next(); if (s == nullptr) { if (opt.log) { olog << "Expected a solution but there are no more solutions." << std::endl; olog << "(Expected " << nexpected << " but only found " << i << ")" << std::endl; olog << "Expected: " << expected[i] << std::endl; } return false; } if (!equal(s->solution(), expected[i])) { if (opt.log) { olog << "Solution does not match expected." << std::endl; olog << "Solution: " << s->solution() << std::endl; olog << "Expected: " << expected[i] << std::endl; } return false; } delete s; } T* s = e.next(); if (s != nullptr) { if (opt.log) { olog << "More solutions than expected:" << std::endl; olog << "(Expected only " << nexpected << ")" << std::endl; olog << s->solution() << std::endl; } return false; }
// Nothing went wrong. return true; }
/// %Test space class OneArray : public Space { public: /// Variables IntVarArray xs; /// Constructor for creation OneArray(int n, int l, int u) : xs(*this,n,l,u) { } /// Constructor for cloning \a s OneArray(OneArray& s) : Space(s) { xs.update(*this,s.xs); } /// Copy during cloning virtual Space* copy(void) { return new OneArray(*this); } /// Return the solution as IntArgs IntArgs solution(void) { IntArgs a(xs.size()); for (int i = 0 ; i < a.size() ; ++i) a[i] = xs[i].val(); return a; } /// Expected solutions virtual IntArgs* expectedSolutions(void) { return nullptr; } };
#ifdef GECODE_HAS_SET_VARS /// %Test space (set version) class OneArraySet : public Space { public: /// Variables SetVarArray xs; /// Constructor for creation OneArraySet(int n, int l, int u) : xs(*this,n, IntSet::empty, l,u) { } /// Constructor for cloning \a s OneArraySet(OneArraySet& s) : Space(s) { xs.update(*this,s.xs); } /// Copy during cloning virtual Space* copy(void) { return new OneArraySet(*this); } /// Return the solution as IntSetArgs IntSetArgs solution(void) { IntSetArgs a(xs.size()); for (int i = 0 ; i < a.size() ; ++i) { SetVarGlbRanges glbranges(xs[i]); a[i] = IntSet(glbranges); } return a; } /// Expected solutions virtual IntSetArgs* expectedSolutions(void) { return nullptr; } };#endif
/// %Test for %LDSB infrastructure template <class T> class LDSB : public Base { public: /// Recomputation distance unsigned int c_d; /// Adaptation distance unsigned int a_d; /// Initialize test LDSB(std::string label, unsigned int c=0, unsigned int a=0) : Test::Base("LDSB::" + label), c_d(c), a_d(a) {} /// Perform actual tests bool run(void) { OneArray *s = new OneArray(T::n, T::l, T::u); T::setup(*s, s->xs); Search::Options o = Search::Options::def; if (c_d != 0) o.c_d = c_d; if (a_d != 0) o.a_d = a_d; DFS<OneArray> e(s,o); bool r = check(e, T::expectedSolutions()); delete s; return r; } };
#ifdef GECODE_HAS_SET_VARS /// %Test for %LDSB infrastructure template <class T> class LDSBSet : public Base { public: /// Recomputation distance unsigned int c_d; /// Adaptation distance unsigned int a_d; /// Initialize test LDSBSet(std::string label, unsigned int c=0, unsigned int a=0) : Test::Base("LDSB::" + label), c_d(c), a_d(a) {} /// Perform actual tests bool run(void) { OneArraySet *s = new OneArraySet(T::n, T::l, T::u); T::setup(*s, s->xs); Search::Options o = Search::Options::def; if (c_d != 0) o.c_d = c_d; if (a_d != 0) o.a_d = a_d; DFS<OneArraySet> e(s,o); bool r = check(e, T::expectedSolutions()); delete s; return r; } };#endif
// Test cases
/// %Test for variable symmetry class VarSym1 { public: /// Number of variables static const int n = 4; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 3; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { Symmetries syms; IntArgs indices({0,1,2,3}); syms << VariableSymmetry(xs, indices); distinct(home, xs); branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), syms); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({0,1,2,3})); return expected; } };
/// %Test for variable symmetry class VarSym1b { public: /// Number of variables static const int n = 4; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 3; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { distinct(home, xs); Symmetries syms; syms << VariableSymmetry(xs); branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), syms); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({0,1,2,3})); return expected; } };
/// %Test for variable symmetry class VarSym2 { public: /// Number of variables static const int n = 4; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 3; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { Symmetries syms; IntArgs indices({0,1,2,3}); syms << VariableSymmetry(xs); branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), syms); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({0,0,0,0})); expected.push_back(IntArgs({0,0,0,1})); expected.push_back(IntArgs({0,0,0,2})); expected.push_back(IntArgs({0,0,0,3})); expected.push_back(IntArgs({0,0,1,1})); expected.push_back(IntArgs({0,0,1,2})); expected.push_back(IntArgs({0,0,1,3})); expected.push_back(IntArgs({0,0,2,2})); expected.push_back(IntArgs({0,0,2,3})); expected.push_back(IntArgs({0,0,3,3})); expected.push_back(IntArgs({0,1,1,1})); expected.push_back(IntArgs({0,1,1,2})); expected.push_back(IntArgs({0,1,1,3})); expected.push_back(IntArgs({0,1,2,2})); expected.push_back(IntArgs({0,1,2,3})); expected.push_back(IntArgs({0,1,3,3})); expected.push_back(IntArgs({0,2,2,2})); expected.push_back(IntArgs({0,2,2,3})); expected.push_back(IntArgs({0,2,3,3})); expected.push_back(IntArgs({0,3,3,3})); expected.push_back(IntArgs({1,1,1,1})); expected.push_back(IntArgs({1,1,1,2})); expected.push_back(IntArgs({1,1,1,3})); expected.push_back(IntArgs({1,1,2,2})); expected.push_back(IntArgs({1,1,2,3})); expected.push_back(IntArgs({1,1,3,3})); expected.push_back(IntArgs({1,2,2,2})); expected.push_back(IntArgs({1,2,2,3})); expected.push_back(IntArgs({1,2,3,3})); expected.push_back(IntArgs({1,3,3,3})); expected.push_back(IntArgs({2,2,2,2})); expected.push_back(IntArgs({2,2,2,3})); expected.push_back(IntArgs({2,2,3,3})); expected.push_back(IntArgs({2,3,3,3})); expected.push_back(IntArgs({3,3,3,3})); return expected; } };
/// %Test for variable symmetry class VarSym3 { public: /// Number of variables static const int n = 4; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 3; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { Symmetries syms; distinct(home, xs); syms << VariableSymmetry(IntVarArgs() << xs[0] << xs[1]); branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), syms); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({0,1,2,3})); expected.push_back(IntArgs({0,1,3,2})); expected.push_back(IntArgs({0,2,1,3})); expected.push_back(IntArgs({0,2,3,1})); expected.push_back(IntArgs({0,3,1,2})); expected.push_back(IntArgs({0,3,2,1})); expected.push_back(IntArgs({1,2,0,3})); expected.push_back(IntArgs({1,2,3,0})); expected.push_back(IntArgs({1,3,0,2})); expected.push_back(IntArgs({1,3,2,0})); expected.push_back(IntArgs({2,3,0,1})); expected.push_back(IntArgs({2,3,1,0})); return expected; } };
/// %Test for variable symmetry class VarSym4 { public: /// Number of variables static const int n = 3; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 2; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { distinct(home, xs); Symmetries s; IntVarArgs symvars; symvars << xs[0]; s << VariableSymmetry(symvars); branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({0,1,2})); expected.push_back(IntArgs({0,2,1})); expected.push_back(IntArgs({1,0,2})); expected.push_back(IntArgs({1,2,0})); expected.push_back(IntArgs({2,0,1})); expected.push_back(IntArgs({2,1,0})); return expected; } };
/// %Test for variable symmetry class VarSym5 { public: /// Number of variables static const int n = 4; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 3; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { distinct(home, xs); Matrix<IntVarArray> m(xs, 4, 1); Symmetries s; s << VariableSymmetry(m.slice(0,2, 0,1)); s << VariableSymmetry(m.slice(2,4, 0,1)); branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({0,1,2,3})); expected.push_back(IntArgs({0,2,1,3})); expected.push_back(IntArgs({0,3,1,2})); expected.push_back(IntArgs({1,2,0,3})); expected.push_back(IntArgs({1,3,0,2})); expected.push_back(IntArgs({2,3,0,1})); return expected; } };
/// %Test for matrix symmetry class MatSym1 { public: /// Number of variables static const int n = 6; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 1; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { Matrix<IntVarArray> m(xs, 2, 3); Symmetries s; s << rows_interchange(m); branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({0,0, 0,0, 0,0})); expected.push_back(IntArgs({0,0, 0,0, 0,1})); expected.push_back(IntArgs({0,0, 0,0, 1,0})); expected.push_back(IntArgs({0,0, 0,0, 1,1})); expected.push_back(IntArgs({0,0, 0,1, 0,0})); expected.push_back(IntArgs({0,0, 0,1, 0,1})); expected.push_back(IntArgs({0,0, 0,1, 1,0})); expected.push_back(IntArgs({0,0, 0,1, 1,1})); expected.push_back(IntArgs({0,0, 1,0, 1,0})); expected.push_back(IntArgs({0,0, 1,0, 1,1})); expected.push_back(IntArgs({0,0, 1,1, 1,1})); expected.push_back(IntArgs({0,1, 0,0, 0,0})); expected.push_back(IntArgs({0,1, 0,0, 0,1})); expected.push_back(IntArgs({0,1, 0,0, 1,0})); expected.push_back(IntArgs({0,1, 0,0, 1,1})); expected.push_back(IntArgs({0,1, 0,1, 0,0})); expected.push_back(IntArgs({0,1, 0,1, 0,1})); expected.push_back(IntArgs({0,1, 0,1, 1,0})); expected.push_back(IntArgs({0,1, 0,1, 1,1})); expected.push_back(IntArgs({0,1, 1,0, 1,0})); expected.push_back(IntArgs({0,1, 1,0, 1,1})); expected.push_back(IntArgs({0,1, 1,1, 1,1})); expected.push_back(IntArgs({1,0, 1,0, 1,0})); expected.push_back(IntArgs({1,0, 1,0, 1,1})); expected.push_back(IntArgs({1,0, 1,1, 1,1})); expected.push_back(IntArgs({1,1, 1,1, 1,1})); return expected; } };
/// %Test for matrix symmetry class MatSym2 { public: /// Number of variables static const int n = 6; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 1; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { Matrix<IntVarArray> m(xs, 2, 3); Symmetries s; s << columns_interchange(m); branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({0,0, 0,0, 0,0})); expected.push_back(IntArgs({0,0, 0,0, 0,1})); expected.push_back(IntArgs({0,0, 0,0, 1,1})); expected.push_back(IntArgs({0,0, 0,1, 0,0})); expected.push_back(IntArgs({0,0, 0,1, 0,1})); expected.push_back(IntArgs({0,0, 0,1, 1,0})); expected.push_back(IntArgs({0,0, 0,1, 1,1})); expected.push_back(IntArgs({0,0, 1,1, 0,0})); expected.push_back(IntArgs({0,0, 1,1, 0,1})); expected.push_back(IntArgs({0,0, 1,1, 1,1})); expected.push_back(IntArgs({0,1, 0,0, 0,0})); expected.push_back(IntArgs({0,1, 0,0, 0,1})); expected.push_back(IntArgs({0,1, 0,0, 1,0})); expected.push_back(IntArgs({0,1, 0,0, 1,1})); expected.push_back(IntArgs({0,1, 0,1, 0,0})); expected.push_back(IntArgs({0,1, 0,1, 0,1})); expected.push_back(IntArgs({0,1, 0,1, 1,0})); expected.push_back(IntArgs({0,1, 0,1, 1,1})); expected.push_back(IntArgs({0,1, 1,0, 0,0})); expected.push_back(IntArgs({0,1, 1,0, 0,1})); expected.push_back(IntArgs({0,1, 1,0, 1,0})); expected.push_back(IntArgs({0,1, 1,0, 1,1})); expected.push_back(IntArgs({0,1, 1,1, 0,0})); expected.push_back(IntArgs({0,1, 1,1, 0,1})); expected.push_back(IntArgs({0,1, 1,1, 1,0})); expected.push_back(IntArgs({0,1, 1,1, 1,1})); expected.push_back(IntArgs({1,1, 0,0, 0,0})); expected.push_back(IntArgs({1,1, 0,0, 0,1})); expected.push_back(IntArgs({1,1, 0,0, 1,1})); expected.push_back(IntArgs({1,1, 0,1, 0,0})); expected.push_back(IntArgs({1,1, 0,1, 0,1})); expected.push_back(IntArgs({1,1, 0,1, 1,0})); expected.push_back(IntArgs({1,1, 0,1, 1,1})); expected.push_back(IntArgs({1,1, 1,1, 0,0})); expected.push_back(IntArgs({1,1, 1,1, 0,1})); expected.push_back(IntArgs({1,1, 1,1, 1,1})); return expected; } };
/// %Test for matrix symmetry class MatSym3 { public: /// Number of variables static const int n = 6; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 1; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { Matrix<IntVarArray> m(xs, 2, 3); Symmetries s; s << rows_interchange(m); s << columns_interchange(m); branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({0,0, 0,0, 0,0})); expected.push_back(IntArgs({0,0, 0,0, 0,1})); expected.push_back(IntArgs({0,0, 0,0, 1,1})); expected.push_back(IntArgs({0,0, 0,1, 0,0})); expected.push_back(IntArgs({0,0, 0,1, 0,1})); expected.push_back(IntArgs({0,0, 0,1, 1,0})); expected.push_back(IntArgs({0,0, 0,1, 1,1})); expected.push_back(IntArgs({0,0, 1,1, 1,1})); expected.push_back(IntArgs({0,1, 0,0, 0,0})); expected.push_back(IntArgs({0,1, 0,0, 0,1})); expected.push_back(IntArgs({0,1, 0,0, 1,0})); expected.push_back(IntArgs({0,1, 0,0, 1,1})); expected.push_back(IntArgs({0,1, 0,1, 0,0})); expected.push_back(IntArgs({0,1, 0,1, 0,1})); expected.push_back(IntArgs({0,1, 0,1, 1,0})); expected.push_back(IntArgs({0,1, 0,1, 1,1})); expected.push_back(IntArgs({0,1, 1,0, 1,0})); expected.push_back(IntArgs({0,1, 1,0, 1,1})); expected.push_back(IntArgs({0,1, 1,1, 1,1})); expected.push_back(IntArgs({1,1, 1,1, 1,1})); return expected; } };
/// %Test for matrix symmetry class MatSym4 { public: /// Number of variables static const int n = 4; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 1; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { Matrix<IntVarArray> m(xs, 1, 4); Symmetries s; s << rows_reflect(m); branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({0, 0, 0, 0})); expected.push_back(IntArgs({0, 0, 0, 1})); expected.push_back(IntArgs({0, 0, 1, 0})); expected.push_back(IntArgs({0, 0, 1, 1})); expected.push_back(IntArgs({0, 1, 0, 0})); expected.push_back(IntArgs({0, 1, 0, 1})); expected.push_back(IntArgs({0, 1, 1, 0})); expected.push_back(IntArgs({0, 1, 1, 1})); expected.push_back(IntArgs({1, 0, 0, 1})); expected.push_back(IntArgs({1, 0, 1, 1})); expected.push_back(IntArgs({1, 1, 1, 1})); return expected; } };
/// %Test for variable sequence symmetry class SimIntVarSym1 { public: /// Number of variables static const int n = 12; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 3; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { Matrix<IntVarArray> m(xs, 3, 4); // The values in the first column are distinct. distinct(home, m.col(0)); // Each row sums to 3. for (int i = 0 ; i < 4 ; ++i) linear(home, m.row(i), IRT_EQ, 3);
// Rows are interchangeable. Symmetries s; s << VariableSequenceSymmetry(xs, 3); branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({0,0,3, 1,0,2, 2,0,1, 3,0,0})); expected.push_back(IntArgs({0,0,3, 1,0,2, 2,1,0, 3,0,0})); expected.push_back(IntArgs({0,0,3, 1,1,1, 2,0,1, 3,0,0})); expected.push_back(IntArgs({0,0,3, 1,1,1, 2,1,0, 3,0,0})); expected.push_back(IntArgs({0,0,3, 1,2,0, 2,0,1, 3,0,0})); expected.push_back(IntArgs({0,0,3, 1,2,0, 2,1,0, 3,0,0})); expected.push_back(IntArgs({0,1,2, 1,0,2, 2,0,1, 3,0,0})); expected.push_back(IntArgs({0,1,2, 1,0,2, 2,1,0, 3,0,0})); expected.push_back(IntArgs({0,1,2, 1,1,1, 2,0,1, 3,0,0})); expected.push_back(IntArgs({0,1,2, 1,1,1, 2,1,0, 3,0,0})); expected.push_back(IntArgs({0,1,2, 1,2,0, 2,0,1, 3,0,0})); expected.push_back(IntArgs({0,1,2, 1,2,0, 2,1,0, 3,0,0})); expected.push_back(IntArgs({0,2,1, 1,0,2, 2,0,1, 3,0,0})); expected.push_back(IntArgs({0,2,1, 1,0,2, 2,1,0, 3,0,0})); expected.push_back(IntArgs({0,2,1, 1,1,1, 2,0,1, 3,0,0})); expected.push_back(IntArgs({0,2,1, 1,1,1, 2,1,0, 3,0,0})); expected.push_back(IntArgs({0,2,1, 1,2,0, 2,0,1, 3,0,0})); expected.push_back(IntArgs({0,2,1, 1,2,0, 2,1,0, 3,0,0})); expected.push_back(IntArgs({0,3,0, 1,0,2, 2,0,1, 3,0,0})); expected.push_back(IntArgs({0,3,0, 1,0,2, 2,1,0, 3,0,0})); expected.push_back(IntArgs({0,3,0, 1,1,1, 2,0,1, 3,0,0})); expected.push_back(IntArgs({0,3,0, 1,1,1, 2,1,0, 3,0,0})); expected.push_back(IntArgs({0,3,0, 1,2,0, 2,0,1, 3,0,0})); expected.push_back(IntArgs({0,3,0, 1,2,0, 2,1,0, 3,0,0})); return expected; } };
/// %Test for variable sequence symmetry class SimIntVarSym2 { /// Number of rows static const int nrows = 4; /// Number of columns static const int ncols = 3; public: /// Number of variables static const int n = nrows*ncols; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 3; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { Matrix<IntVarArray> m(xs, 3, 4); // The values in the first column are distinct. distinct(home, m.col(0)); // Each row sums to 3. for (int i = 0 ; i < nrows ; ++i) linear(home, m.row(i), IRT_EQ, 3);
Symmetries s;
IntArgs a = IntArgs::create(n, 0); // Rows are interchangeable. s << VariableSequenceSymmetry(xs, 3); // Elements (i,1) and (i,2) in row i are interchangeable, // separately for each row. for (int i = 0 ; i < nrows ; i++) { IntVarArgs symvars; symvars << m(1,i) << m(2,i); s << VariableSymmetry(symvars); } branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({0,0,3, 1,0,2, 2,0,1, 3,0,0})); expected.push_back(IntArgs({0,0,3, 1,1,1, 2,0,1, 3,0,0})); expected.push_back(IntArgs({0,1,2, 1,0,2, 2,0,1, 3,0,0})); expected.push_back(IntArgs({0,1,2, 1,1,1, 2,0,1, 3,0,0})); return expected; } };
/// %Test for value sequence symmetry class SimIntValSym1 { public: /// Number of variables static const int n = 2; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 6; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { rel(home, xs[0] + xs[1] == 6); // Values 0,1,2 are symmetric with 6,5,4. IntArgs values({0,1,2, 6,5,4}); Symmetries s; s << ValueSequenceSymmetry(values, 3); branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({0,6})); expected.push_back(IntArgs({1,5})); expected.push_back(IntArgs({2,4})); expected.push_back(IntArgs({3,3})); return expected; } };
/// %Test for value sequence symmetry class SimIntValSym2 { public: /// Number of variables static const int n = 3; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 8; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { TupleSet tuples(3); tuples.add({1,1,1}).add({4,4,4}).add({7,7,7}) .add({0,1,5}).add({0,1,8}).add({3,4,2}) .add({3,4,8}).add({6,7,2}).add({6,7,5}) .finalize(); extensional(home, xs, tuples);
// Values 0,1,2 are symmetric with 3,4,5, and with 6,7,8. IntArgs values({0,1,2, 3,4,5, 6,7,8}); Symmetries s; s << ValueSequenceSymmetry(values, 3); branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({0,1,5})); expected.push_back(IntArgs({1,1,1})); return expected; } };
/// %Test for value sequence symmetry class SimIntValSym3 { public: /// Number of variables static const int n = 2; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 6; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { rel(home, xs[0] + xs[1] == 6); Symmetries s; // Values 0,1,2 are symmetric with 6,5,4. s << values_reflect(0,6); branch(home, xs, INT_VAR_NONE(), INT_VAL_MED(), s); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({3,3})); expected.push_back(IntArgs({2,4})); expected.push_back(IntArgs({1,5})); expected.push_back(IntArgs({0,6})); return expected; } };
/// %Test for value symmetry class ValSym1 { public: /// Number of variables static const int n = 4; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 3; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { distinct(home, xs); Symmetries s; IntArgs indices({0,1,2,3}); s << ValueSymmetry(indices); branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({0,1,2,3})); return expected; } };
/// %Test for value symmetry class ValSym1b { public: /// Number of variables static const int n = 4; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 3; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { distinct(home, xs); Symmetries s; s << ValueSymmetry(xs[0]); branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({0,1,2,3})); return expected; } };
/// %Test for value symmetry class ValSym1c { public: /// Number of variables static const int n = 4; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 3; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { distinct(home, xs); Symmetries s; s << ValueSymmetry(xs[0]); branch(home, xs, INT_VAR_NONE(), INT_VAL_MAX(), s); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({3,2,1,0})); return expected; } };
/// %Test for value symmetry class ValSym2 { public: /// Number of variables static const int n = 4; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 3; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { Symmetries s; IntArgs indices({0,1,2,3}); s << ValueSymmetry(indices); branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({0,0,0,0})); expected.push_back(IntArgs({0,0,0,1})); expected.push_back(IntArgs({0,0,1,0})); expected.push_back(IntArgs({0,0,1,1})); expected.push_back(IntArgs({0,0,1,2})); expected.push_back(IntArgs({0,1,0,0})); expected.push_back(IntArgs({0,1,0,1})); expected.push_back(IntArgs({0,1,0,2})); expected.push_back(IntArgs({0,1,1,0})); expected.push_back(IntArgs({0,1,1,1})); expected.push_back(IntArgs({0,1,1,2})); expected.push_back(IntArgs({0,1,2,0})); expected.push_back(IntArgs({0,1,2,1})); expected.push_back(IntArgs({0,1,2,2})); expected.push_back(IntArgs({0,1,2,3})); return expected; } };
/// %Test for value symmetry class ValSym2b { public: /// Number of variables static const int n = 4; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 3; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { Symmetries s; s << ValueSymmetry(xs[0]); branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({0,0,0,0})); expected.push_back(IntArgs({0,0,0,1})); expected.push_back(IntArgs({0,0,1,0})); expected.push_back(IntArgs({0,0,1,1})); expected.push_back(IntArgs({0,0,1,2})); expected.push_back(IntArgs({0,1,0,0})); expected.push_back(IntArgs({0,1,0,1})); expected.push_back(IntArgs({0,1,0,2})); expected.push_back(IntArgs({0,1,1,0})); expected.push_back(IntArgs({0,1,1,1})); expected.push_back(IntArgs({0,1,1,2})); expected.push_back(IntArgs({0,1,2,0})); expected.push_back(IntArgs({0,1,2,1})); expected.push_back(IntArgs({0,1,2,2})); expected.push_back(IntArgs({0,1,2,3})); return expected; } };
/// %Test for value symmetry class ValSym3 { public: /// Number of variables static const int n = 4; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 3; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { distinct(home, xs); Symmetries s; IntArgs indices({0,1}); s << ValueSymmetry(indices); branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({0,1,2,3})); expected.push_back(IntArgs({0,1,3,2})); expected.push_back(IntArgs({0,2,1,3})); expected.push_back(IntArgs({0,2,3,1})); expected.push_back(IntArgs({0,3,1,2})); expected.push_back(IntArgs({0,3,2,1})); expected.push_back(IntArgs({2,0,1,3})); expected.push_back(IntArgs({2,0,3,1})); expected.push_back(IntArgs({2,3,0,1})); expected.push_back(IntArgs({3,0,1,2})); expected.push_back(IntArgs({3,0,2,1})); expected.push_back(IntArgs({3,2,0,1})); return expected; } };
/// %Test for value symmetry class ValSym4 { public: /// Number of variables static const int n = 3; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 2; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { distinct(home, xs); Symmetries s; IntArgs indices({0}); s << ValueSymmetry(indices); branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({0,1,2})); expected.push_back(IntArgs({0,2,1})); expected.push_back(IntArgs({1,0,2})); expected.push_back(IntArgs({1,2,0})); expected.push_back(IntArgs({2,0,1})); expected.push_back(IntArgs({2,1,0})); return expected; } };
/// %Test for value symmetry class ValSym5 { public: /// Number of variables static const int n = 4; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 3; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { distinct(home, xs); Symmetries s; IntArgs indices0({0,1}); IntArgs indices1({2,3}); s << ValueSymmetry(indices0); s << ValueSymmetry(indices1); branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({0,1,2,3})); expected.push_back(IntArgs({0,2,1,3})); expected.push_back(IntArgs({0,2,3,1})); expected.push_back(IntArgs({2,0,1,3})); expected.push_back(IntArgs({2,0,3,1})); expected.push_back(IntArgs({2,3,0,1})); return expected; } };
/// %Test for variable and value symmetry class VarValSym1 { public: /// Number of variables static const int n = 4; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 3; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { Symmetries s; s << VariableSymmetry(xs); s << ValueSymmetry(IntArgs::create(4,0)); branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({0,0,0,0})); expected.push_back(IntArgs({0,0,0,1})); expected.push_back(IntArgs({0,0,1,1})); expected.push_back(IntArgs({0,0,1,2})); expected.push_back(IntArgs({0,1,1,1})); expected.push_back(IntArgs({0,1,1,2})); expected.push_back(IntArgs({0,1,2,2})); // This solution is symmetric to the previous one. expected.push_back(IntArgs({0,1,2,3})); return expected; } };
/// %Test for %LDSB infrastructure with %Latin square problem class LDSBLatin : public Base { public: /// %Latin square space class Latin : public Space { public: IntVarArray xs; Latin(int n = 4) : xs(*this, n*n, 1, n) { Matrix<IntVarArray> m(xs, n, n); for (int i = 0 ; i < n ; i++) { distinct(*this, m.col(i)); distinct(*this, m.row(i)); } Symmetries s; s << rows_interchange(m); s << columns_interchange(m); s << ValueSymmetry(IntSet(1,n)); branch(*this, xs, INT_VAR_NONE(), INT_VAL_MIN(), s); } // Search support. Latin(Latin& s) : Space(s) { xs.update(*this, s.xs); } virtual Space* copy(void) { return new Latin(*this); } IntArgs solution(void) { IntArgs a(xs.size()); for (int i = 0 ; i < a.size() ; ++i) a[i] = xs[i].val(); return a; }
/// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({1,2,3,4, 2,1,4,3, 3,4,1,2, 4,3,2,1})); expected.push_back(IntArgs({1,2,3,4, 2,1,4,3, 3,4,2,1, 4,3,1,2})); expected.push_back(IntArgs({1,2,3,4, 2,3,4,1, 3,4,1,2, 4,1,2,3})); expected.push_back(IntArgs({1,2,3,4, 2,4,1,3, 3,1,4,2, 4,3,2,1})); return expected; } }; /// Initialize test LDSBLatin(std::string label) : Test::Base("LDSB::" + label) {} /// Perform actual tests bool run(void) { Latin *s = new Latin(); DFS<Latin> e(s); bool r = check(e, Latin::expectedSolutions()); delete s; return r; } };
/* This test should fail if the recomputation-handling does not work * properly. * * Why recomputation can be a problem * ================================== * * Every branch point in LDSB is binary, with a left and a right * branch. Whenever backtracking happens -- when a right branch is * explored -- LDSB computes a set of symmetric literals to * exclude. * * !!! This calculation may depend on the current domains of the * !!! variables. * * During recomputation, parts of the search tree are replayed. To * be specific, the branching constraints are posted, but no * propagation happens. This means that at a given branch point, * the domains during recomputation may be different (weaker) than * they were the first time during search. * * !!! This *cannot* cause solutions to be missed --- LDSB will not * !!! be incorrect --- but it *does* change what will be pruned. * * If recomputation is not handled properly, the difference in * domains will cause extra solutions to be found. This is a result * of symmetries failing to be broken. * */
/// %Test for handling of recomputation class Recomputation { public: /// Number of variables static const int n = 4; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 1; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { TupleSet t(2); t.add({0,0}).add({1,1}).finalize(); IntVarArgs va; va << xs[0] << xs[2]; extensional(home, va, t); Symmetries syms; syms << VariableSequenceSymmetry(xs, 2); branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), syms); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({0,0,0,0})); expected.push_back(IntArgs({0,0,0,1}));
// This is the solution that will be found if recomputation is // not handled. After branching on x[0]=0, we try x[1]=0. When // x[1]=0 backtracks, the symmetry [x[0],x[1]] <-> [x[2],x[3]] // is active --- but only after propagation! (Without // propagation, we do not have x[2]=0.) If propagation happens, // we know that symmetry is active and we can post x[3]!=0. If // it doesn't, we don't use the symmetry and we find a solution // where x[3]=0.
// expected.push_back(IntArgs({0,1,0,0}));
expected.push_back(IntArgs({0,1,0,1}));
expected.push_back(IntArgs({1,0,1,0})); expected.push_back(IntArgs({1,0,1,1})); expected.push_back(IntArgs({1,1,1,1})); return expected; } };
double position(const Space& home, IntVar x, int i) { (void) home; (void) x; return i; }
/// %Test tiebreaking variable heuristic. class TieBreak { public: /// Number of variables static const int n = 4; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 3; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { Symmetries syms; IntArgs indices({0,1,2,3}); syms << VariableSymmetry(xs, indices); distinct(home, xs); // This redundant constraint is to trick the variable // heuristic. rel(home, xs[1] != xs[2]); // xs[1] and xs[2] have higher degree than the others, so they // are considered first. xs[2] is higher than x[1] by the merit // function, so it is assigned first. Now all remaining // variables have the same degree, so they are searched in // reverse order (according to the merit function). So, the // solution found is {3, 2, 0, 1}. branch(home, xs, tiebreak(INT_VAR_DEGREE_MAX(), INT_VAR_MERIT_MAX(position)), INT_VAL_MIN(), syms); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({3,2,0,1})); return expected; } };
#ifdef GECODE_HAS_SET_VARS /// Convenient way to make IntSetArgs IntSetArgs ISA(int n, ...) { IntSetArgs sets; va_list args; va_start(args, n); int i = 0; IntArgs a; while (i < n) { int x = va_arg(args,int); if (x == -1) { i++; sets << IntSet(a); a = IntArgs(); } else { a << x; } } va_end(args); return sets; }
/// %Test for set variable symmetry class SetVarSym1 { public: /// Number of variables static const int n = 2; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 1; /// Setup problem constraints and symmetries static void setup(Home home, SetVarArray& xs) { Symmetries syms; syms << VariableSymmetry(xs); branch(home, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms); } /// Compute list of expected solutions static std::vector<IntSetArgs> expectedSolutions(void) { static std::vector<IntSetArgs> expected; expected.clear(); expected.push_back(ISA(2, 0,1,-1, 0,1,-1)); expected.push_back(ISA(2, 0,1,-1, 0, -1)); expected.push_back(ISA(2, 0,1,-1, 1,-1)); expected.push_back(ISA(2, 0,1,-1, -1)); expected.push_back(ISA(2, 0, -1, 0,1,-1)); expected.push_back(ISA(2, 0, -1, 0, -1)); expected.push_back(ISA(2, 0, -1, 1,-1)); expected.push_back(ISA(2, 0, -1, -1)); // expected.push_back(ISA(2, 1,-1, 0,1,-1)); // expected.push_back(ISA(2, 1,-1, 0, -1)); expected.push_back(ISA(2, 1,-1, 1,-1)); expected.push_back(ISA(2, 1,-1, -1)); // expected.push_back(ISA(2, -1, 0,1,-1)); // expected.push_back(ISA(2, -1, 0, -1)); // expected.push_back(ISA(2, -1, 1,-1)); expected.push_back(ISA(2, -1, -1)); return expected; } };
/* * This tests the special handling of value symmetries on set * values. Look at the third solution (commented out) below. The * first variable has been assigned to {0,1}. If the value symmetry * is not handled specially, then we will consider the value * symmetry broken because the search has touched each value. * However, because both values have been assigned to the same * variable, 0 and 1 are still symmetric. Therefore, the third * solution is symmetric to the second one and should be excluded. */
/// %Test for set value symmetry class SetValSym1 { public: /// Number of variables static const int n = 2; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 1; /// Setup problem constraints and symmetries static void setup(Home home, SetVarArray& xs) { Symmetries syms; syms << ValueSymmetry(IntArgs({0,1})); branch(home, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms); } /// Compute list of expected solutions static std::vector<IntSetArgs> expectedSolutions(void) { static std::vector<IntSetArgs> expected; expected.clear(); expected.push_back(ISA(2, 0,1,-1, 0,1,-1)); expected.push_back(ISA(2, 0,1,-1, 0, -1)); // expected.push_back(ISA(2, 0,1,-1, 1,-1)); // XXXXX bad solution expected.push_back(ISA(2, 0,1,-1, -1)); expected.push_back(ISA(2, 0, -1, 0,1,-1)); expected.push_back(ISA(2, 0, -1, 0, -1)); expected.push_back(ISA(2, 0, -1, 1,-1)); expected.push_back(ISA(2, 0, -1, -1)); // expected.push_back(ISA(2, 1,-1, 0,1,-1)); // expected.push_back(ISA(2, 1,-1, 0, -1)); // expected.push_back(ISA(2, 1,-1, 1,-1)); // expected.push_back(ISA(2, 1,-1, -1)); expected.push_back(ISA(2, -1, 0,1,-1)); expected.push_back(ISA(2, -1, 0, -1)); // expected.push_back(ISA(2, -1, 1,-1)); expected.push_back(ISA(2, -1, -1)); return expected; } };
/// %Test for set value symmetry class SetValSym2 { public: /// Number of variables static const int n = 3; /// Lower bound of values static const int l = 1; /// Upper bound of values static const int u = 4; /// Setup problem constraints and symmetries static void setup(Home home, SetVarArray& xs) { Symmetries syms; syms << ValueSymmetry(IntArgs({1,2,3,4})); for (int i = 0 ; i < 3 ; i++) cardinality(home, xs[i], 1, 1); branch(home, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms); } /// Compute list of expected solutions static std::vector<IntSetArgs> expectedSolutions(void) { static std::vector<IntSetArgs> expected; expected.clear(); expected.push_back(ISA(3, 1,-1, 1,-1, 1,-1)); expected.push_back(ISA(3, 1,-1, 1,-1, 2,-1)); expected.push_back(ISA(3, 1,-1, 2,-1, 1,-1)); expected.push_back(ISA(3, 1,-1, 2,-1, 2,-1)); expected.push_back(ISA(3, 1,-1, 2,-1, 3,-1)); return expected; } };
/// %Test for set variable sequence symmetry class SetVarSeqSym1 { public: /// Number of variables static const int n = 4; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 1; /// Setup problem constraints and symmetries static void setup(Home home, SetVarArray& xs) { Symmetries syms; syms << VariableSequenceSymmetry(xs,2); rel(home, xs[0], SOT_INTER, xs[1], SRT_EQ, IntSet::empty); rel(home, xs[2], SOT_INTER, xs[3], SRT_EQ, IntSet::empty); for (int i = 0 ; i < 4 ; i++) cardinality(home, xs[i], 1, 1); branch(home, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms); } /// Compute list of expected solutions static std::vector<IntSetArgs> expectedSolutions(void) { static std::vector<IntSetArgs> expected; expected.clear(); expected.push_back(ISA(4, 0,-1, 1,-1, 0,-1, 1,-1)); expected.push_back(ISA(4, 0,-1, 1,-1, 1,-1, 0,-1)); // expected.push_back(ISA(4, 1,-1, 0,-1, 0,-1, 1,-1)); expected.push_back(ISA(4, 1,-1, 0,-1, 1,-1, 0,-1)); return expected; } };
/// %Test for set variable sequence symmetry class SetVarSeqSym2 { public: /// Number of variables static const int n = 4; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 0; /// Setup problem constraints and symmetries static void setup(Home home, SetVarArray& xs) { Symmetries syms; syms << VariableSequenceSymmetry(xs,2); rel(home, xs[0], SRT_EQ, xs[2]); branch(home, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms); } /// Compute list of expected solutions static std::vector<IntSetArgs> expectedSolutions(void) { static std::vector<IntSetArgs> expected; expected.clear();
// Symmetric solutions are commented out. expected.push_back(ISA(4, 0, -1,0,-1,0,-1,0,-1)); expected.push_back(ISA(4, 0, -1,0,-1,0,-1, -1)); // expected.push_back(ISA(4, 0, -1,0,-1, -1,0,-1)); // expected.push_back(ISA(4, 0, -1,0,-1, -1, -1)); // expected.push_back(ISA(4, 0, -1, -1,0,-1,0,-1)); expected.push_back(ISA(4, 0, -1, -1,0,-1, -1)); // expected.push_back(ISA(4, 0, -1, -1, -1,0,-1)); // expected.push_back(ISA(4, 0, -1, -1, -1, -1)); // expected.push_back(ISA(4, -1,0,-1,0,-1,0,-1)); // expected.push_back(ISA(4, -1,0,-1,0,-1, -1)); expected.push_back(ISA(4, -1,0,-1, -1,0,-1)); expected.push_back(ISA(4, -1,0,-1, -1, -1)); // expected.push_back(ISA(4, -1, -1,0,-1,0,-1)); // expected.push_back(ISA(4, -1, -1,0,-1, -1)); // expected.push_back(ISA(4, -1, -1, -1,0,-1)); expected.push_back(ISA(4, -1, -1, -1, -1));
return expected; } };
/// %Test for reflection symmetry class ReflectSym1 { public: /// Number of variables static const int n = 6; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 6; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { Matrix<IntVarArray> m(xs, 3, 2);
distinct(home, xs); rel(home, abs(m(0,0)-m(1,0))==1); rel(home, abs(m(0,1)-m(1,1))==1); rel(home, abs(m(1,0)-m(2,0))==1); rel(home, abs(m(1,1)-m(2,1))==1);
Symmetries s; s << values_reflect(l, u); s << rows_interchange(m); s << columns_reflect(m); branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({0,1,2,3,4,5})); expected.push_back(IntArgs({0,1,2,4,5,6})); expected.push_back(IntArgs({0,1,2,5,4,3})); expected.push_back(IntArgs({0,1,2,6,5,4})); return expected; } };
/// %Test for reflection symmetry class ReflectSym2 { public: /// Number of variables static const int n = 2; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 3; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { Symmetries s; s << values_reflect(l, u); branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({0,0})); expected.push_back(IntArgs({0,1})); expected.push_back(IntArgs({0,2})); expected.push_back(IntArgs({0,3})); expected.push_back(IntArgs({1,0})); expected.push_back(IntArgs({1,1})); expected.push_back(IntArgs({1,2})); expected.push_back(IntArgs({1,3})); return expected; } };
/// %Test with action class Action1 { public: /// Number of variables static const int n = 4; /// Lower bound of values static const int l = 0; /// Upper bound of values static const int u = 3; /// Setup problem constraints and symmetries static void setup(Home home, IntVarArray& xs) { distinct(home, xs); Symmetries s; s << VariableSymmetry(xs); s << ValueSymmetry(IntArgs::create(4,0)); branch(home, xs, INT_VAR_ACTION_MIN(0.8), INT_VAL_MIN(), s); } /// Compute list of expected solutions static std::vector<IntArgs> expectedSolutions(void) { static std::vector<IntArgs> expected; expected.clear(); expected.push_back(IntArgs({0,1,2,3})); return expected; } };
#endif
LDSB<VarSym1> varsym1("VarSym1"); LDSB<VarSym1b> varsym1b("VarSym1b"); LDSB<VarSym2> varsym2("VarSym2"); LDSB<VarSym3> varsym3("VarSym3"); LDSB<VarSym4> varsym4("VarSym4"); LDSB<VarSym5> varsym5("VarSym5"); LDSB<MatSym1> matsym1("MatSym1"); LDSB<MatSym2> matsym2("MatSym2"); LDSB<MatSym3> matsym3("MatSym3"); LDSB<MatSym4> matsym4("MatSym4"); LDSB<SimIntVarSym1> simintvarsym1("SimIntVarSym1"); LDSB<SimIntVarSym2> simintvarsym2("SimIntVarSym2"); LDSB<SimIntValSym1> simintvalsym1("SimIntValSym1"); LDSB<SimIntValSym2> simintvalsym2("SimIntValSym2"); LDSB<SimIntValSym3> simintvalsym3("SimIntValSym3"); LDSB<ValSym1> valsym1("ValSym1"); LDSB<ValSym1b> valsym1b("ValSym1b"); LDSB<ValSym1c> valsym1c("ValSym1c"); LDSB<ValSym2> valsym2("ValSym2"); LDSB<ValSym2b> valsym2b("ValSym2b"); LDSB<ValSym3> valsym3("ValSym3"); LDSB<ValSym4> valsym4("ValSym4"); LDSB<ValSym5> valsym5("ValSym5"); LDSB<VarValSym1> varvalsym1("VarValSym1"); LDSBLatin latin("Latin"); LDSB<Recomputation> recomp("Recomputation", 999,999); LDSB<TieBreak> tiebreak("TieBreak");
#ifdef GECODE_HAS_SET_VARS LDSB<ReflectSym1> reflectsym1("ReflectSym1"); LDSB<ReflectSym2> reflectsym2("ReflectSym2"); LDSB<Action1> action1("Action1");
LDSBSet<SetVarSym1> setvarsym1("SetVarSym1"); LDSBSet<SetValSym1> setvalsym1("SetValSym1"); LDSBSet<SetValSym2> setvalsym2("SetValSym2", 0, 1); LDSBSet<SetVarSeqSym1> setvarseqsym1("SetVarSeqSym1"); LDSBSet<SetVarSeqSym2> setvarseqsym2("SetVarSeqSym2");#endif}}
// STATISTICS: test-core