Scippy

SCIP

Solving Constraint Integer Programs

cons_countsols.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file cons_countsols.c
26  * @ingroup DEFPLUGINS_CONS
27  * @brief constraint handler for counting feasible solutions
28  * @author Stefan Heinz
29  * @author Michael Winkler
30  *
31  * If this constraint handler is activated than it counts or collects all feasible solutions. We refer to \ref COUNTER for
32  * more details about using SCIP for counting feasible solutions.
33  *
34  * @todo In the last round of presolving we should check if variables exist, which have up and down lock one. In this
35  * case we know that these locks are coming from this constraint handler. Therefore, they are totally free and can
36  * be ignored in the branch and bound process. To get this result we have to store these variables in the
37  * constraint handler data structure (to remember this free dimensions) and fix them to any feasible value.
38  */
39 
40 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
41 
42 #include "blockmemshell/memory.h"
44 #include "scip/cons_countsols.h"
45 #include "scip/cons_knapsack.h"
46 #include "scip/cons_logicor.h"
47 #include "scip/cons_setppc.h"
48 #include "scip/cons_varbound.h"
49 #include "scip/dialog_default.h"
50 #include "scip/pub_cons.h"
51 #include "scip/pub_dialog.h"
52 #include "scip/pub_disp.h"
53 #include "scip/pub_heur.h"
54 #include "scip/pub_message.h"
55 #include "scip/pub_misc.h"
56 #include "scip/pub_misc_sort.h"
57 #include "scip/pub_sol.h"
58 #include "scip/pub_var.h"
59 #include "scip/scip_branch.h"
60 #include "scip/scip_cons.h"
61 #include "scip/scip_dialog.h"
62 #include "scip/scip_disp.h"
63 #include "scip/scip_general.h"
64 #include "scip/scip_heur.h"
65 #include "scip/scip_mem.h"
66 #include "scip/scip_message.h"
67 #include "scip/scip_numerics.h"
68 #include "scip/scip_param.h"
69 #include "scip/scip_prob.h"
70 #include "scip/scip_sol.h"
71 #include "scip/scip_solve.h"
72 #include "scip/scip_var.h"
73 #include "symmetry/type_symmetry.h"
74 #include <string.h>
75 
76 /* depending on whether the GMP library is available we use a GMP data type or a SCIP_Longint */
77 #ifdef SCIP_WITH_GMP
78 #include <gmp.h>
79 typedef mpz_t Int;
80 #else
81 typedef SCIP_Longint Int;
82 #endif
83 
84 /* constraint handler properties */
85 #define CONSHDLR_NAME "countsols"
86 #define CONSHDLR_DESC "constraint to count feasible solutions"
87 #define CONSHDLR_ENFOPRIORITY -9999999 /**< priority of the constraint handler for constraint enforcing */
88 #define CONSHDLR_CHECKPRIORITY -9999999 /**< priority of the constraint handler for checking feasibility */
89 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
90  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
91 #define CONSHDLR_NEEDSCONS FALSE /**< should the constraint handler be skipped, if no constraints are available? */
92 
93 /* default parameter settings */
94 #define DEFAULT_SPARSETEST TRUE /**< sparse test on or off */
95 #define DEFAULT_DISCARDSOLS TRUE /**< is it allowed to discard solutions */
96 #define DEFAULT_ACTIVE FALSE /**< is the constraint handler active */
97 #define DEFAULT_COLLECT FALSE /**< should the solutions be collected */
98 #define DEFAULT_SOLLIMIT -1LL /**< counting stops, if the given number of solutions were found (-1: no limit) */
99 
100 /* default column settings */
101 #define DISP_SOLS_NAME "sols"
102 #define DISP_SOLS_DESC "number of detected feasible solutions"
103 #define DISP_SOLS_HEADER " sols "
104 #define DISP_SOLS_WIDTH 7
105 #define DISP_SOLS_PRIORITY 110000
106 #define DISP_SOLS_POSITION 100000
107 #define DISP_SOLS_STRIPLINE TRUE
109 #define DISP_CUTS_NAME "feasST"
110 #define DISP_CUTS_DESC "number of detected non trivial feasible subtrees"
111 #define DISP_CUTS_HEADER "feasST"
112 #define DISP_CUTS_WIDTH 6
113 #define DISP_CUTS_PRIORITY 110000
114 #define DISP_CUTS_POSITION 110000
115 #define DISP_CUTS_STRIPLINE TRUE
117 /** creates and adds a constraint which cuts off the solution from the feasibility region
118  *
119  * input:
120  * - scip : SCIP main data structure
121  * - sol : solution to cut off
122  * - conshdlrdata : constraint handler data
123  */
124 #define CUTOFF_CONSTRAINT(x) SCIP_RETCODE x (SCIP* scip, SCIP_SOL* sol, SCIP_CONSHDLRDATA* conshdlrdata)
126 
127 /** constraint handler data */
128 struct SCIP_ConshdlrData
129 {
130  /* solution data and statistic variables */
131  SCIP_SPARSESOL** solutions; /**< array to store all solutions */
132  int nsolutions; /**< number of solution stored */
133  int ssolutions; /**< size of the solution array */
134  int feasST; /**< number of non trivial feasible subtrees */
135  int nDiscardSols; /**< number of discarded solutions */
136  int nNonSparseSols; /**< number of non sparse solutions */
137  Int nsols; /**< number of solutions */
138  CUTOFF_CONSTRAINT((*cutoffSolution)); /**< method for cutting of a solution */
139 
140  /* constraint handler parameters */
141  SCIP_Longint sollimit; /**< counting stops, if the given number of solutions have been found (-1: no limit) */
142  SCIP_Bool active; /**< constraint handler active */
143  SCIP_Bool discardsols; /**< allow to discard solutions */
144  SCIP_Bool sparsetest; /**< allow to check for sparse solutions */
145  SCIP_Bool collect; /**< should the solutions be collected */
146 
147  SCIP_Bool warning; /**< has the warning message already been posted? */
148 
149  /* specific problem data */
150  SCIP_HASHMAP* hashmap; /**< hashmap to store position of active transformed problem variable in our vars array */
151  SCIP_VAR** allvars; /**< array containing a copy of all variables before presolving */
152  SCIP_VAR** vars; /**< array containing a copy of all active variables (after presolving) */
153  int nallvars; /**< number of all variables in the problem */
154  int nvars; /**< number of all active variables in the problem */
155  SCIP_Bool continuous; /**< are there continuous variables */
156 };
157 
158 
159 /*
160  * Local methods for handling the <Int> data structure
161  */
162 
163 /** allocates memory for the value pointer */
164 static
165 void allocInt(
166  Int* value /**< pointer to the value to allocate memory */
167  )
168 { /*lint --e{715}*/
169 #ifdef SCIP_WITH_GMP
170  mpz_init(*value);
171 #endif
172 }
173 
174 
175 /** sets the value pointer to the new value */
176 static
177 void setInt(
178  Int* value, /**< pointer to the value to initialize */
179  SCIP_Longint newvalue /**< new value */
180  )
181 {
182  assert(newvalue < LONG_MAX);
183 
184 #ifdef SCIP_WITH_GMP
185  mpz_set_si(*value, (long) newvalue);
186 #else
187  (*value) = newvalue;
188 #endif
189 }
190 
191 
192 /** sets a power of 2 to the given value */
193 static
194 void setPowerOfTwo(
195  Int* value, /**< pointer to the value to increase */
196  SCIP_Longint exponent /**< exponent for the base 2 */
197  )
198 {
199  assert(0 <= exponent && exponent < LONG_MAX);
200 
201 #ifdef SCIP_WITH_GMP
202  mpz_ui_pow_ui(*value, 2UL, (unsigned long) exponent);
203 #else
204  assert(exponent < 64);
205  (*value) = (SCIP_Longint)1 << exponent;
206 #endif
207 }
208 
209 
210 /** free memory */
211 static
212 void freeInt(
213  Int* value /**< pointer to the value to free */
214  )
215 { /*lint --e{715}*/
216 #ifdef SCIP_WITH_GMP
217  mpz_clear(*value);
218 #endif
219 }
220 
221 
222 /** adds one to the given value */
223 static
224 void addOne(
225  Int* value /**< pointer to the value to increase */
226  )
227 {
228 #ifdef SCIP_WITH_GMP
229  mpz_add_ui(*value, *value, 1UL);
230 #else
231  (*value)++;
232 #endif
233 }
234 
235 
236 /** adds the summand to the given value */
237 static
238 void addInt(
239  Int* value, /**< pointer to the value to increase */
240  Int* summand /**< summand to add on */
241  )
242 {
243 #ifdef SCIP_WITH_GMP
244  mpz_add(*value, *value, *summand);
245 #else
246  (*value) += (*summand);
247 #endif
248 }
249 
250 
251 /** multiplies the factor by the given value */
252 static
253 void multInt(
254  Int* value, /**< pointer to the value to increase */
255  SCIP_Longint factor /**< factor to multiply with */
256  )
257 {
258  assert(0 <= factor && factor < LONG_MAX);
259 
260 #ifdef SCIP_WITH_GMP
261  mpz_mul_ui(*value, *value, (unsigned long) factor);
262 #else
263  (*value) *= factor;
264 #endif
265 }
266 
267 
268 /** method for creating a string out of an Int which is a mpz_t or SCIP_Longint */ /*lint -e{715}*/
269 static
270 void toString(
271  Int value, /**< number */
272  char** buffer, /**< pointer to buffer for storing the string */
273  int buffersize /**< length of the buffer */
274  )
275 { /*lint --e{715}*/
276 #ifdef SCIP_WITH_GMP
277  (void) mpz_get_str(*buffer, 10, value);
278 #else
279  (void) SCIPsnprintf (*buffer, buffersize, "%" SCIP_LONGINT_FORMAT "", value);
280 #endif
281 }
282 
283 
284 /** method for creating a SCIP_Longing out of an Int */
285 static
287  Int value, /**< number to convert */
288  SCIP_Bool* valid /**< pointer to store if the return value is valid */
289  )
290 {
291 #ifdef SCIP_WITH_GMP
292  *valid = FALSE;
293  if( 0 != mpz_fits_sint_p(value) )
294  (*valid) = TRUE;
295 
296  return mpz_get_si(value);
297 #else
298  *valid = TRUE;
299  return value;
300 #endif
301 }
302 
303 
304 /*
305  * Local methods
306  */
307 
308 
309 /** returns whether a given integer variable is unfixed in the local domain */
310 static
312  SCIP_VAR* var /**< integer variable */
313  )
314 {
315  assert( var != NULL );
316  assert( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS );
317  assert( SCIPvarGetUbLocal(var) - SCIPvarGetLbLocal(var) >= 0.0 );
318 
319  return ( SCIPvarGetUbLocal(var) - SCIPvarGetLbLocal(var) > 0.5 );
320 }
321 
322 
323 /** creates the constraint handler data */
324 static
326  SCIP* scip, /**< SCIP data structure */
327  SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to store constraint handler data */
328  )
329 {
330  SCIP_CALL( SCIPallocBlockMemory(scip, conshdlrdata) );
331 
332  (*conshdlrdata)->feasST = 0;
333  (*conshdlrdata)->nDiscardSols = 0;
334  (*conshdlrdata)->nNonSparseSols = 0;
335  (*conshdlrdata)->solutions = NULL;
336  (*conshdlrdata)->nsolutions = 0;
337  (*conshdlrdata)->ssolutions = 0;
338 
339  allocInt(&(*conshdlrdata)->nsols); /*lint !e545*/
340 
341  (*conshdlrdata)->cutoffSolution = NULL;
342  (*conshdlrdata)->warning = FALSE;
343  (*conshdlrdata)->hashmap = NULL;
344  (*conshdlrdata)->allvars = NULL;
345  (*conshdlrdata)->vars = NULL;
346  (*conshdlrdata)->nallvars = 0;
347  (*conshdlrdata)->nvars = 0;
348  (*conshdlrdata)->continuous = FALSE;
349 
350  return SCIP_OKAY;
351 }
352 
353 
354 #ifndef NDEBUG
355 /** check solution in original space */
356 static
357 void checkSolutionOrig(
358  SCIP* scip, /**< SCIP data structure */
359  SCIP_SOL* sol, /**< solution to add */
360  SCIP_CONSHDLRDATA* conshdlrdata /**< constraint handler data */
361  )
362 {
363  SCIP_Bool feasible;
364  SCIP_RETCODE retcode;
365 
366  /* turn off solution counting to be able to check the solution */
367  conshdlrdata->active = FALSE;
368 
369  SCIPdebugMsg(scip, "check solution in original space before counting\n");
370 
371  feasible = FALSE;
372 
373  /* check solution in original space */
374  retcode = SCIPcheckSolOrig(scip, sol, &feasible, TRUE, TRUE);
375  assert(feasible);
376 
377  /* check return code manually */
378  if( retcode != SCIP_OKAY )
379  {
380  SCIPprintError(retcode);
381  SCIPABORT();
382  }
383 
384  /* turn on solution counting to continue */
385  conshdlrdata->active = TRUE;
386 }
387 #else
388 #define checkSolutionOrig(scip, sol, conshdlrdata) /**/
389 #endif
390 
391 /** check if the current parameter setting is correct for a safe counting process */
392 static
394  SCIP* scip /**< SCIP data structure */
395  )
396 {
397  SCIP_HEUR** heuristics;
398  int nheuristics;
399  int h;
400  int intvalue;
401  SCIP_Bool valid;
402 
403  assert( scip != NULL );
404 
405  valid = TRUE;
406 
407  /* check if all heuristics are turned off */
408  heuristics = SCIPgetHeurs(scip);
409  nheuristics = SCIPgetNHeurs(scip);
410 
411  for( h = 0; h < nheuristics && valid; ++h )
412  {
413  if( SCIPheurGetFreq(heuristics[h]) != -1 )
414  valid = FALSE;
415  }
416 
417  if( valid )
418  {
420  "At least one heuristic is not turned off! Heuristic solutions are currently not accepted while couting.\n");
421  }
422 
423  /* check if restart is turned off */
424  SCIP_CALL( SCIPgetIntParam(scip, "presolving/maxrestarts", &intvalue) );
425  if( intvalue != 0 )
426  {
427  /* need to disable restarts, since collecting solutions won't work, but also the capturing for variables is not
428  * correctly handled
429  */
430  SCIPwarningMessage(scip, "counting forces parameter <presolving/maxrestarts> to 0.\n");
431  if( SCIPisParamFixed(scip, "presolving/maxrestarts") )
432  {
433  SCIP_CALL( SCIPunfixParam(scip, "presolving/maxrestarts") );
434  }
435 
436  SCIP_CALL( SCIPsetIntParam(scip, "presolving/maxrestarts", 0) );
437  }
438 
439  /* check if symmetry handling is turned off */
440  SCIP_CALL( SCIPgetIntParam(scip, "misc/usesymmetry", &intvalue) );
441  if ( intvalue != 0 )
442  {
443  /* need to disable symmetry handling, since counting is not supported if symmetry handling is enabled */
444  SCIPwarningMessage(scip, "counting forces parameter <misc/usesymmetry> to 0.\n");
445  if( SCIPisParamFixed(scip, "misc/usesymmetry") )
446  {
447  SCIP_CALL( SCIPunfixParam(scip, "misc/usesymmetry") );
448  }
449 
450  SCIP_CALL( SCIPsetIntParam(scip, "misc/usesymmetry", 0) );
451  }
452 
453  return SCIP_OKAY;
454 }
455 
456 /** creates and adds a constraints which cuts off the current solution from the feasibility region in the case there are
457  * only binary variables
458  */
459 static
460 CUTOFF_CONSTRAINT(addBinaryCons)
461 {
462  int v;
463  SCIP_VAR** consvars;
464  SCIP_VAR** vars;
465  int nvars;
466  SCIP_Real value;
467  SCIP_VAR* var;
468  SCIP_CONS* cons;
469 
470  assert( scip != NULL );
471  assert( sol != NULL );
472  assert( conshdlrdata != NULL );
473 
474  vars = conshdlrdata->vars;
475  nvars = conshdlrdata->nvars;
476 
477  /* allocate buffer memory */
478  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nvars) );
479 
480  for( v = 0; v < nvars; ++v )
481  {
482  var = vars[v];
483 
484  assert( var != NULL );
485  assert( SCIPvarIsBinary(var) );
486 
487  value = SCIPgetSolVal(scip, sol, var);
488  assert( SCIPisFeasIntegral(scip, value) );
489 
490  if( value > 0.5 )
491  {
492  SCIP_CALL( SCIPgetNegatedVar(scip, var, &consvars[v]) );
493  }
494  else
495  consvars[v] = var;
496  }
497 
498  /* create constraint */
499  SCIP_CALL( SCIPcreateConsSetcover(scip, &cons, "Setcovering created by countsols", nvars, consvars,
501 
502  /* add and release constraint */
503  SCIP_CALL( SCIPaddCons(scip, cons) );
504  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
505 
506  /* free buffer array */
507  SCIPfreeBufferArray(scip, &consvars);
508 
509  return SCIP_OKAY;
510 }
511 
512 
513 /** creates and adds a bound disjunction constraints which cuts off the current solution from the feasibility region; if
514  * only binary variables are involved, then a set covering constraint is created which is a special case of a bound
515  * disjunction constraint
516  */
517 static
518 CUTOFF_CONSTRAINT(addIntegerCons)
519 {
520  int v;
521  SCIP_VAR** consvars;
522  SCIP_VAR** vars;
523  SCIP_Real* bounds;
524  SCIP_BOUNDTYPE* boundtypes;
525  int nvars;
526  int nbinvars = 0;
527  int nconsvars;
528  SCIP_VAR* var;
529  SCIP_Real value;
530  SCIP_CONS* cons;
531 
532  assert( scip != NULL );
533  assert( sol != NULL );
534  assert( conshdlrdata != NULL );
535 
536  vars = conshdlrdata->vars;
537  nvars = conshdlrdata->nvars;
538 
539  nconsvars = nvars * 2;
540  assert( nvars > 0 );
541 
542  /* allocate buffer memory */
543  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nconsvars) );
544  SCIP_CALL( SCIPallocBufferArray(scip, &bounds, nconsvars) );
545  SCIP_CALL( SCIPallocBufferArray(scip, &boundtypes, nconsvars) );
546 
547  nconsvars = 0;
548 
549  for( v = nvars - 1; v >= 0; --v )
550  {
551  var = vars[v];
552 
553  assert( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS );
554 
555  if( SCIPvarIsBinary(var) )
556  {
557  ++nbinvars;
558  value = SCIPgetSolVal(scip, sol, var);
559  assert( SCIPisFeasIntegral(scip, value) );
560 
561  if( value < 0.5 )
562  {
563  boundtypes[nconsvars] = SCIP_BOUNDTYPE_LOWER;
564  bounds[nconsvars] = 1;
565  }
566  else
567  {
568  boundtypes[nconsvars] = SCIP_BOUNDTYPE_UPPER;
569  bounds[nconsvars] = 0;
570  }
571  }
572  else
573  {
574  SCIP_Real lb;
575  SCIP_Real ub;
576  SCIP_Real valueInt;
577 
578  assert( SCIPisFeasIntegral(scip, SCIPvarGetLbLocal(var)) );
579  assert( SCIPisFeasIntegral(scip, SCIPvarGetUbLocal(var)) );
580  assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, var)) );
581 
582  lb = SCIPvarGetLbLocal(var);
583  ub = SCIPvarGetUbLocal(var);
584  valueInt = SCIPgetSolVal(scip, sol, var);
585 
586  if( SCIPisFeasEQ(scip, valueInt, lb) )
587  {
588  boundtypes[nconsvars] = SCIP_BOUNDTYPE_LOWER;
589  bounds[nconsvars] = lb + 1.0;
590  }
591  else if( SCIPisFeasEQ(scip, valueInt, ub) )
592  {
593  boundtypes[nconsvars] = SCIP_BOUNDTYPE_UPPER;
594  bounds[nconsvars] = ub - 1.0;
595  }
596  else
597  {
598  boundtypes[nconsvars] = SCIP_BOUNDTYPE_LOWER;
599  bounds[nconsvars] = valueInt + 1.0;
600  consvars[nconsvars] = var;
601  ++nconsvars;
602  boundtypes[nconsvars] = SCIP_BOUNDTYPE_UPPER;
603  bounds[nconsvars] = valueInt - 1.0;
604  }
605  }
606 
607  consvars[nconsvars] = var;
608  ++nconsvars;
609  }
610 
611  /* check if only binary variables appear in the constraint; if this is the case, we
612  * create a set covering constraint instead of a bound disjunction constraint
613  */
614  if( nvars == nbinvars )
615  {
616  for( v = nbinvars - 1; v >= 0; --v )
617  {
618  /* in the case the bound is zero we have use the negated variable */
619  if( bounds[v] == 0)
620  {
621  SCIP_CALL( SCIPgetNegatedVar(scip, consvars[v], &consvars[v]));
622  }
623  }
624 
625  SCIP_CALL( SCIPcreateConsSetcover(scip, &cons, "Setcovering created by countsols", nbinvars, consvars,
627  }
628  else
629  {
630  SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &cons, "Bounddisjunction created by countsols",
631  nconsvars, consvars, boundtypes, bounds,
633  }
634 
635  /* add and release constraint locally */
636  SCIP_CALL( SCIPaddCons(scip, cons) );
637  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
638 
639  /* free buffer memory */
640  SCIPfreeBufferArray(scip, &consvars);
641  SCIPfreeBufferArray(scip, &bounds);
642  SCIPfreeBufferArray(scip, &boundtypes);
643 
644  return SCIP_OKAY;
645 }
646 
647 /** collect given solution or local domains as sparse solution */
648 static
650  SCIP* scip, /**< SCIP data structure */
651  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
652  SCIP_SOL* sol /**< solution, or NULL if local domains */
653  )
654 {
655  SCIP_SPARSESOL* solution;
656  SCIP_Longint* lbvalues;
657  SCIP_Longint* ubvalues;
658  int nvars;
659  int v;
660 
661  /* ensure size of solution array
662  *
663  * we use normal memory instead of block memory because this plugin is rarely used, the size of 'solutions'
664  * can be arbitrary large, and the change that the other blocks can be used is quite small
665  */
666  if( conshdlrdata->nsolutions == conshdlrdata->ssolutions )
667  {
668  if( conshdlrdata->ssolutions == 0 )
669  {
670  conshdlrdata->ssolutions = 100;
671  SCIP_CALL( SCIPallocMemoryArray(scip, &conshdlrdata->solutions, conshdlrdata->ssolutions) );
672  }
673  else
674  {
675  assert( conshdlrdata->ssolutions < INT_MAX / 2);
676  conshdlrdata->ssolutions *= 2;
677  SCIP_CALL( SCIPreallocMemoryArray(scip, &conshdlrdata->solutions, conshdlrdata->ssolutions) );
678  }
679  }
680  assert( conshdlrdata->nsolutions < conshdlrdata->ssolutions );
681 
682  /* get number of active variables */
683  nvars = conshdlrdata->nvars;
684 
685  SCIPdebugMsg(scip, "creating solution number %d\n", conshdlrdata->nsolutions);
686 
687  /* create a solution */
688  SCIP_CALL_FINALLY( SCIPsparseSolCreate(&solution, conshdlrdata->vars, nvars, FALSE), SCIPsparseSolFree(&solution) );
689  assert(solution != NULL);
690 
691  lbvalues = SCIPsparseSolGetLbs(solution);
692  ubvalues = SCIPsparseSolGetUbs(solution);
693  assert(ubvalues != NULL);
694  assert(lbvalues != NULL);
695 
696  for( v = nvars - 1; v >= 0; --v )
697  {
698  SCIP_VAR* var;
699 
700  var = conshdlrdata->vars[v];
701  assert(var != NULL);
702 
703  if( sol == NULL )
704  {
705  lbvalues[v] = SCIPconvertRealToLongint(scip, SCIPvarGetLbLocal(var));
706  ubvalues[v] = SCIPconvertRealToLongint(scip, SCIPvarGetUbLocal(var));
707  }
708  else
709  {
710  lbvalues[v] = SCIPconvertRealToLongint(scip, SCIPgetSolVal(scip, sol, var));
711  ubvalues[v] = lbvalues[v];
712  }
713 
714  SCIPdebugMsg(scip, "variable <%s> [%" SCIP_LONGINT_FORMAT ",%" SCIP_LONGINT_FORMAT "]\n",
715  SCIPvarGetName(var), lbvalues[v], ubvalues[v]);
716  }
717 
718  conshdlrdata->solutions[conshdlrdata->nsolutions] = solution;
719  conshdlrdata->nsolutions++;
720 
721  return SCIP_OKAY;
722 }
723 
724 
725 /** counts the number of solutions represented by sol */
726 static
728  SCIP* scip, /**< SCIP data structure */
729  SCIP_SOL* sol, /**< solution */
730  SCIP_Bool feasible, /**< is solution feasible? */
731  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
732  SCIP_RESULT* result /**< pointer to store the result of the checking process */
733  )
734 {
735  assert( scip != NULL );
736  assert( sol != NULL );
737  assert( conshdlrdata != NULL );
738  assert( result != NULL );
739 
740  /* the result should be infeasible since we reject any solution; however, if the solution passes the sparse test, the
741  * result is set to SCIP_CUTOFF which cuts off the subtree initialized through the current node
742  */
743  assert(*result == SCIP_INFEASIBLE);
744 
745  if( feasible )
746  {
747  int v;
748  Int newsols;
749  SCIP_VAR** vars;
750  int nvars;
751  SCIP_VAR* var;
752  SCIP_Real lb;
753  SCIP_Real ub;
754 
755  SCIPdebugMsg(scip, "counts number of solutions represented through the given one\n");
756 
757  /**@note aggregations and multi aggregations: we do not have to care about these things
758  * since we count solutions from the transformed problem and therefore, SCIP does
759  * it for us
760  */
761  assert( SCIPgetNPseudoBranchCands(scip) != 0 );
762 
763  allocInt(&newsols); /*lint !e545*/
764 
765  /* set newsols to one */
766  setInt(&newsols, 1LL); /*lint !e545*/
767 
768  if( SCIPgetNBinVars(scip) == SCIPgetNVars(scip) )
769  {
770  int npseudocands;
771 
772  npseudocands = SCIPgetNPseudoBranchCands(scip);
773 
774  /* sets a power of 2 to the number of solutions */
775  setPowerOfTwo(&newsols, (SCIP_Longint) npseudocands); /*lint !e545*/
776  }
777  else
778  {
779  SCIP_VAR* origvar;
780  SCIP_Real scalar = 1.0;
781  SCIP_Real constant = 0.0;
782 
783  SCIP_CALL( SCIPgetPseudoBranchCands(scip, &vars, &nvars, NULL) );
784 
785  for( v = 0; v < nvars; ++v )
786  {
787  var = vars[v];
788  origvar = var;
789 
790  /* get original variable to decide if we will count the domain; continuous variables aren't counted */
791  SCIP_CALL( SCIPvarGetOrigvarSum(&origvar, &scalar, &constant) );
792 
793  if( origvar != NULL && SCIPvarGetType(origvar) != SCIP_VARTYPE_CONTINUOUS )
794  {
795  lb = SCIPvarGetLbLocal(var);
796  ub = SCIPvarGetUbLocal(var);
797 
798  SCIPdebugMsg(scip, "variable <%s> Local Bounds are [%g,%g]\n", SCIPvarGetName(var), lb, ub);
799 
800  assert( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS );
801  assert( SCIPisFeasIntegral(scip, lb) );
802  assert( SCIPisFeasIntegral(scip, ub) );
803  assert( SCIPisFeasIntegral(scip, ub - lb) );
804  assert( SCIPisFeasLT(scip, lb, ub) );
805 
806  /* the number of integers lying in the interval [lb,ub] is (ub - lb + 1); to make everything integral we
807  * add another 0.5 and cut the fractional part off
808  */
809  multInt(&newsols, (SCIP_Longint)(ub - lb + 1.5) ); /*lint !e545*/
810  }
811  }
812  }
813 
814  *result = SCIP_CUTOFF;
815  conshdlrdata->feasST++;
816 
817  if( conshdlrdata->collect )
818  {
819  SCIP_CALL( collectSolution(scip, conshdlrdata, NULL) );
820  }
821 
822  addInt(&conshdlrdata->nsols, &newsols); /*lint !e545*/
823  freeInt(&newsols); /*lint !e545*/
824  }
825  else if(!conshdlrdata->discardsols)
826  {
827  SCIP_CALL( conshdlrdata->cutoffSolution(scip, sol, conshdlrdata) );
828  addOne(&conshdlrdata->nsols); /*lint !e545*/
829  conshdlrdata->nNonSparseSols++;
830  if( conshdlrdata->collect )
831  {
832  SCIP_CALL( collectSolution(scip, conshdlrdata, sol) );
833  }
834  }
835  else
836  conshdlrdata->nDiscardSols++;
837 
838  return SCIP_OKAY;
839 }
840 
841 
842 /** checks if the new solution is feasible for the logicor constraints */
843 static
845  SCIP* scip, /**< SCIP data structure */
846  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
847  int nconss, /**< number of enabled constraints */
848  SCIP_Bool* satisfied /**< pointer to store if the logicor constraints a satisfied */
849  )
850 {
851  /**@note the logicor constraints are not fully propagated; therefore, we have to check
852  * them by hand if they are satisfied or not; if a constraint is satisfied we
853  * delete it locally from the branch and bound tree.
854  */
855 
856  SCIP_CONS** conss;
857  SCIP_VAR** vars;
858  SCIP_Bool fixedone;
859  int nvars;
860  int c;
861  int v;
862 
863  SCIPdebugMsg(scip, "check logicor %d constraints\n", nconss);
864 
865  assert( scip != NULL );
866  assert( conshdlr != NULL );
867  assert( strcmp(SCIPconshdlrGetName(conshdlr),"logicor") == 0 );
868  assert( nconss == SCIPconshdlrGetNEnabledConss(conshdlr) );
869 
870  conss = SCIPconshdlrGetConss(conshdlr);
871  assert( conss != NULL );
872 
873  (*satisfied) = TRUE;
874  c = SCIPconshdlrGetNActiveConss(conshdlr) - 1;
875 
876  for( ; c >= 0 && nconss > 0 && (*satisfied); --c )
877  {
878  SCIPdebugMsg(scip, "logicor constraint %d\n", c);
879 
880  if( !SCIPconsIsEnabled(conss[c]) )
881  continue;
882 
883  nconss--;
884 
885  nvars = SCIPgetNVarsLogicor(scip, conss[c]);
886  vars = SCIPgetVarsLogicor(scip, conss[c]);
887 
888  /* calculate the constraint's activity */
889  fixedone = FALSE;
890  for( v = 0; v < nvars && !fixedone; ++v )
891  {
892  assert(SCIPvarIsBinary(vars[v]));
893 
894  if( !varIsUnfixedLocal(vars[v] ) )
895  fixedone = SCIPvarGetLbLocal(vars[v]) > 0.5;
896  }
897 
898  if( !fixedone )
899  {
900  SCIPdebugMsg(scip, "constraint <%s> cannot be disabled\n", SCIPconsGetName(conss[c]));
901  SCIPdebugPrintCons(scip, conss[c], NULL);
902  (*satisfied) = FALSE;
903  }
904  else
905  {
906  /* delete constraint from the problem locally since it is satisfied */
907  SCIP_CALL( SCIPdelConsLocal(scip, conss[c]) );
908  }
909  }
910 
911  return SCIP_OKAY;
912 }
913 
914 
915 /** checks if the new solution is feasible for the knapsack constraints */
916 static
918  SCIP* scip, /**< SCIP data structure */
919  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
920  int nconss, /**< number of enabled constraints */
921  SCIP_Bool* satisfied /**< pointer to store if the logicor constraints a satisfied */
922  )
923 {
924  /**@note the knapsack constraints are not fully propagated; therefore, we have to check
925  * them by hand if they are satisfied or not; if a constraint is satisfied we
926  * delete it locally from the branch and bound tree.
927  */
928 
929  SCIP_CONS** conss;
930  SCIP_VAR** vars;
931  SCIP_Longint* weights;
932  SCIP_Longint capacity;
933  SCIP_Real capa;
934  int nvars;
935  int c;
936  int v;
937 
938  SCIPdebugMsg(scip, "check knapsack %d constraints\n", nconss);
939 
940  assert( scip != NULL );
941  assert( conshdlr != NULL );
942  assert( strcmp(SCIPconshdlrGetName(conshdlr),"knapsack") == 0 );
943  assert( nconss == SCIPconshdlrGetNEnabledConss(conshdlr) );
944 
945  conss = SCIPconshdlrGetConss(conshdlr);
946  assert( conss != NULL );
947 
948  (*satisfied) = TRUE;
949  c = SCIPconshdlrGetNActiveConss(conshdlr) - 1;
950 
951  for( ; c >= 0 && nconss > 0 && (*satisfied); --c )
952  {
953  SCIPdebugMsg(scip, "knapsack constraint %d\n", c);
954 
955  if( !SCIPconsIsEnabled(conss[c]) )
956  continue;
957 
958  nconss--;
959 
960  nvars = SCIPgetNVarsKnapsack(scip, conss[c]);
961  vars = SCIPgetVarsKnapsack(scip, conss[c]);
962  capacity = SCIPgetCapacityKnapsack(scip, conss[c]);
963  weights = SCIPgetWeightsKnapsack(scip,conss[c]);
964 
965  SCIPdebugMsg(scip, "knapsack capacity = %" SCIP_LONGINT_FORMAT "\n", capacity);
966 
967  capa = capacity + 0.1;
968 
969  for( v = nvars - 1; v >= 0 && capa >= 0 ; --v )
970  {
971  SCIPdebug( SCIP_CALL( SCIPprintVar( scip, vars[v], NULL) ) );
972  SCIPdebugMsg(scip, "weight = %" SCIP_LONGINT_FORMAT " :\n", weights[v]);
973  assert( SCIPvarIsIntegral(vars[v]) );
974 
975  /* the weights should be greater or equal to zero */
976  assert( weights[v] >= 0);
977 
978  if( !varIsUnfixedLocal(vars[v]) )
979  {
980  /* variable is fixed locally; therefore, subtract fixed variable value multiplied by
981  * the weight;
982  */
983  capa -= weights[v] * SCIPvarGetLbLocal(vars[v]);
984  }
985  else if( weights[v] >= 1 )
986  {
987  /* variable is unfixed and weight is greater than 0; therefore, subtract upper bound
988  * value multiplied by the weight
989  */
990  capa -= weights[v] * SCIPvarGetUbLocal(vars[v]);
991  }
992  }
993 
994  if( SCIPisFeasLT(scip, capa, 0.0) )
995  {
996  SCIPdebugMsg(scip, "constraint %s cannot be disabled\n", SCIPconsGetName(conss[c]));
997  SCIPdebugPrintCons(scip, conss[c], NULL);
998  (*satisfied) = FALSE;
999  }
1000  else
1001  {
1002  /* delete constraint from the problem locally since it is satisfied */
1003  SCIP_CALL( SCIPdelConsLocal(scip, conss[c]) );
1004  }
1005  }
1006  return SCIP_OKAY;
1007 }
1008 
1009 
1010 /** checks if the new solution is feasible for the bounddisjunction constraints */
1011 static
1013  SCIP* scip, /**< SCIP data structure */
1014  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
1015  int nconss, /**< number of enabled constraints */
1016  SCIP_Bool* satisfied /**< pointer to store if the logicor constraints a satisfied */
1017  )
1018 {
1019  /**@note the bounddisjunction constraints are not fully propagated; therefore, we have to check
1020  * them by hand if they are satisfied or not; if a constraint is satisfied we
1021  * delete it locally from the branch and bound tree
1022  */
1023 
1024  SCIP_CONS** conss;
1025  SCIP_VAR** vars;
1026  SCIP_BOUNDTYPE* boundtypes;
1027  SCIP_Real* bounds;
1028  SCIP_Bool satisfiedbound;
1029  int nvars;
1030  int c;
1031  int v;
1032 
1033  assert( scip != NULL );
1034  assert( conshdlr != NULL );
1035  assert( strcmp(SCIPconshdlrGetName(conshdlr),"bounddisjunction") == 0 );
1036  assert( nconss == SCIPconshdlrGetNEnabledConss(conshdlr) );
1037 
1038  conss = SCIPconshdlrGetConss(conshdlr);
1039  assert( conss != NULL );
1040 
1041  (*satisfied) = TRUE;
1042  c = SCIPconshdlrGetNActiveConss(conshdlr) - 1;
1043 
1044  for( ; c >= 0 && nconss > 0 && (*satisfied); --c )
1045  {
1046  if( !SCIPconsIsEnabled(conss[c]) )
1047  continue;
1048 
1049  nconss--;
1050  satisfiedbound = FALSE;
1051 
1052  nvars = SCIPgetNVarsBounddisjunction(scip, conss[c]);
1053  vars = SCIPgetVarsBounddisjunction(scip, conss[c]);
1054 
1055  boundtypes = SCIPgetBoundtypesBounddisjunction(scip, conss[c]);
1056  bounds = SCIPgetBoundsBounddisjunction(scip, conss[c]);
1057 
1058  for( v = nvars-1; v >= 0 && !satisfiedbound; --v )
1059  {
1060  SCIPdebug( SCIPprintVar(scip, vars[v], NULL) );
1061 
1062  /* variable should be in right bounds to delete constraint */
1063  if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER )
1064  satisfiedbound = SCIPisFeasGE(scip, SCIPvarGetLbLocal(vars[v]), bounds[v]);
1065  else
1066  {
1067  assert( boundtypes[v] == SCIP_BOUNDTYPE_UPPER );
1068  satisfiedbound = SCIPisFeasLE(scip, SCIPvarGetUbLocal(vars[v]), bounds[v]);
1069  }
1070  }
1071 
1072  if( !satisfiedbound )
1073  {
1074  SCIPdebugMsg(scip, "constraint %s cannot be disabled\n", SCIPconsGetName(conss[c]));
1075  SCIPdebugPrintCons(scip, conss[c], NULL);
1076  (*satisfied) = FALSE;
1077  }
1078  else
1079  {
1080  /* delete constraint from the problem locally since it is satisfied */
1081  SCIP_CALL( SCIPdelConsLocal(scip, conss[c]) );
1082  }
1083  }
1084  return SCIP_OKAY;
1085 }
1086 
1087 
1088 /** checks if the new solution is feasible for the varbound constraints */
1089 static
1091  SCIP* scip, /**< SCIP data structure */
1092  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
1093  int nconss, /**< number of enabled constraints */
1094  SCIP_Bool* satisfied /**< pointer to store if the logicor constraints a satisfied */
1095  )
1096 {
1097  /**@note the varbound constraints are not fully propagated; therefore, we have to check
1098  * them by hand if they are satisfied or not; if a constraint is satisfied we
1099  * delete it locally from the branch and bound tree.
1100  */
1101 
1102  SCIP_CONS** conss;
1103  SCIP_VAR* var;
1104  SCIP_VAR* vbdvar;
1105  SCIP_Real lhs;
1106  SCIP_Real rhs;
1107  SCIP_Real coef;
1108  int c;
1109 
1110  SCIPdebugMsg(scip, "check varbound %d constraints\n", nconss);
1111 
1112  assert( scip != NULL );
1113  assert( conshdlr != NULL );
1114  assert( strcmp(SCIPconshdlrGetName(conshdlr),"varbound") == 0 );
1115  assert( nconss == SCIPconshdlrGetNEnabledConss(conshdlr) );
1116 
1117  conss = SCIPconshdlrGetConss(conshdlr);
1118  assert( conss != NULL );
1119 
1120  (*satisfied) = TRUE;
1121  c = SCIPconshdlrGetNActiveConss(conshdlr) - 1;
1122 
1123  for( ; c >= 0 && nconss > 0 && (*satisfied); --c )
1124  {
1125  SCIPdebugMsg(scip, "varbound constraint %d\n", c);
1126 
1127  if( !SCIPconsIsEnabled(conss[c]) )
1128  continue;
1129 
1130  nconss--;
1131 
1132  var = SCIPgetVarVarbound(scip, conss[c]);
1133  vbdvar = SCIPgetVbdvarVarbound(scip, conss[c]);
1134 
1135  assert (SCIPvarGetType(vbdvar) != SCIP_VARTYPE_CONTINUOUS);
1136 
1137  coef = SCIPgetVbdcoefVarbound(scip, conss[c]);
1138  lhs = SCIPgetLhsVarbound(scip, conss[c]);
1139  rhs = SCIPgetRhsVarbound(scip, conss[c]);
1140 
1141  /* variables y is fixed locally; therefore, subtract fixed variable value multiplied by
1142  * the coefficient;
1143  */
1144  if(SCIPisGT(scip, SCIPvarGetUbLocal(var), rhs - SCIPvarGetUbLocal(vbdvar) * coef )
1145  || !SCIPisGE(scip, SCIPvarGetLbLocal(var), lhs - SCIPvarGetLbLocal(vbdvar) * coef ) )
1146  {
1147  SCIPdebugMsg(scip, "constraint %s cannot be disabled\n", SCIPconsGetName(conss[c]));
1148  SCIPdebugPrintCons(scip, conss[c], NULL);
1149  SCIPdebugMsg(scip, "<%s> lb: %.15g\t ub: %.15g\n", SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var));
1150  SCIPdebugMsg(scip, "<%s> lb: %.15g\t ub: %.15g\n", SCIPvarGetName(vbdvar), SCIPvarGetLbLocal(vbdvar), SCIPvarGetUbLocal(vbdvar));
1151  (*satisfied) = FALSE;
1152  }
1153  else
1154  {
1155  /* delete constraint from the problem locally since it is satisfied */
1156  SCIP_CALL( SCIPdelConsLocal(scip, conss[c]) );
1157  }
1158  }
1159 
1160  return SCIP_OKAY;
1161 }
1162 
1163 
1164 /** check if the current node initializes a non trivial unrestricted subtree */
1165 static
1167  SCIP* scip, /**< SCIP main data structure */
1168  SCIP_SOL* sol, /**< solution to check */
1169  SCIP_Bool* feasible /**< pointer to store the result of the check */
1170  )
1171 {
1172  int h;
1173 
1174  SCIP_CONSHDLR** conshdlrs;
1175  int nconshdlrs;
1176 
1177  SCIP_CONSHDLR* conshdlr;
1178  int nconss;
1179 
1180  SCIPdebugMsg(scip, "check if the sparse solution is feasible\n");
1181 
1182  assert( scip != NULL );
1183  assert( sol != NULL );
1184  assert( feasible != NULL );
1185 
1186  assert( SCIPgetNPseudoBranchCands(scip) != 0 );
1187 
1188  *feasible = FALSE;
1189 
1190  nconshdlrs = SCIPgetNConshdlrs(scip) - 1;
1191  conshdlrs = SCIPgetConshdlrs(scip);
1192  assert(conshdlrs != NULL);
1193 
1194  /* check each constraint handler if there are constraints which are not enabled */
1195  for( h = nconshdlrs ; h >= 0 ; --h )
1196  {
1197  conshdlr = conshdlrs[h];
1198  assert( conshdlr != NULL );
1199 
1200  /* skip this constraints handler */
1201  if( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 )
1202  continue;
1203 
1204  nconss = SCIPconshdlrGetNEnabledConss(conshdlr);
1205 
1206  if( nconss > 0 )
1207  {
1208  SCIP_Bool satisfied;
1209 
1210  SCIPdebugMsg(scip, "constraint handler %s has %d active constraint(s)\n",
1211  SCIPconshdlrGetName(conshdlr), nconss );
1212 
1213  if( strcmp(SCIPconshdlrGetName(conshdlr), "logicor") == 0 )
1214  {
1215  SCIP_CALL( checkLogicor(scip, conshdlr, nconss, &satisfied) );
1216  if( !satisfied )
1217  {
1218  SCIPdebugMsg(scip, "a <logicor> constraint cannot be disabled\n");
1219  return SCIP_OKAY;
1220  }
1221  }
1222  else if( strcmp(SCIPconshdlrGetName(conshdlr), "knapsack") == 0 )
1223  {
1224  SCIP_CALL( checkKnapsack(scip, conshdlr, nconss, &satisfied) );
1225  if( !satisfied )
1226  {
1227  SCIPdebugMsg(scip, "a <knapsack> constraint cannot be disabled\n");
1228  return SCIP_OKAY;
1229  }
1230  }
1231  else if( strcmp(SCIPconshdlrGetName(conshdlr), "bounddisjunction") == 0 )
1232  {
1233  SCIP_CALL( checkBounddisjunction(scip, conshdlr, nconss, &satisfied) );
1234  if( !satisfied )
1235  {
1236  SCIPdebugMsg(scip, "a <bounddisjunction> constraint cannot be disabled\n");
1237  return SCIP_OKAY;
1238  }
1239  }
1240  else if( strcmp(SCIPconshdlrGetName(conshdlr), "varbound") == 0 )
1241  {
1242  SCIP_CALL( checkVarbound(scip, conshdlr, nconss, &satisfied) );
1243  if( !satisfied )
1244  {
1245  SCIPdebugMsg(scip, "a <varbound> constraint cannot be disabled\n");
1246  return SCIP_OKAY;
1247  }
1248  }
1249  else
1250  {
1251  SCIPdebugMsg(scip, "sparse solution is infeasible since the following constraint (and maybe more) is(/are) enabled\n");
1252  SCIPdebugPrintCons(scip, SCIPconshdlrGetConss(conshdlr)[0], NULL);
1253  return SCIP_OKAY;
1254  }
1255  }
1256  }
1257 
1258  *feasible = TRUE;
1259  SCIPdebugMsg(scip, "sparse solution is feasible\n");
1260 
1261  return SCIP_OKAY;
1262 }
1263 
1264 
1265 /** check the given solution */
1266 static
1268  SCIP* scip, /**< SCIP data structure */
1269  SCIP_SOL* sol, /**< solution to add */
1270  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
1271  SCIP_RESULT* result /**< pointer to store the result of the checking process */
1272  )
1273 {
1274  SCIP_Longint nsols;
1275  SCIP_Bool feasible;
1276  SCIP_Bool valid;
1277 
1278  SCIPdebugMsg(scip, "start to add sparse solution\n");
1279 
1280  assert( scip != NULL );
1281  assert( sol != NULL );
1282  assert( conshdlrdata != NULL );
1283  assert( result != NULL );
1284 
1285  /* the solution should not be found through a heuristic since in this case the information of SCIP is not valid for
1286  * this solution
1287  */
1288 
1289  /**@todo it might be not necessary to check this assert since we can check in general all solutions of feasibility
1290  * independently of the origin; however, the locally fixed technique does only work if the solution comes from
1291  * the branch and bound tree; in case the solution comes from a heuristic we should try to sequentially fix the
1292  * variables in the branch and bound tree and check after every fixing if all constraints are disabled; at the
1293  * point where all constraints are disabled the unfixed variables are "stars" (arbitrary);
1294  */
1295  assert( SCIPgetNOrigVars(scip) != 0);
1296  assert( SCIPsolGetHeur(sol) == NULL);
1297 
1298  /* setting result to infeasible since we reject any solution; however, if the solution passes the sparse test or is
1299  * completely fixed, the result is set to SCIP_CUTOFF which cuts off the subtree initialized through the current node
1300  */
1301  *result = SCIP_INFEASIBLE;
1302 
1303 #ifdef SCIP_DEBUG
1304  {
1305  SCIP_VAR* var;
1306  SCIP_VAR** vars;
1307  int v;
1308  int nvars;
1309 
1310  nvars = SCIPgetNVars(scip);
1311  vars = SCIPgetVars(scip);
1312 
1313  for( v = 0; v < nvars; ++v )
1314  {
1315  var = vars[v];
1316  SCIPdebugMsg(scip, "variables <%s> Local Bounds are [%g,%g] Global Bounds are [%g,%g]\n",
1318  }
1319  }
1320 #endif
1321 
1322  /* check if integer variables are completely fixed */
1323  if( SCIPgetNPseudoBranchCands(scip) == 0 )
1324  {
1325  /* check solution original space */
1326  checkSolutionOrig(scip, sol, conshdlrdata);
1327 
1328  addOne(&conshdlrdata->nsols); /*lint !e545*/
1329  conshdlrdata->nNonSparseSols++;
1330 
1331  SCIPdebugMsg(scip, "-> add one to number of solutions\n");
1332 
1333  if( conshdlrdata->collect )
1334  {
1335  SCIP_CALL( collectSolution(scip, conshdlrdata, sol) );
1336  }
1337 
1338  /* in case of continuous variables are present we explicitly cutoff the integer assignment since in case of
1339  * nonlinear constraint we want to avoid to count that integer assignment again
1340  */
1341  if( conshdlrdata->continuous )
1342  {
1343  SCIP_CALL( conshdlrdata->cutoffSolution(scip, sol, conshdlrdata) );
1344  }
1345 
1346  /* since all integer are fixed, we cut off the subtree */
1347  *result = SCIP_CUTOFF;
1348  }
1349  else if( conshdlrdata->sparsetest )
1350  {
1351  SCIP_CALL( checkFeasSubtree(scip, sol, &feasible) ) ;
1352  SCIP_CALL( countSparseSol(scip, sol, feasible, conshdlrdata, result) );
1353  }
1354 
1355  /* transform the current number of solutions into a SCIP_Longint */
1356  nsols = getNCountedSols(conshdlrdata->nsols, &valid);
1357 
1358  /* check if the solution limit is hit and stop SCIP if this is the case */
1359  if( conshdlrdata->sollimit > -1 && (!valid || conshdlrdata->sollimit <= nsols) )
1360  {
1361  SCIP_CALL( SCIPinterruptSolve(scip) );
1362  }
1363 
1364  assert( *result == SCIP_INFEASIBLE || *result == SCIP_CUTOFF );
1365  SCIPdebugMsg(scip, "result is %s\n", *result == SCIP_INFEASIBLE ? "SCIP_INFEASIBLE" : "SCIP_CUTOFF" );
1366 
1367  return SCIP_OKAY;
1368 }
1369 
1370 /*
1371  * Callback methods of constraint handler
1372  */
1373 
1374 /** creates the handler for countsols constraints and includes it in SCIP */
1375 static
1377  SCIP* scip, /**< SCIP data structure */
1378  SCIP_Bool dialogs /**< sould count dialogs be added */
1379  );
1380 
1381 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
1382 static
1383 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyCountsols)
1384 { /*lint --e{715}*/
1385  SCIP_CONSHDLRDATA* conshdlrdata;
1386 
1387  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1388  assert(conshdlrdata != NULL);
1389 
1390  /* in case the countsols constraint handler is active we avoid copying to ensure a safe count */
1391  if( conshdlrdata->active )
1392  *valid = FALSE;
1393  else
1394  {
1395  assert(scip != NULL);
1396  assert(conshdlr != NULL);
1397  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1398 
1399  /* call inclusion method of constraint handler and do not add counting dialogs */
1401 
1402  *valid = TRUE;
1403  }
1404 
1405  return SCIP_OKAY;
1406 }
1407 
1408 #define consCopyCountsols NULL
1410 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
1411 static
1412 SCIP_DECL_CONSFREE(consFreeCountsols)
1413 { /*lint --e{715}*/
1414  SCIP_CONSHDLRDATA* conshdlrdata;
1415 
1416  assert(conshdlr != NULL);
1417  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1418 
1419  /* free constraint handler data */
1420  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1421  assert(conshdlrdata != NULL);
1422 
1423  /* free conshdlrdata */
1424  freeInt(&conshdlrdata->nsols); /*lint !e545*/
1425 
1426  assert( conshdlrdata->solutions == NULL );
1427  assert( conshdlrdata->nsolutions == 0 );
1428  assert( conshdlrdata->ssolutions == 0 );
1429 
1430  SCIPfreeBlockMemory(scip, &conshdlrdata);
1431  SCIPconshdlrSetData(conshdlr, NULL);
1432 
1433  return SCIP_OKAY;
1434 }
1435 
1436 /** initialization method of constraint handler (called after problem was transformed) */
1437 static
1438 SCIP_DECL_CONSINIT(consInitCountsols)
1439 { /*lint --e{715}*/
1440  SCIP_CONSHDLRDATA* conshdlrdata;
1441 
1442  assert( conshdlr != NULL );
1443  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1444 
1445  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1446  assert(conshdlrdata != NULL );
1447 
1448  /* reset counting variables */
1449  conshdlrdata->feasST = 0; /* number of non trivial unrestricted subtrees */
1450  conshdlrdata->nDiscardSols = 0; /* number of discard solutions */
1451  conshdlrdata->nNonSparseSols = 0; /* number of non sparse solutions */
1452  setInt(&conshdlrdata->nsols, 0LL); /* number of solutions */ /*lint !e545*/
1453 
1454  conshdlrdata->solutions = NULL;
1455  conshdlrdata->nsolutions = 0;
1456  conshdlrdata->ssolutions = 0;
1457 
1458  if( conshdlrdata->active )
1459  {
1460  SCIP_VAR** origvars;
1461  int norigvars;
1462  int nallvars;
1463  int v;
1464 
1465  origvars = SCIPgetOrigVars(scip);
1466  norigvars = SCIPgetNOrigVars(scip);
1467 
1468  /* get number of integral variables */
1469  conshdlrdata->nallvars = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
1470 
1471  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conshdlrdata->allvars, conshdlrdata->nallvars) );
1472 
1473  nallvars = 0;
1474 
1475  /* capture and lock all variables */
1476  for( v = 0; v < norigvars; ++v )
1477  {
1478  if( SCIPvarGetType(origvars[v]) != SCIP_VARTYPE_CONTINUOUS )
1479  {
1480  assert(nallvars < conshdlrdata->nallvars);
1481 
1482  SCIP_CALL( SCIPgetTransformedVar(scip, origvars[v], &conshdlrdata->allvars[nallvars]) );
1483  assert(conshdlrdata->allvars[nallvars] != NULL);
1484 
1485  /* capture variable to ensure that the variable will not be deleted */
1486  SCIP_CALL( SCIPcaptureVar(scip, conshdlrdata->allvars[nallvars]) );
1487 
1488  if( strncmp(SCIPvarGetName(conshdlrdata->allvars[nallvars]), "t_andresultant_", strlen("t_andresultant_")) != 0 )
1489  {
1490  /* lock variable to avoid dual reductions */
1491  SCIP_CALL( SCIPaddVarLocksType(scip, conshdlrdata->allvars[nallvars], SCIP_LOCKTYPE_MODEL, 1, 1) );
1492  }
1493 
1494  nallvars++;
1495  }
1496  }
1497  assert(nallvars == conshdlrdata->nallvars);
1498 
1499  /* check if continuous variables are present */
1500  conshdlrdata->continuous = SCIPgetNContVars(scip) > 0;
1501  }
1502 
1503  return SCIP_OKAY;
1504 }
1505 
1506 /** deinitialization method of constraint handler (called before transformed problem is freed) */
1507 static
1508 SCIP_DECL_CONSEXIT(consExitCountsols)
1509 { /*lint --e{715}*/
1510  SCIP_CONSHDLRDATA* conshdlrdata;
1511  int s;
1512  int v;
1513 
1514  assert( conshdlr != NULL );
1515  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1516 
1517  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1518  assert(conshdlrdata != NULL );
1519 
1520  /* release variables to hashmap */
1521  for( v = conshdlrdata->nvars - 1; v >= 0; --v )
1522  {
1523  SCIP_CALL( SCIPreleaseVar(scip, &(conshdlrdata->vars[v])) );
1524  }
1525 
1526  if( conshdlrdata->hashmap != NULL)
1527  {
1528  /* free hashmap of active variables to pistions */
1529  SCIPhashmapFree(&(conshdlrdata->hashmap));
1530  }
1531 
1532  /* free active variables */
1533  SCIPfreeBlockMemoryArrayNull(scip, &(conshdlrdata->vars), conshdlrdata->nvars);
1534  conshdlrdata->nvars = 0;
1535 
1536  if( conshdlrdata->allvars != NULL )
1537  {
1538  /* release and unlock all variables */
1539  for( v = 0; v < conshdlrdata->nallvars; ++v )
1540  {
1541  if( strncmp(SCIPvarGetName(conshdlrdata->allvars[v]), "t_andresultant_", strlen("t_andresultant_")) != 0 )
1542  {
1543  /* remove the previously added variable locks */
1544  SCIP_CALL( SCIPaddVarLocksType(scip, conshdlrdata->allvars[v], SCIP_LOCKTYPE_MODEL, -1, -1) );
1545  }
1546 
1547  SCIP_CALL( SCIPreleaseVar(scip, &conshdlrdata->allvars[v]) );
1548  }
1549 
1550  SCIPfreeBlockMemoryArrayNull(scip, &conshdlrdata->allvars, conshdlrdata->nallvars);
1551  conshdlrdata->nallvars = 0;
1552  }
1553 
1554  if( conshdlrdata->nsolutions > 0 )
1555  {
1556  for( s = conshdlrdata->nsolutions - 1; s >= 0 ; --s )
1557  {
1558  SCIPsparseSolFree(&(conshdlrdata->solutions[s]));
1559  }
1560 
1561  SCIPfreeMemoryArrayNull(scip, &conshdlrdata->solutions);
1562  conshdlrdata->nsolutions = 0;
1563  conshdlrdata->ssolutions = 0;
1564 
1565  assert( conshdlrdata->solutions == NULL );
1566  }
1567  conshdlrdata->continuous = FALSE;
1568 
1569  assert( conshdlrdata->solutions == NULL );
1570  assert( conshdlrdata->nsolutions == 0 );
1571  assert( conshdlrdata->ssolutions == 0 );
1572 
1573  return SCIP_OKAY;
1574 }
1575 
1576 
1577 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin)
1578  *
1579  * This method is called when the presolving was finished and the branch and bound process is about to begin.
1580  * The constraint handler may use this call to initialize its branch and bound specific data.
1581  */
1582 static
1583 SCIP_DECL_CONSINITSOL(consInitsolCountsols)
1584 { /*lint --e{715}*/
1585  SCIP_CONSHDLRDATA* conshdlrdata;
1586 
1587  assert( conshdlr != NULL );
1588  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1589 
1590  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1591  assert(conshdlrdata != NULL );
1592 
1593  if( conshdlrdata->active )
1594  {
1595  SCIP_VAR** vars;
1596  int v;
1597 
1598  assert(conshdlrdata->nsolutions == 0);
1599  assert(conshdlrdata->solutions == NULL);
1600 
1601  conshdlrdata->nvars = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
1602  vars = SCIPgetVars(scip);
1603 
1604  /* exclude upgrade continuous original variables */
1605  for( v = conshdlrdata->nvars - 1; v >= 0; --v )
1606  {
1607  SCIP_VAR* origvar;
1608  SCIP_Real scalar = 1.0;
1609  SCIP_Real constant = 0.0;
1610 
1611  origvar = vars[v];
1612 
1613  /* get original variable to decide if we will count the domain; continuous variables aren't counted */
1614  SCIP_CALL( SCIPvarGetOrigvarSum(&origvar, &scalar, &constant) );
1615 
1616  if( origvar != NULL && SCIPvarGetType(origvar) != SCIP_VARTYPE_CONTINUOUS )
1617  break;
1618  }
1619  conshdlrdata->nvars = v + 1;
1620 
1621  /* @todo we need to forbid variable downgrading, from integer type to implicit integer type, e.g. done in
1622  * cons_linear
1623  */
1624 #ifndef NDEBUG
1625  for( v = conshdlrdata->nvars - 1; v >= 0; --v )
1626  {
1627  SCIP_VAR* origvar;
1628  SCIP_Real scalar = 1.0;
1629  SCIP_Real constant = 0.0;
1630 
1631  origvar = vars[v];
1632 
1633  /* get original variable to decide if we will count the domain; continuous variables aren't counted */
1634  SCIP_CALL( SCIPvarGetOrigvarSum(&origvar, &scalar, &constant) );
1635 
1636  assert(origvar != NULL && SCIPvarGetType(origvar) != SCIP_VARTYPE_CONTINUOUS);
1637  }
1638 #endif
1639 
1640  /* copy array of active variables */
1641  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(conshdlrdata->vars), vars, conshdlrdata->nvars) );
1642 
1643  /* store mapping from all active variables to their position afetr presolving because during solving new variables
1644  * might be added and therefore could destroy writing collected solutions
1645  */
1646  SCIP_CALL( SCIPhashmapCreate(&(conshdlrdata->hashmap), SCIPblkmem(scip), conshdlrdata->nvars + 1) );
1647 
1648  /* add variables to hashmap */
1649  for( v = conshdlrdata->nvars - 1; v >= 0; --v )
1650  {
1651  assert(SCIPvarGetProbindex(conshdlrdata->vars[v]) == v);
1652  SCIP_CALL( SCIPhashmapInsertInt(conshdlrdata->hashmap, conshdlrdata->vars[v], v+1) );
1653  SCIP_CALL( SCIPcaptureVar(scip, conshdlrdata->vars[v]) );
1654  }
1655 
1656  /* check if the problem is binary (ignoring continuous variables) */
1657  if( SCIPgetNBinVars(scip) == (SCIPgetNVars(scip) - SCIPgetNContVars(scip)) )
1658  conshdlrdata->cutoffSolution = addBinaryCons;
1659  else
1660  conshdlrdata->cutoffSolution = addIntegerCons;
1661  }
1662 
1663  return SCIP_OKAY;
1664 }
1665 
1666 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
1667 static
1668 SCIP_DECL_CONSEXITSOL(consExitsolCountsols)
1669 { /*lint --e{715}*/
1670  SCIP_CONSHDLRDATA* conshdlrdata;
1671 
1672  assert(scip != NULL);
1673  assert(conshdlr != NULL);
1674  assert(nconss == 0);
1675  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1676 
1677  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1678  assert(conshdlrdata != NULL );
1679 
1680  if( conshdlrdata->active && restart )
1681  {
1682  SCIPerrorMessage("When collecting and counting solutions restarts need to be disabled (presolving/maxrestarts = 0).\n");
1683  SCIPABORT();
1684  return SCIP_INVALIDCALL; /*lint !e527*/
1685  }
1686 
1687  return SCIP_OKAY;
1688 }
1689 
1690 /** constraint enforcing method of constraint handler for LP solutions */
1691 static
1692 SCIP_DECL_CONSENFOLP(consEnfolpCountsols)
1693 { /*lint --e{715}*/
1694  SCIP_CONSHDLRDATA* conshdlrdata;
1695 
1696  SCIPdebugMsg(scip, "method SCIP_DECL_CONSENFOLP(consEnfolpCountsols)\n");
1697 
1698  assert( scip != NULL );
1699  assert( conshdlr != NULL );
1700  assert( nconss == 0 );
1701 
1702  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1703  assert( conshdlrdata != NULL );
1704 
1705  if( conshdlrdata->active )
1706  {
1707  if( !solinfeasible )
1708  {
1709  SCIP_SOL* sol;
1710 
1711  SCIP_CALL( SCIPcreateLPSol(scip, &sol, NULL ) );
1712 
1713  SCIP_CALL( checkSolution(scip, sol, conshdlrdata, result) );
1714  SCIP_CALL( SCIPfreeSol(scip, &sol) );
1715  }
1716  else
1717  *result = SCIP_INFEASIBLE;
1718  }
1719  else
1720  *result = SCIP_FEASIBLE;
1721 
1722  assert( !conshdlrdata->active || *result == SCIP_INFEASIBLE || *result == SCIP_CUTOFF );
1723 
1724  return SCIP_OKAY;
1725 }
1726 
1727 /** constraint enforcing method of constraint handler for relaxation solutions */
1728 static
1729 SCIP_DECL_CONSENFORELAX(consEnforelaxCountsols)
1730 { /*lint --e{715}*/
1731  SCIP_CONSHDLRDATA* conshdlrdata;
1732 
1733  SCIPdebugMsg(scip, "method SCIP_DECL_CONSENFORELAX(consEnfolpCountsols)\n");
1734 
1735  assert( scip != NULL );
1736  assert( conshdlr != NULL );
1737  assert( nconss == 0 );
1738 
1739  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1740  assert( conshdlrdata != NULL );
1741 
1742  if( conshdlrdata->active )
1743  {
1744  if( !solinfeasible )
1745  {
1746  SCIP_CALL( checkSolution(scip, sol, conshdlrdata, result) );
1747  }
1748  else
1749  *result = SCIP_INFEASIBLE;
1750  }
1751  else
1752  *result = SCIP_FEASIBLE;
1753 
1754  assert( !conshdlrdata->active || *result == SCIP_INFEASIBLE || *result == SCIP_CUTOFF );
1755 
1756  return SCIP_OKAY;
1757 }
1758 
1759 /** constraint enforcing method of constraint handler for pseudo solutions */
1760 static
1761 SCIP_DECL_CONSENFOPS(consEnfopsCountsols)
1762 { /*lint --e{715}*/
1763  SCIP_CONSHDLRDATA* conshdlrdata;
1764 
1765  SCIPdebugMsg(scip, "method SCIP_DECL_CONSENFOPS(consEnfopsCountsols)\n");
1766 
1767  assert( scip != NULL );
1768  assert( conshdlr != NULL );
1769  assert( nconss == 0 );
1770 
1771  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1772  assert( conshdlrdata != NULL );
1773 
1774  if( conshdlrdata->active )
1775  {
1776  if( !solinfeasible )
1777  {
1778  SCIP_SOL* sol;
1779 
1780  SCIP_CALL( SCIPcreatePseudoSol(scip, &sol, NULL ) );
1781 
1782  SCIP_CALL( checkSolution(scip, sol, conshdlrdata, result) );
1783  SCIP_CALL( SCIPfreeSol(scip, &sol) );
1784  }
1785  else
1786  *result = SCIP_INFEASIBLE;
1787  }
1788  else
1789  *result = SCIP_FEASIBLE;
1790 
1791  assert( !conshdlrdata->active || *result == SCIP_INFEASIBLE || *result == SCIP_CUTOFF );
1792 
1793  return SCIP_OKAY;
1794 }
1795 
1796 
1797 /** feasibility check method of constraint handler for integral solutions */
1798 static
1799 SCIP_DECL_CONSCHECK(consCheckCountsols)
1800 { /*lint --e{715}*/
1801  /**@todo solutions which come from scip_check should be ignored since it is not clear who
1802  * generated these solution; later we should analyze this problem */
1803  SCIP_CONSHDLRDATA* conshdlrdata;
1804 
1805  SCIPdebugMsg(scip, "method SCIP_DECL_CONSCHECK(consCheckCountsols)\n");
1806 
1807  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1808  assert( conshdlrdata != NULL );
1809 
1810  if( conshdlrdata->active )
1811  {
1812  if( !conshdlrdata->warning )
1813  {
1814  SCIPwarningMessage(scip, "a solution comes in over <SCIP_DECL_CONSCHECK(consCheckCountsols)>; currently these solutions are ignored.\n");
1815  conshdlrdata->warning = TRUE;
1816  }
1817 
1818  *result = SCIP_INFEASIBLE;
1819  }
1820  else
1821  *result = SCIP_FEASIBLE;
1822 
1823  return SCIP_OKAY;
1824 }
1825 
1826 
1827 /** variable rounding lock method of constraint handler */
1828 static
1829 SCIP_DECL_CONSLOCK(consLockCountsols)
1830 { /*lint --e{715}*/
1831  return SCIP_OKAY;
1832 }
1833 
1834 
1835 /*
1836  * Callback methods and local method for dialogs
1837  */
1838 
1839 /** dialog execution method for the count command */
1840 SCIP_DECL_DIALOGEXEC(SCIPdialogExecCountPresolve)
1841 { /*lint --e{715}*/
1842  SCIP_Bool active;
1843  int usesymmetry;
1844 
1845  SCIP_CALL( SCIPgetIntParam(scip, "misc/usesymmetry", &usesymmetry) );
1846 
1847  if ( usesymmetry != 0 )
1848  {
1849  int symcomptiming = 2;
1850 
1851  /* get timing of symmetry computation */
1852  if ( ((unsigned) usesymmetry & SYM_HANDLETYPE_SYMCONS) != 0 )
1853  {
1854  SCIP_CALL( SCIPgetIntParam(scip, "propagating/symmetry/addconsstiming", &symcomptiming) );
1855  }
1856  else if ( usesymmetry == 2 )
1857  {
1858  SCIP_CALL( SCIPgetIntParam(scip, "propagating/symmetry/ofsymcomptiming", &symcomptiming) );
1859  }
1860 
1861  if ( symcomptiming < SYM_COMPUTETIMING_AFTERPRESOL &&
1863  {
1864  SCIPerrorMessage("Symmetry handling and solution counting are not compatible. " \
1865  "You might want to disable symmetry by setting parameter <misc/usesymmetry> to 0.\n");
1866 
1867  return SCIP_INVALIDCALL;
1868  }
1869 
1870  SCIPwarningMessage(scip, "Symmetry handling has been deactivated since it is not compatible with counting.\n");
1871  SCIPwarningMessage(scip, "=> counting forces parameter <misc/usesymmetry> to 0.\n");
1872 
1873  SCIP_CALL( SCIPsetIntParam(scip, "misc/usesymmetry", 0) );
1874  }
1875 
1876  SCIP_CALL( SCIPdialoghdlrAddHistory(dialoghdlr, dialog, NULL, FALSE) );
1877  SCIPdialogMessage(scip, NULL, "\n");
1878  SCIP_CALL( SCIPgetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", &active) );
1879 
1880  switch( SCIPgetStage(scip) )
1881  {
1882  case SCIP_STAGE_INIT:
1883  SCIPdialogMessage(scip, NULL, "no problem exists\n");
1884  break;
1885 
1886  case SCIP_STAGE_PROBLEM:
1887  /* activate constraint handler cons_countsols */
1888  if( !active )
1889  {
1890  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", TRUE) );
1891  }
1892  /*lint -fallthrough*/
1894  case SCIP_STAGE_PRESOLVING:
1895  /* presolve problem */
1896  SCIP_CALL( SCIPpresolve(scip) );
1897 
1898  /* reset cons_countsols activation */
1899  if( !active )
1900  {
1901  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", FALSE) );
1902  }
1903  break;
1904 
1905  case SCIP_STAGE_PRESOLVED:
1906  case SCIP_STAGE_SOLVING:
1907  SCIPdialogMessage(scip, NULL, "problem is already presolved\n");
1908  break;
1909 
1910  case SCIP_STAGE_SOLVED:
1911  SCIPdialogMessage(scip, NULL, "problem is already (pre)solved\n");
1912  break;
1913 
1917  case SCIP_STAGE_INITSOLVE:
1918  case SCIP_STAGE_EXITSOLVE:
1919  case SCIP_STAGE_FREETRANS:
1920  case SCIP_STAGE_FREE:
1921  default:
1922  SCIPerrorMessage("invalid SCIP stage\n");
1923  return SCIP_INVALIDCALL;
1924  } /*lint --e{616}*/
1925 
1926  SCIPdialogMessage(scip, NULL, "\n");
1927  *nextdialog = SCIPdialoghdlrGetRoot(dialoghdlr);
1928 
1929  return SCIP_OKAY;
1930 }
1931 
1932 /** dialog execution method for the count command */
1933 SCIP_DECL_DIALOGEXEC(SCIPdialogExecCount)
1934 { /*lint --e{715}*/
1935  SCIP_RETCODE retcode;
1936  SCIP_Bool active;
1937 
1938  SCIP_Bool valid;
1939  SCIP_Longint nsols;
1940  int displayprimalbound;
1941  int displaygap;
1942  int displaysols;
1943  int displayfeasST;
1944  int nrestarts;
1945  int usesymmetry;
1946 
1947  SCIP_CALL( SCIPdialoghdlrAddHistory(dialoghdlr, dialog, NULL, FALSE) );
1948  SCIPdialogMessage(scip, NULL, "\n");
1949  SCIP_CALL( SCIPgetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", &active) );
1950  SCIP_CALL( SCIPgetIntParam(scip, "presolving/maxrestarts", &nrestarts) );
1951 
1952  if( nrestarts != 0 )
1953  {
1954  /* need to disable restarts, since collecting solutions won't work, but also the capturing for variables is not
1955  * correctly handled
1956  */
1957  SCIPwarningMessage(scip, "counting forces parameter <presolving/maxrestarts> to 0.\n");
1958  if( SCIPisParamFixed(scip, "presolving/maxrestarts") )
1959  {
1960  SCIP_CALL( SCIPunfixParam(scip, "presolving/maxrestarts") );
1961  }
1962  SCIP_CALL( SCIPsetIntParam(scip, "presolving/maxrestarts", 0) );
1963  }
1964 
1965  SCIP_CALL( SCIPgetIntParam(scip, "misc/usesymmetry", &usesymmetry) );
1966 
1967  if ( usesymmetry != 0 )
1968  {
1969  int symcomptiming = 2;
1970 
1971  /* get timing of symmetry computation */
1972  if ( ((unsigned) usesymmetry & SYM_HANDLETYPE_SYMCONS) != 0 )
1973  {
1974  SCIP_CALL( SCIPgetIntParam(scip, "propagating/symmetry/addconsstiming", &symcomptiming) );
1975  }
1976  else if ( usesymmetry == 2 )
1977  {
1978  SCIP_CALL( SCIPgetIntParam(scip, "propagating/symmetry/ofsymcomptiming", &symcomptiming) );
1979  }
1980 
1981  if ( symcomptiming < SYM_COMPUTETIMING_AFTERPRESOL &&
1983  {
1984  SCIPerrorMessage("Symmetry handling and solution counting are not compatible. " \
1985  "You might want to disable symmetry by setting parameter <misc/usesymmetry> to 0.\n");
1986 
1987  return SCIP_INVALIDCALL;
1988  }
1989 
1990  SCIPwarningMessage(scip, "Symmetry handling has been deactivated since it is not compatible with counting.\n");
1991  SCIPwarningMessage(scip, "=> counting forces parameter <misc/usesymmetry> to 0.\n");
1992 
1993  SCIP_CALL( SCIPsetIntParam(scip, "misc/usesymmetry", 0) );
1994  }
1995 
1996  switch( SCIPgetStage(scip) )
1997  {
1998  case SCIP_STAGE_INIT:
1999  SCIPdialogMessage(scip, NULL, "no problem exists\n");
2000  break;
2001 
2002  case SCIP_STAGE_PROBLEM:
2003  /* activate constraint handler cons_countsols */
2004  if( !active )
2005  {
2006  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", TRUE) );
2007  }
2008  /*lint -fallthrough*/
2010  case SCIP_STAGE_PRESOLVING:
2011  /* presolve problem */
2012  SCIP_CALL( SCIPpresolve(scip) );
2013  /*lint -fallthrough*/
2014  case SCIP_STAGE_PRESOLVED:
2015  /* reset activity status of constraint handler cons_countsols */
2016  if( !active )
2017  {
2018  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", FALSE) );
2019  }
2020  /*lint -fallthrough*/
2021  case SCIP_STAGE_SOLVING:
2022  /* check if the problem contains continuous variables */
2023  if( SCIPgetNContVars(scip) != 0 )
2024  {
2026  "Problem contains continuous variables (after presolving). Counting projection to integral variables!\n");
2027  }
2028 
2029  /* turn off primal bound and gap column */
2030  SCIP_CALL( SCIPgetIntParam(scip, "display/primalbound/active", &displayprimalbound) );
2031  if( displayprimalbound != 0 )
2032  {
2033  SCIP_CALL( SCIPsetIntParam(scip, "display/primalbound/active", 0) );
2034  }
2035  SCIP_CALL( SCIPgetIntParam(scip, "display/gap/active", &displaygap) );
2036  if( displaygap != 0 )
2037  {
2038  SCIP_CALL( SCIPsetIntParam(scip, "display/gap/active", 0) );
2039  }
2040 
2041  /* turn on sols and feasST column */
2042  SCIP_CALL( SCIPgetIntParam(scip, "display/sols/active", &displaysols) );
2043  if( displayprimalbound != 2 )
2044  {
2045  SCIP_CALL( SCIPsetIntParam(scip, "display/sols/active", 2) );
2046  }
2047  SCIP_CALL( SCIPgetIntParam(scip, "display/feasST/active", &displayfeasST) );
2048  if( displayprimalbound != 2 )
2049  {
2050  SCIP_CALL( SCIPsetIntParam(scip, "display/feasST/active", 2) );
2051  }
2052 
2053  /* find the countsols constraint handler */
2054  assert( SCIPfindConshdlr(scip, CONSHDLR_NAME) != NULL );
2055 
2056  retcode = SCIPcount(scip);
2057 
2058  valid = FALSE;
2059  nsols = SCIPgetNCountedSols(scip, &valid);
2060 
2061  if( valid )
2062  SCIPdialogMessage(scip, NULL, "Feasible Solutions : %" SCIP_LONGINT_FORMAT "", nsols);
2063  else
2064  {
2065  char* buffer;
2066  int buffersize = SCIP_MAXSTRLEN;
2067  int requiredsize;
2068 
2069  SCIP_CALL( SCIPallocBufferArray(scip, &buffer, buffersize) );
2070  SCIPgetNCountedSolsstr(scip, &buffer, buffersize, &requiredsize);
2071 
2072  if( requiredsize > buffersize )
2073  {
2074  SCIP_CALL( SCIPreallocBufferArray(scip, &buffer, requiredsize) );
2075  SCIPgetNCountedSolsstr(scip, &buffer, buffersize, &requiredsize);
2076  }
2077 
2078  assert( buffersize >= requiredsize );
2079  SCIPdialogMessage(scip, NULL, "Feasible Solutions : %s", buffer);
2080 
2081  SCIPfreeBufferArray(scip, &buffer);
2082  }
2083 
2084  SCIPdialogMessage(scip, NULL, " (%" SCIP_LONGINT_FORMAT " non-trivial feasible subtrees)\n", SCIPgetNCountedFeasSubtrees(scip));
2085 
2086  *nextdialog = SCIPdialoghdlrGetRoot(dialoghdlr);
2087 
2088  /* reset display columns */
2089  if( displayprimalbound != 0 )
2090  {
2091  SCIP_CALL( SCIPsetIntParam(scip, "display/primalbound/active", displayprimalbound) );
2092  }
2093  if( displaygap != 0 )
2094  {
2095  SCIP_CALL( SCIPsetIntParam(scip, "display/gap/active", displaygap) );
2096  }
2097 
2098  /* reset sols and feasST column */
2099  if( displaysols != 2 )
2100  {
2101  SCIP_CALL( SCIPsetIntParam(scip, "display/sols/active", displaysols) );
2102  }
2103  if( displayfeasST != 2 )
2104  {
2105  SCIP_CALL( SCIPsetIntParam(scip, "display/feasST/active", displayfeasST) );
2106  }
2107 
2108  /* reset cons_countsols activation */
2109  if( !active )
2110  {
2111  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", FALSE) );
2112  }
2113 
2114  /* evaluate retcode */
2115  SCIP_CALL( retcode );
2116  break;
2117 
2118  case SCIP_STAGE_SOLVED:
2119  SCIPdialogMessage(scip, NULL, "problem is already solved\n");
2120  break;
2121 
2125  case SCIP_STAGE_INITSOLVE:
2126  case SCIP_STAGE_EXITSOLVE:
2127  case SCIP_STAGE_FREETRANS:
2128  case SCIP_STAGE_FREE:
2129  default:
2130  SCIPerrorMessage("invalid SCIP stage\n");
2131  return SCIP_INVALIDCALL;
2132  } /*lint --e{616}*/
2133 
2134  SCIPdialogMessage(scip, NULL, "\n");
2135  *nextdialog = SCIPdialoghdlrGetRoot(dialoghdlr);
2136 
2137  return SCIP_OKAY;
2138 }
2139 
2140 /** comparison method for sorting variables by non-decreasing w.r.t. problem index */
2141 static
2142 SCIP_DECL_SORTPTRCOMP(varCompProbindex)
2144  SCIP_VAR* var1;
2145  SCIP_VAR* var2;
2146 
2147  var1 = (SCIP_VAR*)elem1;
2148  var2 = (SCIP_VAR*)elem2;
2149 
2150  assert(var1 != NULL);
2151  assert(var2 != NULL);
2152 
2153  if( SCIPvarGetProbindex(var1) < SCIPvarGetProbindex(var2) )
2154  return -1;
2155  else if( SCIPvarGetProbindex(var1) > SCIPvarGetProbindex(var2) )
2156  return +1;
2157  else
2158  {
2159  assert(var1 == var2 || (SCIPvarGetProbindex(var1) == -1 && SCIPvarGetProbindex(var2) == -1));
2160  return 0;
2161  }
2162 }
2163 
2164 /** expands the sparse solutions and writes them to the file */
2165 static
2167  SCIP* scip, /**< SCIP data structure */
2168  FILE* file, /**< file handler */
2169  SCIP_VAR** allvars, /**< SCIP variables */
2170  int nallvars, /**< number of all variables */
2171  SCIP_VAR** activevars, /**< SCIP variables */
2172  int nactivevars, /**< number of active variables */
2173  SCIP_HASHMAP* hashmap, /**< hashmap from active solution variable to the position in the active
2174  * variables array
2175  */
2176  SCIP_SPARSESOL** sols, /**< sparse solutions to expands and write */
2177  int nsols /**< number of sparse solutions */
2178  )
2179 {
2180  SCIP_SPARSESOL* sparsesol;
2181  SCIP_VAR** vars;
2182  SCIP_Real* scalars;
2183  SCIP_Longint* sol;
2184  SCIP_Longint solcnt;
2185  int s;
2186  int v;
2187 
2188  assert(scip != NULL);
2189  assert(file != NULL);
2190  assert(hashmap != NULL);
2191  assert(allvars != NULL || nallvars == 0);
2192  assert(activevars != NULL || nactivevars == 0);
2193  assert(sols != NULL || nsols == 0);
2194 
2195  solcnt = 0;
2196 
2197  /* get memory to store active solution */
2198  SCIP_CALL( SCIPallocBufferArray(scip, &sol, nactivevars) );
2199  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nactivevars) );
2200  SCIP_CALL( SCIPallocBufferArray(scip, &scalars, nactivevars) );
2201 
2202  /* loop over all sparse solutions */
2203  for( s = 0; s < nsols; ++s )
2204  {
2205  sparsesol = sols[s]; /*lint !e613*/
2206  assert(sparsesol != NULL);
2207  assert(SCIPsparseSolGetNVars(sparsesol) == nactivevars);
2208 
2209  /* get first solution of the sparse solution */
2210  SCIPsparseSolGetFirstSol(sparsesol, sol, nactivevars);
2211 
2212  do
2213  {
2214  SCIP_Real objval;
2215 
2216  solcnt++;
2217 
2218  /* print solution number */
2219  SCIPinfoMessage(scip, file, "%d(%" SCIP_LONGINT_FORMAT "), ", s+1, solcnt);
2220 
2221  objval = 0.0;
2222 
2223  /* write none active variables */
2224  for( v = 0; v < nallvars; ++v )
2225  {
2226  SCIP_Real constant;
2227  SCIP_Real realvalue;
2228  int requiredsize;
2229  int nvars;
2230  int idx;
2231  int i;
2232 
2233  vars[0] = allvars[v]; /*lint !e613*/
2234  scalars[0] = 1.0;
2235  nvars = 1;
2236  constant = 0.0;
2237 
2238  SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, scalars, &nvars, nallvars, &constant, &requiredsize, TRUE) );
2239  assert(requiredsize <= nallvars);
2240  assert(nvars <= nactivevars);
2241 
2242  realvalue = constant;
2243 
2244  for( i = 0; i < nvars; ++i )
2245  {
2246  assert(SCIPhashmapExists(hashmap, vars[i]));
2247  idx = SCIPhashmapGetImageInt(hashmap, vars[i]) - 1;
2248  assert(0 <= idx && idx < nactivevars);
2249  assert(activevars[idx] == vars[i]); /*lint !e613*/
2250 
2251  objval += SCIPvarGetObj(vars[i]) * sol[idx];
2252  realvalue += scalars[i] * sol[idx];
2253  }
2254  assert(SCIPisIntegral(scip, realvalue));
2255 
2256  SCIPinfoMessage(scip, file, "%g, ", realvalue);
2257  }
2258 
2259  /* transform objective value into original problem space */
2260  objval = SCIPretransformObj(scip, objval);
2261 
2262  /* output the objective value of the solution */
2263  SCIPinfoMessage(scip, file, "%g\n", objval);
2264  }
2265  while( SCIPsparseSolGetNextSol(sparsesol, sol, nactivevars) );
2266  }
2267 
2268  /* free buffer arrays */
2269  SCIPfreeBufferArray(scip, &scalars);
2270  SCIPfreeBufferArray(scip, &vars);
2271  SCIPfreeBufferArray(scip, &sol);
2272 
2273  return SCIP_OKAY;
2274 }
2275 
2276 /** execution method of dialog for writing all solutions */
2277 SCIP_DECL_DIALOGEXEC(SCIPdialogExecWriteAllsolutions)
2278 { /*lint --e{715}*/
2279  FILE* file;
2280  SCIP_Longint nsols;
2281  char* filename;
2282  char* word;
2283  SCIP_Bool endoffile;
2284  SCIP_Bool valid;
2285 
2286  assert( scip != NULL );
2287 
2288  SCIP_CALL( SCIPdialoghdlrAddHistory(dialoghdlr, dialog, NULL, FALSE) );
2289 
2290  switch( SCIPgetStage(scip) )
2291  {
2292  case SCIP_STAGE_INIT:
2293  SCIPdialogMessage(scip, NULL, "no problem available\n");
2294  break;
2295  case SCIP_STAGE_PROBLEM:
2297  case SCIP_STAGE_FREETRANS:
2298  SCIPdialogMessage(scip, NULL, "the counting process was not started yet\n");
2299  break;
2302  case SCIP_STAGE_PRESOLVING:
2304  case SCIP_STAGE_PRESOLVED:
2305  case SCIP_STAGE_INITSOLVE:
2306  case SCIP_STAGE_SOLVING:
2307  case SCIP_STAGE_SOLVED:
2308  case SCIP_STAGE_EXITSOLVE:
2309  {
2310  SCIP_CONSHDLR* conshdlr;
2311  SCIP_CONSHDLRDATA* conshdlrdata;
2312  int nsparsesols;
2313 
2314  valid = FALSE;
2315  nsols = SCIPgetNCountedSols(scip, &valid);
2316 
2317  /* find the countsols constraint handler */
2318  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2319  assert( conshdlr != NULL );
2320 
2321  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2322  assert( conshdlrdata != NULL );
2323 
2324  nsparsesols = conshdlrdata->nsolutions;
2325 
2326  if( !valid )
2327  {
2328  /* too many solutions, output not "possible" */
2329  char* buffer;
2330  int buffersize;
2331  int requiredsize;
2332 
2333  buffersize = SCIP_MAXSTRLEN;
2334 
2335  SCIP_CALL( SCIPallocBufferArray(scip, &buffer, buffersize) );
2336  SCIPgetNCountedSolsstr(scip, &buffer, buffersize, &requiredsize);
2337 
2338  if( requiredsize > buffersize )
2339  {
2340  buffersize = requiredsize;
2341  SCIP_CALL( SCIPreallocBufferArray(scip, &buffer, requiredsize) );
2342  SCIPgetNCountedSolsstr(scip, &buffer, buffersize, &requiredsize);
2343  }
2344 
2345  assert( buffersize >= requiredsize );
2346  SCIPdialogMessage(scip, NULL, "no output, because of too many feasible solutions : %s\n", buffer);
2347 
2348  SCIPfreeBufferArray(scip, &buffer);
2349  }
2350  else if( nsols == 0 )
2351  {
2352  SCIPdialogMessage(scip, NULL, "there are no counted solutions\n");
2353  }
2354  else if( nsparsesols == 0 )
2355  {
2356  SCIPdialogMessage(scip, NULL, "there is no solution collect (set parameter <constraints/countsols/collect> to TRUE)\n");
2357  }
2358  else
2359  {
2360  SCIP_CALL( SCIPdialoghdlrGetWord(dialoghdlr, dialog, "enter filename: ", &word, &endoffile) );
2361 
2362  /* copy the filename for later use */
2363  SCIP_CALL( SCIPduplicateBufferArray(scip, &filename, word, (int)strlen(word)+1) );
2364 
2365  if( endoffile )
2366  {
2367  *nextdialog = NULL;
2368  return SCIP_OKAY;
2369  }
2370 
2371  SCIP_CALL( SCIPdialoghdlrAddHistory(dialoghdlr, dialog, filename, TRUE) );
2372 
2373  if( filename[0] != '\0' )
2374  {
2375  file = fopen(filename, "w");
2376 
2377  if( file == NULL )
2378  {
2379  SCIPdialogMessage(scip, NULL, "error creating file <%s>\n", filename);
2380  SCIPdialoghdlrClearBuffer(dialoghdlr);
2381  }
2382  else
2383  {
2384  SCIP_SPARSESOL** sparsesols;
2385  SCIP_VAR** origvars;
2386  SCIP_VAR** allvars;
2387  int norigvars;
2388  int nvars;
2389  int v;
2390 
2391  SCIP_RETCODE retcode;
2392 
2393  /* get sparse solutions defined over the active variables */
2394  nvars = conshdlrdata->nvars;
2395  sparsesols = conshdlrdata->solutions;
2396 
2397  /* get original problem variables */
2398  retcode = SCIPallocBufferArray(scip, &origvars, SCIPgetNOrigVars(scip));
2399  if( retcode != SCIP_OKAY )
2400  {
2401  fclose(file);
2402  SCIP_CALL( retcode );
2403  }
2404 
2405  norigvars = 0;
2406 
2407  for( v = 0; v < SCIPgetNOrigVars(scip); ++v )
2408  {
2410  {
2411  origvars[norigvars] = SCIPgetOrigVars(scip)[v];
2412  norigvars++;
2413  }
2414  }
2415  assert(norigvars == conshdlrdata->nallvars);
2416 
2417  retcode = SCIPduplicateBufferArray(scip, &allvars, conshdlrdata->allvars, norigvars);
2418  if( retcode != SCIP_OKAY )
2419  {
2420  fclose(file); /*lint !e449*/
2421  SCIP_CALL( retcode );
2422  }
2423 
2424  /* sort original variables array and the corresponding transformed variables w.r.t. the problem index */
2425  SCIPsortDownPtrPtr((void**)allvars, (void**)origvars, varCompProbindex, norigvars);
2426 
2427  SCIPdialogMessage(scip, NULL, "saving %" SCIP_LONGINT_FORMAT " (%d) feasible solutions\n", nsols, nsparsesols);
2428 
2429  /* first row: output the names of the variables in the given ordering */
2430  SCIPinfoMessage(scip, file, "#, ");
2431 
2432  for( v = 0; v < norigvars; ++v )
2433  {
2434 #ifndef NDEBUG
2435  {
2436  /* check if the original variable fits to the transformed variable the constraint handler has stored */
2437  SCIP_VAR* transvar;
2438  SCIP_CALL( SCIPgetTransformedVar(scip, origvars[v], &transvar) );
2439  assert(transvar != NULL);
2440  assert(transvar == allvars[v]);
2441  }
2442 #endif
2443  SCIPinfoMessage(scip, file, "%s, ", SCIPvarGetName(origvars[v]));
2444  }
2445 
2446  SCIPinfoMessage(scip, file, "objval\n");
2447 
2448  /* expand and write solution */
2449  retcode = writeExpandedSolutions(scip, file, allvars, conshdlrdata->nallvars, conshdlrdata->vars, nvars, conshdlrdata->hashmap, sparsesols, nsparsesols);
2450  if( retcode != SCIP_OKAY )
2451  {
2452  fclose(file);
2453  SCIP_CALL( retcode );
2454  }
2455  SCIPdialogMessage(scip, NULL, "written solutions information to file <%s>\n", filename);
2456 
2457  SCIPfreeBufferArray(scip, &allvars);
2458  SCIPfreeBufferArray(scip, &origvars);
2459 
2460  fclose(file);
2461  }
2462 
2463  /* free buffer array */
2464  SCIPfreeBufferArray(scip, &filename);
2465  }
2466  }
2467  break;
2468  }
2469  case SCIP_STAGE_FREE:
2470  SCIPerrorMessage("invalid call during SCIP_STAGE_FREE\n");
2471  return SCIP_ERROR;
2472  }
2473 
2474  *nextdialog = SCIPdialoghdlrGetRoot(dialoghdlr);
2475 
2476  return SCIP_OKAY;
2477 }
2478 
2479 /** create the interactive shell dialogs for the counting process */
2480 static
2482  SCIP* scip /**< SCIP data structure */
2483  )
2484 {
2485  SCIP_DIALOG* root;
2486  SCIP_DIALOG* dialog;
2487  SCIP_DIALOG* submenu;
2488 
2489  root = SCIPgetRootDialog(scip);
2490 
2491  /* skip dialogs if they seem to be disabled */
2492  if( root == NULL )
2493  return SCIP_OKAY;
2494 
2495  /* add dialog entry for counting */
2496  if( !SCIPdialogHasEntry(root, "count") )
2497  {
2498  SCIP_CALL( SCIPincludeDialog(scip, &dialog, NULL, SCIPdialogExecCount, NULL, NULL,
2499  "count", "count number of feasible solutions", FALSE, NULL) );
2500  SCIP_CALL( SCIPaddDialogEntry(scip, root, dialog) );
2501  SCIP_CALL( SCIPreleaseDialog(scip, &dialog) );
2502  }
2503 
2504  /* add dialog entry for counting */
2505  if( !SCIPdialogHasEntry(root, "countpresolve") )
2506  {
2507  SCIP_CALL( SCIPincludeDialog(scip, &dialog, NULL, SCIPdialogExecCountPresolve, NULL, NULL,
2508  "countpresolve", "presolve instance before counting number of feasible solutions", FALSE, NULL) );
2509  SCIP_CALL( SCIPaddDialogEntry(scip, root, dialog) );
2510  SCIP_CALL( SCIPreleaseDialog(scip, &dialog) );
2511  }
2512 
2513  /* search for the "write" sub menu to add "allsolutions" dialog */
2514  if( SCIPdialogFindEntry(root, "write", &submenu) != 1 )
2515  {
2516  SCIPerrorMessage("write sub menu not found\n");
2517  return SCIP_PLUGINNOTFOUND;
2518  }
2519  assert(submenu != NULL);
2520 
2521  /* add dialog "allsolutions" to sub menu "write" */
2522  if( !SCIPdialogHasEntry(submenu, "allsolutions") )
2523  {
2524  SCIP_CALL( SCIPincludeDialog(scip, &dialog, NULL, SCIPdialogExecWriteAllsolutions, NULL, NULL,
2525  "allsolutions", "write all counted primal solutions to file", FALSE, NULL) );
2526  SCIP_CALL( SCIPaddDialogEntry(scip, submenu, dialog) );
2527  SCIP_CALL( SCIPreleaseDialog(scip, &dialog) );
2528  }
2529 
2530  return SCIP_OKAY;
2531 }
2532 
2533 /*
2534  * Callback methods for columns
2535  */
2536 
2537 /** output method of display column to output file stream 'file' */
2538 static
2539 SCIP_DECL_DISPOUTPUT(dispOutputSols)
2540 { /*lint --e{715}*/
2541 #ifndef NDEBUG
2542  SCIP_CONSHDLR* conshdlr;
2543 #endif
2544  SCIP_Longint sols;
2545  SCIP_Bool valid;
2546 
2547  assert(disp != NULL);
2548  assert(strcmp(SCIPdispGetName(disp), DISP_SOLS_NAME) == 0);
2549  assert(scip != NULL);
2550 
2551 #ifndef NDEBUG
2552  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2553  assert( conshdlr != NULL );
2554  assert( SCIPconshdlrGetNConss(conshdlr) == 0 );
2555 #endif
2556 
2557  sols = SCIPgetNCountedSols(scip, &valid);
2558 
2559  if( !valid )
2560  {
2561  SCIPinfoMessage(scip, file, "TooMany");
2562  }
2563  else
2564  {
2566  }
2567 
2568  return SCIP_OKAY;
2569 }
2570 
2571 
2572 /** output method of display column to output file stream 'file' */
2573 static
2574 SCIP_DECL_DISPOUTPUT(dispOutputFeasSubtrees)
2575 { /*lint --e{715}*/
2576 #ifndef NDEBUG
2577  SCIP_CONSHDLR* conshdlr;
2578 #endif
2579 
2580  assert(disp != NULL);
2581  assert(scip != NULL);
2582  assert(strcmp(SCIPdispGetName(disp), DISP_CUTS_NAME) == 0);
2583 
2584 #ifndef NDEBUG
2585  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2586  assert( conshdlr != NULL );
2587  assert( SCIPconshdlrGetNConss(conshdlr) == 0 );
2588 #endif
2589 
2591 
2592  return SCIP_OKAY;
2593 }
2594 
2595 
2596 /*
2597  * Interface methods of constraint handler
2598  */
2599 
2600 /** creates the handler for countsols constraints and includes it in SCIP */
2601 static
2603  SCIP* scip, /**< SCIP data structure */
2604  SCIP_Bool dialogs /**< sould count dialogs be added */
2605  )
2606 {
2607  /* create countsol constraint handler data */
2608  SCIP_CONSHDLRDATA* conshdlrdata;
2609  SCIP_CONSHDLR* conshdlr;
2610 
2611 #ifdef SCIP_WITH_GMP
2612  char gmpversion[20];
2613 #endif
2614 
2615  /* create constraint handler specific data here */
2616  SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata) );
2617 
2618  /* include constraint handler */
2621  consEnfolpCountsols, consEnfopsCountsols, consCheckCountsols, consLockCountsols,
2622  conshdlrdata) );
2623 
2624  assert(conshdlr != NULL);
2625 
2626  /* set non-fundamental callbacks via specific setter functions */
2627  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyCountsols, consCopyCountsols) );
2628  SCIP_CALL( SCIPsetConshdlrExit(scip, conshdlr, consExitCountsols) );
2629  SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolCountsols) );
2630  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeCountsols) );
2631  SCIP_CALL( SCIPsetConshdlrInit(scip, conshdlr, consInitCountsols) );
2632  SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolCountsols) );
2633  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxCountsols) );
2634 
2635  /* add countsols constraint handler parameters */
2637  "constraints/" CONSHDLR_NAME "/active",
2638  "is the constraint handler active?",
2639  &conshdlrdata->active, FALSE, DEFAULT_ACTIVE, NULL, NULL));
2641  "constraints/" CONSHDLR_NAME "/sparsetest",
2642  "should the sparse solution test be turned on?",
2643  &conshdlrdata->sparsetest, FALSE, DEFAULT_SPARSETEST, NULL, NULL));
2645  "constraints/" CONSHDLR_NAME "/discardsols",
2646  "is it allowed to discard solutions?",
2647  &conshdlrdata->discardsols, FALSE, DEFAULT_DISCARDSOLS, NULL, NULL));
2649  "constraints/" CONSHDLR_NAME "/collect",
2650  "should the solutions be collected?",
2651  &conshdlrdata->collect, FALSE, DEFAULT_COLLECT, NULL, NULL));
2653  "constraints/" CONSHDLR_NAME "/sollimit",
2654  "counting stops, if the given number of solutions were found (-1: no limit)",
2655  &conshdlrdata->sollimit, FALSE, DEFAULT_SOLLIMIT, -1LL, SCIP_LONGINT_MAX, NULL, NULL));
2656 
2657  /* create the interactive shell dialogs for the counting process */
2658  if( dialogs )
2659  {
2660  SCIP_CALL( createCountDialog(scip) );
2661  }
2662 
2663  /* include display column */
2665  NULL, NULL, NULL, NULL, NULL, NULL, dispOutputSols,
2668  NULL, NULL, NULL, NULL, NULL, NULL, dispOutputFeasSubtrees,
2670 
2671 #ifdef SCIP_WITH_GMP
2672 #ifdef mpir_version
2673  /* add info about using MPIR to external codes information */
2674  (void) SCIPsnprintf(gmpversion, (int) sizeof(gmpversion), "MPIR %s", mpir_version);
2675  SCIP_CALL( SCIPincludeExternalCodeInformation(scip, gmpversion, "Multiple Precision Integers and Rationals Library developed by W. Hart (mpir.org)") );
2676 #else
2677  /* add info about using GMP to external codes information */
2678  (void) SCIPsnprintf(gmpversion, (int) sizeof(gmpversion), "GMP %s", gmp_version);
2679  SCIP_CALL( SCIPincludeExternalCodeInformation(scip, gmpversion, "GNU Multiple Precision Arithmetic Library developed by T. Granlund (gmplib.org)") );
2680 #endif
2681 #endif
2682 
2683  return SCIP_OKAY;
2684 }
2685 
2686 /** creates the handler for countsols constraints and includes it in SCIP */
2688  SCIP* scip /**< SCIP data structure */
2689  )
2690 {
2691  /* include constraint handler including the count dialog */
2693 
2694  return SCIP_OKAY;
2695 }
2696 
2697 
2698 /** execute counting */
2700  SCIP* scip /**< SCIP data structure */
2701  )
2702 {
2703  SCIP_Bool active;
2704 
2705  /* activate constraint handler cons_countsols */
2706  SCIP_CALL( SCIPgetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", &active) );
2707  if( !active )
2708  {
2709  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", TRUE) );
2710  }
2711 
2712  /* check if the parameter setting allows a valid counting process */
2713  SCIP_CALL( checkParameters(scip) );
2714 
2715  /* start the solving process */
2716  SCIP_CALL( SCIPsolve(scip) );
2717 
2718  /* reset activity status of constraint handler cons_countsols */
2719  if( !active )
2720  {
2721  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", FALSE) );
2722  }
2723 
2724  return SCIP_OKAY;
2725 }
2726 
2727 
2728 /** returns number of feasible solutions found as SCIP_Longint; if the number does not fit into
2729  * a SCIP_Longint the valid flag is set to FALSE
2730  */
2732  SCIP* scip, /**< SCIP data structure */
2733  SCIP_Bool* valid /**< pointer to store if the return value is valid */
2734  )
2735 {
2736  SCIP_CONSHDLR* conshdlr;
2737  SCIP_CONSHDLRDATA* conshdlrdata;
2738 
2739  /* find the countsols constraint handler */
2740  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2741  assert( conshdlr != NULL );
2742 
2743  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2744  assert( conshdlrdata != NULL );
2745 
2746  return getNCountedSols(conshdlrdata->nsols, valid);
2747 }
2748 
2749 
2750 /** puts the number of counted solutions in the given char* buffer */
2752  SCIP* scip, /**< SCIP data structure */
2753  char** buffer, /**< buffer to store the number for counted solutions */
2754  int buffersize, /**< buffer size */
2755  int* requiredsize /**< pointer to store the required size */
2756  )
2757 {
2758  SCIP_CONSHDLR* conshdlr;
2759  SCIP_CONSHDLRDATA* conshdlrdata;
2760 
2761  /* find the countsols constraint handler */
2762  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2763  assert( conshdlr != NULL );
2764 
2765  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2766  assert( conshdlrdata != NULL );
2767 
2768 #ifdef SCIP_WITH_GMP
2769  /* size must be by two larger than the length of the string, since there need to be storage for a sign and a
2770  * null-termination
2771  */
2772  assert(0 <= (int) (mpz_sizeinbase( conshdlrdata->nsols, 10 ) + 2));
2773  *requiredsize = (int) (mpz_sizeinbase( conshdlrdata->nsols, 10 ) + 2);
2774  if( *requiredsize <= buffersize)
2775  toString(conshdlrdata->nsols, buffer, buffersize);
2776 #else
2777  if( conshdlrdata->nsols < pow(10.0, (double)buffersize) )
2778  {
2779  toString(conshdlrdata->nsols, buffer, buffersize);
2780  *requiredsize = (int)strlen(*buffer);
2781  }
2782  else
2783  *requiredsize = 21;
2784 #endif
2785 }
2786 
2787 
2788 /** returns number of counted non trivial feasible subtrees */
2790  SCIP* scip /**< SCIP data structure */
2791  )
2792 {
2793  SCIP_CONSHDLR* conshdlr;
2794  SCIP_CONSHDLRDATA* conshdlrdata;
2795 
2796  assert( scip != NULL );
2797 
2798  /* find the countsols constraint handler */
2799  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2800  assert( conshdlr != NULL );
2801 
2802  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2803  assert( conshdlrdata != NULL );
2804 
2805  return conshdlrdata->feasST;
2806 }
2807 
2808 
2809 /** Method to get the sparse solution.
2810  *
2811  * @note You get the pointer to the sparse solutions stored in the constraint handler (not a copy).
2812  *
2813  * @note The sparse solutions are stored w.r.t. the active variables. There are the variables which have not been removed
2814  * during presolving. For none active variables the value has to be computed depending on their aggregation
2815  * type. See for more details about that \ref COLLECTALLFEASEBLES.
2816  */
2818  SCIP* scip, /**< SCIP data structure */
2819  SCIP_VAR*** vars, /**< pointer to active variable array defining to variable order */
2820  int* nvars, /**< number of active variables */
2821  SCIP_SPARSESOL*** sols, /**< pointer to the solutions */
2822  int* nsols /**< pointer to number of solutions */
2823  )
2824 {
2825  SCIP_CONSHDLR* conshdlr;
2826  SCIP_CONSHDLRDATA* conshdlrdata;
2827 
2828  assert( scip != NULL );
2829 
2830  /* find the countsols constraint handler */
2831  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2832  assert( conshdlr != NULL );
2833 
2834  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2835  assert( conshdlrdata != NULL );
2836 
2837  *vars = conshdlrdata->vars;
2838  *nvars = conshdlrdata->nvars;
2839  *sols = conshdlrdata->solutions;
2840  *nsols = conshdlrdata->nsolutions;
2841 }
2842 
2843 /** setting SCIP parameters for such that a valid counting process is possible */
2845  SCIP* scip /**< SCIP data structure */
2846  )
2847 {
2849  return SCIP_OKAY;
2850 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
static SCIP_RETCODE createCountDialog(SCIP *scip)
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:59
void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata)
Definition: cons.c:4229
#define DISP_SOLS_STRIPLINE
#define NULL
Definition: def.h:267
SCIP_Bool SCIPconsIsEnabled(SCIP_CONS *cons)
Definition: cons.c:8313
#define DISP_SOLS_DESC
#define DISP_SOLS_HEADER
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#define CONSHDLR_ENFOPRIORITY
static SCIP_RETCODE checkBounddisjunction(SCIP *scip, SCIP_CONSHDLR *conshdlr, int nconss, SCIP_Bool *satisfied)
void SCIPdialoghdlrClearBuffer(SCIP_DIALOGHDLR *dialoghdlr)
Definition: dialog.c:446
#define DISP_SOLS_WIDTH
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for SCIP parameter handling
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:380
#define CONSHDLR_EAGERFREQ
void SCIPsparseSolGetFirstSol(SCIP_SPARSESOL *sparsesol, SCIP_Longint *sol, int nvars)
Definition: misc.c:869
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Constraint handler for variable bound constraints .
void SCIPdialogMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:191
#define SCIPfreeMemoryArrayNull(scip, ptr)
Definition: scip_mem.h:81
static SCIP_RETCODE checkKnapsack(SCIP *scip, SCIP_CONSHDLR *conshdlr, int nconss, SCIP_Bool *satisfied)
public methods for memory management
SCIP_RETCODE SCIPaddDialogEntry(SCIP *scip, SCIP_DIALOG *dialog, SCIP_DIALOG *subdialog)
Definition: scip_dialog.c:171
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
#define CUTOFF_CONSTRAINT(x)
int SCIPgetNVarsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetLhsVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18079
int SCIPgetNVarsLogicor(SCIP *scip, SCIP_CONS *cons)
#define SCIP_MAXSTRLEN
Definition: def.h:288
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:323
static void addOne(Int *value)
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip_prob.c:2432
SCIP_VAR ** SCIPgetVarsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18135
#define SCIP_CALL_FINALLY(x, y)
Definition: def.h:422
SCIP_RETCODE SCIPcreateConsSetcover(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_setppc.c:9475
int SCIPgetNPseudoBranchCands(SCIP *scip)
Definition: scip_branch.c:758
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:64
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void SCIPdispLongint(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, SCIP_Longint val, int width)
Definition: disp.c:581
public solving methods
SCIP_Real * SCIPgetBoundsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
int SCIPconshdlrGetNEnabledConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4682
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1441
SCIP_Bool SCIPsparseSolGetNextSol(SCIP_SPARSESOL *sparsesol, SCIP_Longint *sol, int nvars)
Definition: misc.c:892
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1250
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17600
static void setPowerOfTwo(Int *value, SCIP_Longint exponent)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE checkParameters(SCIP *scip)
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4595
#define FALSE
Definition: def.h:94
SCIP_RETCODE SCIPcount(SCIP *scip)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:111
void SCIPgetNCountedSolsstr(SCIP *scip, char **buffer, int buffersize, int *requiredsize)
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip_cons.c:181
static SCIP_DECL_CONSENFORELAX(consEnforelaxCountsols)
#define CONSHDLR_NEEDSCONS
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
#define TRUE
Definition: def.h:93
#define SCIPdebug(x)
Definition: pub_message.h:93
#define CONSHDLR_NAME
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
#define CONSHDLR_CHECKPRIORITY
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3192
static void multInt(Int *value, SCIP_Longint factor)
static SCIP_DECL_CONSENFOPS(consEnfopsCountsols)
SCIP_HEUR ** SCIPgetHeurs(SCIP *scip)
Definition: scip_heur.c:271
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17769
int SCIPdialogFindEntry(SCIP_DIALOG *dialog, const char *entryname, SCIP_DIALOG **subdialog)
Definition: dialog.c:1028
SCIP_VAR ** SCIPgetOrigVars(SCIP *scip)
Definition: scip_prob.c:2405
#define consCopyCountsols
public methods for displaying runtime statistics
public methods for problem variables
static GRAPHNODE ** active
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
SCIP_VAR ** SCIPgetVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_MESSAGEHDLR * SCIPgetMessagehdlr(SCIP *scip)
Definition: scip_message.c:88
SCIP_VAR ** vars
Definition: struct_misc.h:48
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
SCIP_DECL_DIALOGEXEC(SCIPdialogExecCountPresolve)
#define SCIP_LONGINT_MAX
Definition: def.h:159
#define DISP_CUTS_STRIPLINE
SCIP_RETCODE SCIPcreateLPSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:226
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
SCIP_VAR * SCIPgetVarVarbound(SCIP *scip, SCIP_CONS *cons)
Constraint handler for counting feasible solutions.
Constraint handler for the set partitioning / packing / covering constraints .
static void checkSolutionOrig(SCIP *scip, SCIP_SOL *sol, SCIP_CONSHDLRDATA *conshdlrdata)
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:102
#define DISP_CUTS_PRIORITY
public methods for SCIP variables
static SCIP_RETCODE conshdlrdataCreate(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
#define SCIPdebugMsg
Definition: scip_message.h:78
static SCIP_DECL_CONSFREE(consFreeCountsols)
static SCIP_DECL_CONSEXIT(consExitCountsols)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2172
void SCIPgetCountedSparseSols(SCIP *scip, SCIP_VAR ***vars, int *nvars, SCIP_SPARSESOL ***sols, int *nsols)
#define SYM_HANDLETYPE_SYMCONS
Definition: type_symmetry.h:94
public methods for numerical tolerances
int SCIPgetNConshdlrs(SCIP *scip)
Definition: scip_cons.c:965
SCIP_Longint SCIPgetNCountedSols(SCIP *scip, SCIP_Bool *valid)
static void freeInt(Int *value)
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3423
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4261
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyCountsols)
SCIP_DIALOG * SCIPgetRootDialog(SCIP *scip)
Definition: scip_dialog.c:157
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18089
static SCIP_DECL_CONSINITSOL(consInitsolCountsols)
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:444
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
SCIP_RETCODE SCIPincludeDialog(SCIP *scip, SCIP_DIALOG **dialog, SCIP_DECL_DIALOGCOPY((*dialogcopy)), SCIP_DECL_DIALOGEXEC((*dialogexec)), SCIP_DECL_DIALOGDESC((*dialogdesc)), SCIP_DECL_DIALOGFREE((*dialogfree)), const char *name, const char *desc, SCIP_Bool issubmenu, SCIP_DIALOGDATA *dialogdata)
Definition: scip_dialog.c:59
public methods for managing constraints
Constraint handler for knapsack constraints of the form , x binary and .
SCIP_Real SCIPgetRhsVarbound(SCIP *scip, SCIP_CONS *cons)
static SCIP_DECL_CONSENFOLP(consEnfolpCountsols)
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2486
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:347
#define DISP_SOLS_POSITION
SCIP_Longint * SCIPsparseSolGetLbs(SCIP_SPARSESOL *sparsesol)
Definition: misc.c:849
#define SCIPerrorMessage
Definition: pub_message.h:64
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4199
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:219
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2770
SCIP_CONSHDLR ** SCIPgetConshdlrs(SCIP *scip)
Definition: scip_cons.c:954
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:3474
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:429
SCIP_RETCODE SCIPpresolve(SCIP *scip)
Definition: scip_solve.c:2316
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8216
#define SCIPreallocMemoryArray(scip, ptr, newnum)
Definition: scip_mem.h:70
SCIP_RETCODE SCIPcreateConsBounddisjunction(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_BOUNDTYPE *boundtypes, SCIP_Real *bounds, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPcheckSolOrig(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *feasible, SCIP_Bool printreason, SCIP_Bool completely)
Definition: scip_sol.c:3309
SCIP_VAR ** SCIPgetVarsLogicor(SCIP *scip, SCIP_CONS *cons)
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17420
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:372
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3108
static SCIP_RETCODE checkLogicor(SCIP *scip, SCIP_CONSHDLR *conshdlr, int nconss, SCIP_Bool *satisfied)
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4219
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:250
static SCIP_RETCODE writeExpandedSolutions(SCIP *scip, FILE *file, SCIP_VAR **allvars, int nallvars, SCIP_VAR **activevars, int nactivevars, SCIP_HASHMAP *hashmap, SCIP_SPARSESOL **sols, int nsols)
SCIP_HEUR * SCIPsolGetHeur(SCIP_SOL *sol)
Definition: sol.c:2804
void SCIPsortDownPtrPtr(void **ptrarray1, void **ptrarray2, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
static SCIP_Bool varIsUnfixedLocal(SCIP_VAR *var)
int SCIPheurGetFreq(SCIP_HEUR *heur)
Definition: heur.c:1538
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:269
SCIP_RETCODE SCIPunfixParam(SCIP *scip, const char *name)
Definition: scip_param.c:385
public methods for primal CIP solutions
static void toString(Int value, char **buffer, int buffersize)
#define SCIP_CALL(x)
Definition: def.h:380
SCIP_RETCODE SCIPgetProbvarLinearSum(SCIP *scip, SCIP_VAR **vars, SCIP_Real *scalars, int *nvars, int varssize, SCIP_Real *constant, int *requiredsize, SCIP_Bool mergemultiples)
Definition: scip_var.c:1740
SCIP_VAR * h
Definition: circlepacking.c:68
SCIP_RETCODE SCIPsetEmphasis(SCIP *scip, SCIP_PARAMEMPHASIS paramemphasis, SCIP_Bool quiet)
Definition: scip_param.c:882
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
SCIP_RETCODE SCIPincludeConshdlrCountsols(SCIP *scip)
static SCIP_DECL_CONSLOCK(consLockCountsols)
static SCIP_DECL_CONSCHECK(consCheckCountsols)
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip_branch.c:733
public methods for primal heuristic plugins and divesets
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4638
public methods for constraint handler plugins and constraints
SCIP_Longint SCIPgetCapacityKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR * SCIPgetVbdvarVarbound(SCIP *scip, SCIP_CONS *cons)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:91
SCIP_RETCODE SCIPincludeDisp(SCIP *scip, const char *name, const char *desc, const char *header, SCIP_DISPSTATUS dispstatus, SCIP_DECL_DISPCOPY((*dispcopy)), SCIP_DECL_DISPFREE((*dispfree)), SCIP_DECL_DISPINIT((*dispinit)), SCIP_DECL_DISPEXIT((*dispexit)), SCIP_DECL_DISPINITSOL((*dispinitsol)), SCIP_DECL_DISPEXITSOL((*dispexitsol)), SCIP_DECL_DISPOUTPUT((*dispoutput)), SCIP_DISPDATA *dispdata, int width, int priority, int position, SCIP_Bool stripline)
Definition: scip_disp.c:55
static void setInt(Int *value, SCIP_Longint newvalue)
SCIP_Longint * SCIPsparseSolGetUbs(SCIP_SPARSESOL *sparsesol)
Definition: misc.c:859
SCIP_Longint SCIPgetNCountedFeasSubtrees(SCIP *scip)
SCIP_RETCODE SCIPsparseSolCreate(SCIP_SPARSESOL **sparsesol, SCIP_VAR **vars, int nvars, SCIP_Bool cleared)
Definition: misc.c:763
SCIP_Bool SCIPdialogHasEntry(SCIP_DIALOG *dialog, const char *entryname)
Definition: dialog.c:995
#define DISP_CUTS_NAME
static SCIP_RETCODE includeConshdlrCountsols(SCIP *scip, SCIP_Bool dialogs)
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:487
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:841
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17927
SCIP_Real SCIPgetVbdcoefVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPdialoghdlrGetWord(SCIP_DIALOGHDLR *dialoghdlr, SCIP_DIALOG *dialog, const char *prompt, char **inputword, SCIP_Bool *endoffile)
Definition: dialog.c:546
#define DISP_CUTS_DESC
static SCIP_DECL_SORTPTRCOMP(varCompProbindex)
SCIP_RETCODE SCIPvarGetOrigvarSum(SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: var.c:12775
SCIP_Longint SCIPconvertRealToLongint(SCIP *scip, SCIP_Real real)
SCIP_RETCODE SCIPdialoghdlrAddHistory(SCIP_DIALOGHDLR *dialoghdlr, SCIP_DIALOG *dialog, const char *command, SCIP_Bool escapecommand)
Definition: dialog.c:726
#define DEFAULT_SOLLIMIT
SCIP_RETCODE SCIPcreatePseudoSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:316
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4672
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
#define DEFAULT_DISCARDSOLS
methods for sorting joint arrays of various types
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
int SCIPsparseSolGetNVars(SCIP_SPARSESOL *sparsesol)
Definition: misc.c:839
public methods for branching rule plugins and branching
int SCIPgetNHeurs(SCIP *scip)
Definition: scip_heur.c:282
static void addInt(Int *value, Int *summand)
general public methods
SCIP_DIALOG * SCIPdialoghdlrGetRoot(SCIP_DIALOGHDLR *dialoghdlr)
Definition: dialog.c:436
type definitions for symmetry computations
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
public methods for solutions
static const SCIP_Real scalars[]
Definition: lp.c:5743
SCIP_RETCODE SCIPsetConshdlrInit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINIT((*consinit)))
Definition: scip_cons.c:396
#define DISP_CUTS_HEADER
SCIP_RETCODE SCIPsetConshdlrExit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXIT((*consexit)))
Definition: scip_cons.c:420
static SCIP_DECL_CONSEXITSOL(consExitsolCountsols)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
public methods for message output
SCIP_BOUNDTYPE * SCIPgetBoundtypesBounddisjunction(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition: scip_sol.c:1432
#define DISP_CUTS_WIDTH
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
default user interface dialog
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1216
#define SCIP_Real
Definition: def.h:173
#define DISP_CUTS_POSITION
SCIP_Longint Int
#define SYM_COMPUTETIMING_AFTERPRESOL
Definition: type_symmetry.h:52
static SCIP_DECL_CONSINIT(consInitCountsols)
int SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
public methods for message handling
#define DEFAULT_COLLECT
public methods for dialog handler plugins
#define SCIP_Longint
Definition: def.h:158
static SCIP_RETCODE countSparseSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool feasible, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_RESULT *result)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17585
SCIP_RETCODE SCIPreleaseDialog(SCIP *scip, SCIP_DIALOG **dialog)
Definition: scip_dialog.c:124
SCIP_RETCODE SCIPincludeExternalCodeInformation(SCIP *scip, const char *name, const char *description)
Definition: scip_general.c:728
static SCIP_RETCODE collectSolution(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_SOL *sol)
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:64
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18145
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
Definition: scip_solve.c:3417
public methods for primal heuristics
static SCIP_RETCODE checkVarbound(SCIP *scip, SCIP_CONSHDLR *conshdlr, int nconss, SCIP_Bool *satisfied)
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3281
static void allocInt(Int *value)
void SCIPprintError(SCIP_RETCODE retcode)
Definition: scip_general.c:221
constraint handler for bound disjunction constraints
SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
Definition: scip_cons.c:468
#define SCIPABORT()
Definition: def.h:352
const char * SCIPdispGetName(SCIP_DISP *disp)
Definition: disp.c:335
public methods for global and local (sub)problems
#define CONSHDLR_DESC
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17611
#define DISP_SOLS_PRIORITY
#define DISP_SOLS_NAME
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
static SCIP_RETCODE checkSolution(SCIP *scip, SCIP_SOL *sol, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_RESULT *result)
public methods for user interface dialog
static SCIP_DECL_DISPOUTPUT(dispOutputSols)
SCIP_RETCODE SCIPprintVar(SCIP *scip, SCIP_VAR *var, FILE *file)
Definition: scip_var.c:9998
public methods for display handler plugins
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip_var.c:1529
void SCIPsparseSolFree(SCIP_SPARSESOL **sparsesol)
Definition: misc.c:815
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
#define DEFAULT_ACTIVE
SCIP_RETCODE SCIPsetParamsCountsols(SCIP *scip)
static SCIP_Longint getNCountedSols(Int value, SCIP_Bool *valid)
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:128
#define DEFAULT_SPARSETEST
static SCIP_RETCODE checkFeasSubtree(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *feasible)
memory allocation routines