[gecode-users] Global cardinality slow

Mon May 25 23:39:17 CEST 2015

Hi,

I'll point this out, it's not really a bug but it's something you might 
want to look at. The attached flatzinc solves very slowly.

At first I had no annotation on the global_cardinality constraint and 
Gecode took a very long time -- I did not run to completion. I added 
::domain to that constraint and it solves in 109 seconds, 981 nodes -- 
so the time to reach a fixed point at each node is about 1/10th second. 
Minion solves the equivalent model in 492 left (assignment) branches (I 
guess the same node count as gecode) and just over 10 seconds -- so I  
guess reaching a fixed point in 1/100 s.

Does gecode partition the gcc constraint or just remove assigned 
variables? That might explain the difference with domain consistency

Also, did the default propagation level change on gcc? I don't remember 
this test causing a problem previously.

Before you tell me -- I know magic sequence is a stupid benchmark!

Cheers,
Pete
-------------- next part --------------
predicate all_different_int(array [int] of var int: xs);
var 0..199: x_00000::output_var; %
var 0..199: x_00001::output_var; %
var 0..199: x_00002::output_var; %
var 0..199: x_00003::output_var; %
var 0..199: x_00004::output_var; %
var 0..199: x_00005::output_var; %
var 0..199: x_00006::output_var; %
var 0..199: x_00007::output_var; %
var 0..199: x_00008::output_var; %
var 0..199: x_00009::output_var; %
var 0..199: x_00010::output_var; %
var 0..199: x_00011::output_var; %
var 0..199: x_00012::output_var; %
var 0..199: x_00013::output_var; %
var 0..199: x_00014::output_var; %
var 0..199: x_00015::output_var; %
var 0..199: x_00016::output_var; %
var 0..199: x_00017::output_var; %
var 0..199: x_00018::output_var; %
var 0..199: x_00019::output_var; %
var 0..199: x_00020::output_var; %
var 0..199: x_00021::output_var; %
var 0..199: x_00022::output_var; %
var 0..199: x_00023::output_var; %
var 0..199: x_00024::output_var; %
var 0..199: x_00025::output_var; %
var 0..199: x_00026::output_var; %
var 0..199: x_00027::output_var; %
var 0..199: x_00028::output_var; %
var 0..199: x_00029::output_var; %
var 0..199: x_00030::output_var; %
var 0..199: x_00031::output_var; %
var 0..199: x_00032::output_var; %
var 0..199: x_00033::output_var; %
var 0..199: x_00034::output_var; %
var 0..199: x_00035::output_var; %
var 0..199: x_00036::output_var; %
var 0..199: x_00037::output_var; %
var 0..199: x_00038::output_var; %
var 0..199: x_00039::output_var; %
var 0..199: x_00040::output_var; %
var 0..199: x_00041::output_var; %
var 0..199: x_00042::output_var; %
var 0..199: x_00043::output_var; %
var 0..199: x_00044::output_var; %
var 0..199: x_00045::output_var; %
var 0..199: x_00046::output_var; %
var 0..199: x_00047::output_var; %
var 0..199: x_00048::output_var; %
var 0..199: x_00049::output_var; %
var 0..199: x_00050::output_var; %
var 0..199: x_00051::output_var; %
var 0..199: x_00052::output_var; %
var 0..199: x_00053::output_var; %
var 0..199: x_00054::output_var; %
var 0..199: x_00055::output_var; %
var 0..199: x_00056::output_var; %
var 0..199: x_00057::output_var; %
var 0..199: x_00058::output_var; %
var 0..199: x_00059::output_var; %
var 0..199: x_00060::output_var; %
var 0..199: x_00061::output_var; %
var 0..199: x_00062::output_var; %
var 0..199: x_00063::output_var; %
var 0..199: x_00064::output_var; %
var 0..199: x_00065::output_var; %
var 0..199: x_00066::output_var; %
var 0..199: x_00067::output_var; %
var 0..199: x_00068::output_var; %
var 0..199: x_00069::output_var; %
var 0..199: x_00070::output_var; %
var 0..199: x_00071::output_var; %
var 0..199: x_00072::output_var; %
var 0..199: x_00073::output_var; %
var 0..199: x_00074::output_var; %
var 0..199: x_00075::output_var; %
var 0..199: x_00076::output_var; %
var 0..199: x_00077::output_var; %
var 0..199: x_00078::output_var; %
var 0..199: x_00079::output_var; %
var 0..199: x_00080::output_var; %
var 0..199: x_00081::output_var; %
var 0..199: x_00082::output_var; %
var 0..199: x_00083::output_var; %
var 0..199: x_00084::output_var; %
var 0..199: x_00085::output_var; %
var 0..199: x_00086::output_var; %
var 0..199: x_00087::output_var; %
var 0..199: x_00088::output_var; %
var 0..199: x_00089::output_var; %
var 0..199: x_00090::output_var; %
var 0..199: x_00091::output_var; %
var 0..199: x_00092::output_var; %
var 0..199: x_00093::output_var; %
var 0..199: x_00094::output_var; %
var 0..199: x_00095::output_var; %
var 0..199: x_00096::output_var; %
var 0..199: x_00097::output_var; %
var 0..199: x_00098::output_var; %
var 0..199: x_00099::output_var; %
var 0..199: x_00100::output_var; %
var 0..199: x_00101::output_var; %
var 0..199: x_00102::output_var; %
var 0..199: x_00103::output_var; %
var 0..199: x_00104::output_var; %
var 0..199: x_00105::output_var; %
var 0..199: x_00106::output_var; %
var 0..199: x_00107::output_var; %
var 0..199: x_00108::output_var; %
var 0..199: x_00109::output_var; %
var 0..199: x_00110::output_var; %
var 0..199: x_00111::output_var; %
var 0..199: x_00112::output_var; %
var 0..199: x_00113::output_var; %
var 0..199: x_00114::output_var; %
var 0..199: x_00115::output_var; %
var 0..199: x_00116::output_var; %
var 0..199: x_00117::output_var; %
var 0..199: x_00118::output_var; %
var 0..199: x_00119::output_var; %
var 0..199: x_00120::output_var; %
var 0..199: x_00121::output_var; %
var 0..199: x_00122::output_var; %
var 0..199: x_00123::output_var; %
var 0..199: x_00124::output_var; %
var 0..199: x_00125::output_var; %
var 0..199: x_00126::output_var; %
var 0..199: x_00127::output_var; %
var 0..199: x_00128::output_var; %
var 0..199: x_00129::output_var; %
var 0..199: x_00130::output_var; %
var 0..199: x_00131::output_var; %
var 0..199: x_00132::output_var; %
var 0..199: x_00133::output_var; %
var 0..199: x_00134::output_var; %
var 0..199: x_00135::output_var; %
var 0..199: x_00136::output_var; %
var 0..199: x_00137::output_var; %
var 0..199: x_00138::output_var; %
var 0..199: x_00139::output_var; %
var 0..199: x_00140::output_var; %
var 0..199: x_00141::output_var; %
var 0..199: x_00142::output_var; %
var 0..199: x_00143::output_var; %
var 0..199: x_00144::output_var; %
var 0..199: x_00145::output_var; %
var 0..199: x_00146::output_var; %
var 0..199: x_00147::output_var; %
var 0..199: x_00148::output_var; %
var 0..199: x_00149::output_var; %
var 0..199: x_00150::output_var; %
var 0..199: x_00151::output_var; %
var 0..199: x_00152::output_var; %
var 0..199: x_00153::output_var; %
var 0..199: x_00154::output_var; %
var 0..199: x_00155::output_var; %
var 0..199: x_00156::output_var; %
var 0..199: x_00157::output_var; %
var 0..199: x_00158::output_var; %
var 0..199: x_00159::output_var; %
var 0..199: x_00160::output_var; %
var 0..199: x_00161::output_var; %
var 0..199: x_00162::output_var; %
var 0..199: x_00163::output_var; %
var 0..199: x_00164::output_var; %
var 0..199: x_00165::output_var; %
var 0..199: x_00166::output_var; %
var 0..199: x_00167::output_var; %
var 0..199: x_00168::output_var; %
var 0..199: x_00169::output_var; %
var 0..199: x_00170::output_var; %
var 0..199: x_00171::output_var; %
var 0..199: x_00172::output_var; %
var 0..199: x_00173::output_var; %
var 0..199: x_00174::output_var; %
var 0..199: x_00175::output_var; %
var 0..199: x_00176::output_var; %
var 0..199: x_00177::output_var; %
var 0..199: x_00178::output_var; %
var 0..199: x_00179::output_var; %
var 0..199: x_00180::output_var; %
var 0..199: x_00181::output_var; %
var 0..199: x_00182::output_var; %
var 0..199: x_00183::output_var; %
var 0..199: x_00184::output_var; %
var 0..199: x_00185::output_var; %
var 0..199: x_00186::output_var; %
var 0..199: x_00187::output_var; %
var 0..199: x_00188::output_var; %
var 0..199: x_00189::output_var; %
var 0..199: x_00190::output_var; %
var 0..199: x_00191::output_var; %
var 0..199: x_00192::output_var; %
var 0..199: x_00193::output_var; %
var 0..199: x_00194::output_var; %
var 0..199: x_00195::output_var; %
var 0..199: x_00196::output_var; %
var 0..199: x_00197::output_var; %
var 0..199: x_00198::output_var; %
var 0..199: x_00199::output_var; %
constraint int_lin_eq([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[-200,x_00000,x_00001,x_00002,x_00003,x_00004,x_00005,x_00006,x_00007,x_00008,x_00009,x_00010,x_00011,x_00012,x_00013,x_00014,x_00015,x_00016,x_00017,x_00018,x_00019,x_00020,x_00021,x_00022,x_00023,x_00024,x_00025,x_00026,x_00027,x_00028,x_00029,x_00030,x_00031,x_00032,x_00033,x_00034,x_00035,x_00036,x_00037,x_00038,x_00039,x_00040,x_00041,x_00042,x_00043,x_00044,x_00045,x_00046,x_00047,x_00048,x_00049,x_00050,x_00051,x_00052,x_00053,x_00054,x_00055,x_00056,x_00057,x_00058,x_00059,x_00060,x_00061,x_00062,x_00063,x_00064,x_00065,x_00066,x_00067,x_00068,x_00069,x_00070,x_00071,x_00072,x_00073,x_00074,x_00075,x_00076,x_00077,x_00078,x_00079,x_00080,x_00081,x_00082,x_00083,x_00084,x_00085,x_00086,x_00087,x_00088,x_00089,x_00090,x_00091,x_00092,x_00093,x_00094,x_00095,x_00096,x_00097,x_00098,x_00099,x_00100,x_00101,x_00102,x_00103,x_00104,x_00105,x_00106,x_00107,x_00108,x_00109,x_00110,x_00111,x_00112,x_00113,x_00114,x_00115,x_00116,x_00117,x_00118,x_00119,x_00120,x_00121,x_00122,x_00123,x_00124,x_00125,x_00126,x_00127,x_00128,x_00129,x_00130,x_00131,x_00132,x_00133,x_00134,x_00135,x_00136,x_00137,x_00138,x_00139,x_00140,x_00141,x_00142,x_00143,x_00144,x_00145,x_00146,x_00147,x_00148,x_00149,x_00150,x_00151,x_00152,x_00153,x_00154,x_00155,x_00156,x_00157,x_00158,x_00159,x_00160,x_00161,x_00162,x_00163,x_00164,x_00165,x_00166,x_00167,x_00168,x_00169,x_00170,x_00171,x_00172,x_00173,x_00174,x_00175,x_00176,x_00177,x_00178,x_00179,x_00180,x_00181,x_00182,x_00183,x_00184,x_00185,x_00186,x_00187,x_00188,x_00189,x_00190,x_00191,x_00192,x_00193,x_00194,x_00195,x_00196,x_00197,x_00198,x_00199],0);
constraint global_cardinality([x_00000, x_00001, x_00002, x_00003, x_00004, x_00005, x_00006, x_00007, x_00008, x_00009, x_00010, x_00011, x_00012, x_00013, x_00014, x_00015, x_00016, x_00017, x_00018, x_00019, x_00020, x_00021, x_00022, x_00023, x_00024, x_00025, x_00026, x_00027, x_00028, x_00029, x_00030, x_00031, x_00032, x_00033, x_00034, x_00035, x_00036, x_00037, x_00038, x_00039, x_00040, x_00041, x_00042, x_00043, x_00044, x_00045, x_00046, x_00047, x_00048, x_00049, x_00050, x_00051, x_00052, x_00053, x_00054, x_00055, x_00056, x_00057, x_00058, x_00059, x_00060, x_00061, x_00062, x_00063, x_00064, x_00065, x_00066, x_00067, x_00068, x_00069, x_00070, x_00071, x_00072, x_00073, x_00074, x_00075, x_00076, x_00077, x_00078, x_00079, x_00080, x_00081, x_00082, x_00083, x_00084, x_00085, x_00086, x_00087, x_00088, x_00089, x_00090, x_00091, x_00092, x_00093, x_00094, x_00095, x_00096, x_00097, x_00098, x_00099, x_00100, x_00101, x_00102, x_00103, x_00104, x_00105, x_00106, x_00107, x_00108, x_00109, x_00110, x_00111, x_00112, x_00113, x_00114, x_00115, x_00116, x_00117, x_00118, x_00119, x_00120, x_00121, x_00122, x_00123, x_00124, x_00125, x_00126, x_00127, x_00128, x_00129, x_00130, x_00131, x_00132, x_00133, x_00134, x_00135, x_00136, x_00137, x_00138, x_00139, x_00140, x_00141, x_00142, x_00143, x_00144, x_00145, x_00146, x_00147, x_00148, x_00149, x_00150, x_00151, x_00152, x_00153, x_00154, x_00155, x_00156, x_00157, x_00158, x_00159, x_00160, x_00161, x_00162, x_00163, x_00164, x_00165, x_00166, x_00167, x_00168, x_00169, x_00170, x_00171, x_00172, x_00173, x_00174, x_00175, x_00176, x_00177, x_00178, x_00179, x_00180, x_00181, x_00182, x_00183, x_00184, x_00185, x_00186, x_00187, x_00188, x_00189, x_00190, x_00191, x_00192, x_00193, x_00194, x_00195, x_00196, x_00197, x_00198, x_00199],[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199],[x_00000, x_00001, x_00002, x_00003, x_00004, x_00005, x_00006, x_00007, x_00008, x_00009, x_00010, x_00011, x_00012, x_00013, x_00014, x_00015, x_00016, x_00017, x_00018, x_00019, x_00020, x_00021, x_00022, x_00023, x_00024, x_00025, x_00026, x_00027, x_00028, x_00029, x_00030, x_00031, x_00032, x_00033, x_00034, x_00035, x_00036, x_00037, x_00038, x_00039, x_00040, x_00041, x_00042, x_00043, x_00044, x_00045, x_00046, x_00047, x_00048, x_00049, x_00050, x_00051, x_00052, x_00053, x_00054, x_00055, x_00056, x_00057, x_00058, x_00059, x_00060, x_00061, x_00062, x_00063, x_00064, x_00065, x_00066, x_00067, x_00068, x_00069, x_00070, x_00071, x_00072, x_00073, x_00074, x_00075, x_00076, x_00077, x_00078, x_00079, x_00080, x_00081, x_00082, x_00083, x_00084, x_00085, x_00086, x_00087, x_00088, x_00089, x_00090, x_00091, x_00092, x_00093, x_00094, x_00095, x_00096, x_00097, x_00098, x_00099, x_00100, x_00101, x_00102, x_00103, x_00104, x_00105, x_00106, x_00107, x_00108, x_00109, x_00110, x_00111, x_00112, x_00113, x_00114, x_00115, x_00116, x_00117, x_00118, x_00119, x_00120, x_00121, x_00122, x_00123, x_00124, x_00125, x_00126, x_00127, x_00128, x_00129, x_00130, x_00131, x_00132, x_00133, x_00134, x_00135, x_00136, x_00137, x_00138, x_00139, x_00140, x_00141, x_00142, x_00143, x_00144, x_00145, x_00146, x_00147, x_00148, x_00149, x_00150, x_00151, x_00152, x_00153, x_00154, x_00155, x_00156, x_00157, x_00158, x_00159, x_00160, x_00161, x_00162, x_00163, x_00164, x_00165, x_00166, x_00167, x_00168, x_00169, x_00170, x_00171, x_00172, x_00173, x_00174, x_00175, x_00176, x_00177, x_00178, x_00179, x_00180, x_00181, x_00182, x_00183, x_00184, x_00185, x_00186, x_00187, x_00188, x_00189, x_00190, x_00191, x_00192, x_00193, x_00194, x_00195, x_00196, x_00197, x_00198, x_00199])::domain;

solve :: int_search([x_00000, x_00001, x_00002, x_00003, x_00004, x_00005, x_00006, x_00007, x_00008, x_00009, x_00010, x_00011, x_00012, x_00013, x_00014, x_00015, x_00016, x_00017, x_00018, x_00019, x_00020, x_00021, x_00022, x_00023, x_00024, x_00025, x_00026, x_00027, x_00028, x_00029, x_00030, x_00031, x_00032, x_00033, x_00034, x_00035, x_00036, x_00037, x_00038, x_00039, x_00040, x_00041, x_00042, x_00043, x_00044, x_00045, x_00046, x_00047, x_00048, x_00049, x_00050, x_00051, x_00052, x_00053, x_00054, x_00055, x_00056, x_00057, x_00058, x_00059, x_00060, x_00061, x_00062, x_00063, x_00064, x_00065, x_00066, x_00067, x_00068, x_00069, x_00070, x_00071, x_00072, x_00073, x_00074, x_00075, x_00076, x_00077, x_00078, x_00079, x_00080, x_00081, x_00082, x_00083, x_00084, x_00085, x_00086, x_00087, x_00088, x_00089, x_00090, x_00091, x_00092, x_00093, x_00094, x_00095, x_00096, x_00097, x_00098, x_00099, x_00100, x_00101, x_00102, x_00103, x_00104, x_00105, x_00106, x_00107, x_00108, x_00109, x_00110, x_00111, x_00112, x_00113, x_00114, x_00115, x_00116, x_00117, x_00118, x_00119, x_00120, x_00121, x_00122, x_00123, x_00124, x_00125, x_00126, x_00127, x_00128, x_00129, x_00130, x_00131, x_00132, x_00133, x_00134, x_00135, x_00136, x_00137, x_00138, x_00139, x_00140, x_00141, x_00142, x_00143, x_00144, x_00145, x_00146, x_00147, x_00148, x_00149, x_00150, x_00151, x_00152, x_00153, x_00154, x_00155, x_00156, x_00157, x_00158, x_00159, x_00160, x_00161, x_00162, x_00163, x_00164, x_00165, x_00166, x_00167, x_00168, x_00169, x_00170, x_00171, x_00172, x_00173, x_00174, x_00175, x_00176, x_00177, x_00178, x_00179, x_00180, x_00181, x_00182, x_00183, x_00184, x_00185, x_00186, x_00187, x_00188, x_00189, x_00190, x_00191, x_00192, x_00193, x_00194, x_00195, x_00196, x_00197, x_00198, x_00199], input_order, indomain_min, complete)
 satisfy;