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( SCIPsolGetHeur(sol) == NULL);
1296 
1297  /* setting result to infeasible since we reject any solution; however, if the solution passes the sparse test or is
1298  * completely fixed, the result is set to SCIP_CUTOFF which cuts off the subtree initialized through the current node
1299  */
1300  *result = SCIP_INFEASIBLE;
1301 
1302 #ifdef SCIP_DEBUG
1303  {
1304  SCIP_VAR* var;
1305  SCIP_VAR** vars;
1306  int v;
1307  int nvars;
1308 
1309  nvars = SCIPgetNVars(scip);
1310  vars = SCIPgetVars(scip);
1311 
1312  for( v = 0; v < nvars; ++v )
1313  {
1314  var = vars[v];
1315  SCIPdebugMsg(scip, "variables <%s> Local Bounds are [%g,%g] Global Bounds are [%g,%g]\n",
1317  }
1318  }
1319 #endif
1320 
1321  /* check if integer variables are completely fixed */
1322  if( SCIPgetNPseudoBranchCands(scip) == 0 )
1323  {
1324  /* check solution original space */
1325  checkSolutionOrig(scip, sol, conshdlrdata);
1326 
1327  addOne(&conshdlrdata->nsols); /*lint !e545*/
1328  conshdlrdata->nNonSparseSols++;
1329 
1330  SCIPdebugMsg(scip, "-> add one to number of solutions\n");
1331 
1332  if( conshdlrdata->collect )
1333  {
1334  SCIP_CALL( collectSolution(scip, conshdlrdata, sol) );
1335  }
1336 
1337  /* in case of continuous variables are present we explicitly cutoff the integer assignment since in case of
1338  * nonlinear constraint we want to avoid to count that integer assignment again
1339  */
1340  if( conshdlrdata->continuous )
1341  {
1342  SCIP_CALL( conshdlrdata->cutoffSolution(scip, sol, conshdlrdata) );
1343  }
1344 
1345  /* since all integer are fixed, we cut off the subtree */
1346  *result = SCIP_CUTOFF;
1347  }
1348  else if( conshdlrdata->sparsetest )
1349  {
1350  SCIP_CALL( checkFeasSubtree(scip, sol, &feasible) ) ;
1351  SCIP_CALL( countSparseSol(scip, sol, feasible, conshdlrdata, result) );
1352  }
1353 
1354  /* transform the current number of solutions into a SCIP_Longint */
1355  nsols = getNCountedSols(conshdlrdata->nsols, &valid);
1356 
1357  /* check if the solution limit is hit and stop SCIP if this is the case */
1358  if( conshdlrdata->sollimit > -1 && (!valid || conshdlrdata->sollimit <= nsols) )
1359  {
1360  SCIP_CALL( SCIPinterruptSolve(scip) );
1361  }
1362 
1363  assert( *result == SCIP_INFEASIBLE || *result == SCIP_CUTOFF );
1364  SCIPdebugMsg(scip, "result is %s\n", *result == SCIP_INFEASIBLE ? "SCIP_INFEASIBLE" : "SCIP_CUTOFF" );
1365 
1366  return SCIP_OKAY;
1367 }
1368 
1369 /*
1370  * Callback methods of constraint handler
1371  */
1372 
1373 /** creates the handler for countsols constraints and includes it in SCIP */
1374 static
1376  SCIP* scip, /**< SCIP data structure */
1377  SCIP_Bool dialogs /**< sould count dialogs be added */
1378  );
1379 
1380 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
1381 static
1382 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyCountsols)
1383 { /*lint --e{715}*/
1384  SCIP_CONSHDLRDATA* conshdlrdata;
1385 
1386  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1387  assert(conshdlrdata != NULL);
1388 
1389  /* in case the countsols constraint handler is active we avoid copying to ensure a safe count */
1390  if( conshdlrdata->active )
1391  *valid = FALSE;
1392  else
1393  {
1394  assert(scip != NULL);
1395  assert(conshdlr != NULL);
1396  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1397 
1398  /* call inclusion method of constraint handler and do not add counting dialogs */
1400 
1401  *valid = TRUE;
1402  }
1403 
1404  return SCIP_OKAY;
1405 }
1406 
1407 #define consCopyCountsols NULL
1409 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
1410 static
1411 SCIP_DECL_CONSFREE(consFreeCountsols)
1412 { /*lint --e{715}*/
1413  SCIP_CONSHDLRDATA* conshdlrdata;
1414 
1415  assert(conshdlr != NULL);
1416  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1417 
1418  /* free constraint handler data */
1419  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1420  assert(conshdlrdata != NULL);
1421 
1422  /* free conshdlrdata */
1423  freeInt(&conshdlrdata->nsols); /*lint !e545*/
1424 
1425  assert( conshdlrdata->solutions == NULL );
1426  assert( conshdlrdata->nsolutions == 0 );
1427  assert( conshdlrdata->ssolutions == 0 );
1428 
1429  SCIPfreeBlockMemory(scip, &conshdlrdata);
1430  SCIPconshdlrSetData(conshdlr, NULL);
1431 
1432  return SCIP_OKAY;
1433 }
1434 
1435 /** initialization method of constraint handler (called after problem was transformed) */
1436 static
1437 SCIP_DECL_CONSINIT(consInitCountsols)
1438 { /*lint --e{715}*/
1439  SCIP_CONSHDLRDATA* conshdlrdata;
1440 
1441  assert( conshdlr != NULL );
1442  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1443 
1444  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1445  assert(conshdlrdata != NULL );
1446 
1447  /* reset counting variables */
1448  conshdlrdata->feasST = 0; /* number of non trivial unrestricted subtrees */
1449  conshdlrdata->nDiscardSols = 0; /* number of discard solutions */
1450  conshdlrdata->nNonSparseSols = 0; /* number of non sparse solutions */
1451  setInt(&conshdlrdata->nsols, 0LL); /* number of solutions */ /*lint !e545*/
1452 
1453  conshdlrdata->solutions = NULL;
1454  conshdlrdata->nsolutions = 0;
1455  conshdlrdata->ssolutions = 0;
1456 
1457  if( conshdlrdata->active )
1458  {
1459  SCIP_VAR** origvars;
1460  int norigvars;
1461  int nallvars;
1462  int v;
1463 
1464  origvars = SCIPgetOrigVars(scip);
1465  norigvars = SCIPgetNOrigVars(scip);
1466 
1467  /* get number of integral variables */
1468  conshdlrdata->nallvars = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
1469 
1470  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conshdlrdata->allvars, conshdlrdata->nallvars) );
1471 
1472  nallvars = 0;
1473 
1474  /* capture and lock all variables */
1475  for( v = 0; v < norigvars; ++v )
1476  {
1477  if( SCIPvarGetType(origvars[v]) != SCIP_VARTYPE_CONTINUOUS )
1478  {
1479  assert(nallvars < conshdlrdata->nallvars);
1480 
1481  SCIP_CALL( SCIPgetTransformedVar(scip, origvars[v], &conshdlrdata->allvars[nallvars]) );
1482  assert(conshdlrdata->allvars[nallvars] != NULL);
1483 
1484  /* capture variable to ensure that the variable will not be deleted */
1485  SCIP_CALL( SCIPcaptureVar(scip, conshdlrdata->allvars[nallvars]) );
1486 
1487  if( strncmp(SCIPvarGetName(conshdlrdata->allvars[nallvars]), "t_andresultant_", strlen("t_andresultant_")) != 0 )
1488  {
1489  /* lock variable to avoid dual reductions */
1490  SCIP_CALL( SCIPaddVarLocksType(scip, conshdlrdata->allvars[nallvars], SCIP_LOCKTYPE_MODEL, 1, 1) );
1491  }
1492 
1493  nallvars++;
1494  }
1495  }
1496  assert(nallvars == conshdlrdata->nallvars);
1497 
1498  /* check if continuous variables are present */
1499  conshdlrdata->continuous = SCIPgetNContVars(scip) > 0;
1500  }
1501 
1502  return SCIP_OKAY;
1503 }
1504 
1505 /** deinitialization method of constraint handler (called before transformed problem is freed) */
1506 static
1507 SCIP_DECL_CONSEXIT(consExitCountsols)
1508 { /*lint --e{715}*/
1509  SCIP_CONSHDLRDATA* conshdlrdata;
1510  int s;
1511  int v;
1512 
1513  assert( conshdlr != NULL );
1514  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1515 
1516  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1517  assert(conshdlrdata != NULL );
1518 
1519  /* release variables to hashmap */
1520  for( v = conshdlrdata->nvars - 1; v >= 0; --v )
1521  {
1522  SCIP_CALL( SCIPreleaseVar(scip, &(conshdlrdata->vars[v])) );
1523  }
1524 
1525  if( conshdlrdata->hashmap != NULL)
1526  {
1527  /* free hashmap of active variables to pistions */
1528  SCIPhashmapFree(&(conshdlrdata->hashmap));
1529  }
1530 
1531  /* free active variables */
1532  SCIPfreeBlockMemoryArrayNull(scip, &(conshdlrdata->vars), conshdlrdata->nvars);
1533  conshdlrdata->nvars = 0;
1534 
1535  if( conshdlrdata->allvars != NULL )
1536  {
1537  /* release and unlock all variables */
1538  for( v = 0; v < conshdlrdata->nallvars; ++v )
1539  {
1540  if( strncmp(SCIPvarGetName(conshdlrdata->allvars[v]), "t_andresultant_", strlen("t_andresultant_")) != 0 )
1541  {
1542  /* remove the previously added variable locks */
1543  SCIP_CALL( SCIPaddVarLocksType(scip, conshdlrdata->allvars[v], SCIP_LOCKTYPE_MODEL, -1, -1) );
1544  }
1545 
1546  SCIP_CALL( SCIPreleaseVar(scip, &conshdlrdata->allvars[v]) );
1547  }
1548 
1549  SCIPfreeBlockMemoryArrayNull(scip, &conshdlrdata->allvars, conshdlrdata->nallvars);
1550  conshdlrdata->nallvars = 0;
1551  }
1552 
1553  if( conshdlrdata->nsolutions > 0 )
1554  {
1555  for( s = conshdlrdata->nsolutions - 1; s >= 0 ; --s )
1556  {
1557  SCIPsparseSolFree(&(conshdlrdata->solutions[s]));
1558  }
1559 
1560  SCIPfreeMemoryArrayNull(scip, &conshdlrdata->solutions);
1561  conshdlrdata->nsolutions = 0;
1562  conshdlrdata->ssolutions = 0;
1563 
1564  assert( conshdlrdata->solutions == NULL );
1565  }
1566  conshdlrdata->continuous = FALSE;
1567 
1568  assert( conshdlrdata->solutions == NULL );
1569  assert( conshdlrdata->nsolutions == 0 );
1570  assert( conshdlrdata->ssolutions == 0 );
1571 
1572  return SCIP_OKAY;
1573 }
1574 
1575 
1576 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin)
1577  *
1578  * This method is called when the presolving was finished and the branch and bound process is about to begin.
1579  * The constraint handler may use this call to initialize its branch and bound specific data.
1580  */
1581 static
1582 SCIP_DECL_CONSINITSOL(consInitsolCountsols)
1583 { /*lint --e{715}*/
1584  SCIP_CONSHDLRDATA* conshdlrdata;
1585 
1586  assert( conshdlr != NULL );
1587  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1588 
1589  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1590  assert(conshdlrdata != NULL );
1591 
1592  if( conshdlrdata->active && SCIPgetNVars(scip) >= 1 )
1593  {
1594  SCIP_VAR** vars;
1595  int v;
1596 
1597  assert(conshdlrdata->nsolutions == 0);
1598  assert(conshdlrdata->solutions == NULL);
1599 
1600  conshdlrdata->nvars = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
1601  vars = SCIPgetVars(scip);
1602 
1603  /* exclude upgrade continuous original variables */
1604  for( v = conshdlrdata->nvars - 1; v >= 0; --v )
1605  {
1606  SCIP_VAR* origvar;
1607  SCIP_Real scalar = 1.0;
1608  SCIP_Real constant = 0.0;
1609 
1610  origvar = vars[v];
1611 
1612  /* get original variable to decide if we will count the domain; continuous variables aren't counted */
1613  SCIP_CALL( SCIPvarGetOrigvarSum(&origvar, &scalar, &constant) );
1614 
1615  if( origvar != NULL && SCIPvarGetType(origvar) != SCIP_VARTYPE_CONTINUOUS )
1616  break;
1617  }
1618  conshdlrdata->nvars = v + 1;
1619 
1620  /* @todo we need to forbid variable downgrading, from integer type to implicit integer type, e.g. done in
1621  * cons_linear
1622  */
1623 #ifndef NDEBUG
1624  for( v = conshdlrdata->nvars - 1; v >= 0; --v )
1625  {
1626  SCIP_VAR* origvar;
1627  SCIP_Real scalar = 1.0;
1628  SCIP_Real constant = 0.0;
1629 
1630  origvar = vars[v];
1631 
1632  /* get original variable to decide if we will count the domain; continuous variables aren't counted */
1633  SCIP_CALL( SCIPvarGetOrigvarSum(&origvar, &scalar, &constant) );
1634 
1635  assert(origvar != NULL && SCIPvarGetType(origvar) != SCIP_VARTYPE_CONTINUOUS);
1636  }
1637 #endif
1638 
1639  /* copy array of active variables */
1640  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(conshdlrdata->vars), vars, conshdlrdata->nvars) );
1641 
1642  /* store mapping from all active variables to their position afetr presolving because during solving new variables
1643  * might be added and therefore could destroy writing collected solutions
1644  */
1645  SCIP_CALL( SCIPhashmapCreate(&(conshdlrdata->hashmap), SCIPblkmem(scip), conshdlrdata->nvars + 1) );
1646 
1647  /* add variables to hashmap */
1648  for( v = conshdlrdata->nvars - 1; v >= 0; --v )
1649  {
1650  assert(SCIPvarGetProbindex(conshdlrdata->vars[v]) == v);
1651  SCIP_CALL( SCIPhashmapInsertInt(conshdlrdata->hashmap, conshdlrdata->vars[v], v+1) );
1652  SCIP_CALL( SCIPcaptureVar(scip, conshdlrdata->vars[v]) );
1653  }
1654 
1655  /* check if the problem is binary (ignoring continuous variables) */
1656  if( SCIPgetNBinVars(scip) == (SCIPgetNVars(scip) - SCIPgetNContVars(scip)) )
1657  conshdlrdata->cutoffSolution = addBinaryCons;
1658  else
1659  conshdlrdata->cutoffSolution = addIntegerCons;
1660  }
1661 
1662  return SCIP_OKAY;
1663 }
1664 
1665 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
1666 static
1667 SCIP_DECL_CONSEXITSOL(consExitsolCountsols)
1668 { /*lint --e{715}*/
1669  SCIP_CONSHDLRDATA* conshdlrdata;
1670 
1671  assert(scip != NULL);
1672  assert(conshdlr != NULL);
1673  assert(nconss == 0);
1674  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1675 
1676  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1677  assert(conshdlrdata != NULL );
1678 
1679  if( conshdlrdata->active && restart )
1680  {
1681  SCIPerrorMessage("When collecting and counting solutions restarts need to be disabled (presolving/maxrestarts = 0).\n");
1682  SCIPABORT();
1683  return SCIP_INVALIDCALL; /*lint !e527*/
1684  }
1685 
1686  return SCIP_OKAY;
1687 }
1688 
1689 /** constraint enforcing method of constraint handler for LP solutions */
1690 static
1691 SCIP_DECL_CONSENFOLP(consEnfolpCountsols)
1692 { /*lint --e{715}*/
1693  SCIP_CONSHDLRDATA* conshdlrdata;
1694 
1695  SCIPdebugMsg(scip, "method SCIP_DECL_CONSENFOLP(consEnfolpCountsols)\n");
1696 
1697  assert( scip != NULL );
1698  assert( conshdlr != NULL );
1699  assert( nconss == 0 );
1700 
1701  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1702  assert( conshdlrdata != NULL );
1703 
1704  if( conshdlrdata->active )
1705  {
1706  if( !solinfeasible )
1707  {
1708  SCIP_SOL* sol;
1709 
1710  SCIP_CALL( SCIPcreateLPSol(scip, &sol, NULL ) );
1711 
1712  SCIP_CALL( checkSolution(scip, sol, conshdlrdata, result) );
1713  SCIP_CALL( SCIPfreeSol(scip, &sol) );
1714  }
1715  else
1716  *result = SCIP_INFEASIBLE;
1717  }
1718  else
1719  *result = SCIP_FEASIBLE;
1720 
1721  assert( !conshdlrdata->active || *result == SCIP_INFEASIBLE || *result == SCIP_CUTOFF );
1722 
1723  return SCIP_OKAY;
1724 }
1725 
1726 /** constraint enforcing method of constraint handler for relaxation solutions */
1727 static
1728 SCIP_DECL_CONSENFORELAX(consEnforelaxCountsols)
1729 { /*lint --e{715}*/
1730  SCIP_CONSHDLRDATA* conshdlrdata;
1731 
1732  SCIPdebugMsg(scip, "method SCIP_DECL_CONSENFORELAX(consEnfolpCountsols)\n");
1733 
1734  assert( scip != NULL );
1735  assert( conshdlr != NULL );
1736  assert( nconss == 0 );
1737 
1738  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1739  assert( conshdlrdata != NULL );
1740 
1741  if( conshdlrdata->active )
1742  {
1743  if( !solinfeasible )
1744  {
1745  SCIP_CALL( checkSolution(scip, sol, conshdlrdata, result) );
1746  }
1747  else
1748  *result = SCIP_INFEASIBLE;
1749  }
1750  else
1751  *result = SCIP_FEASIBLE;
1752 
1753  assert( !conshdlrdata->active || *result == SCIP_INFEASIBLE || *result == SCIP_CUTOFF );
1754 
1755  return SCIP_OKAY;
1756 }
1757 
1758 /** constraint enforcing method of constraint handler for pseudo solutions */
1759 static
1760 SCIP_DECL_CONSENFOPS(consEnfopsCountsols)
1761 { /*lint --e{715}*/
1762  SCIP_CONSHDLRDATA* conshdlrdata;
1763 
1764  SCIPdebugMsg(scip, "method SCIP_DECL_CONSENFOPS(consEnfopsCountsols)\n");
1765 
1766  assert( scip != NULL );
1767  assert( conshdlr != NULL );
1768  assert( nconss == 0 );
1769 
1770  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1771  assert( conshdlrdata != NULL );
1772 
1773  if( conshdlrdata->active )
1774  {
1775  if( !solinfeasible )
1776  {
1777  SCIP_SOL* sol;
1778 
1779  SCIP_CALL( SCIPcreatePseudoSol(scip, &sol, NULL ) );
1780 
1781  SCIP_CALL( checkSolution(scip, sol, conshdlrdata, result) );
1782  SCIP_CALL( SCIPfreeSol(scip, &sol) );
1783  }
1784  else
1785  *result = SCIP_INFEASIBLE;
1786  }
1787  else
1788  *result = SCIP_FEASIBLE;
1789 
1790  assert( !conshdlrdata->active || *result == SCIP_INFEASIBLE || *result == SCIP_CUTOFF );
1791 
1792  return SCIP_OKAY;
1793 }
1794 
1795 
1796 /** feasibility check method of constraint handler for integral solutions */
1797 static
1798 SCIP_DECL_CONSCHECK(consCheckCountsols)
1799 { /*lint --e{715}*/
1800  /**@todo non-trivial solutions which are only checked have to be ignored since it is unknown how they are generated;
1801  * calculating heuristic solutions should be avoided */
1802  SCIP_CONSHDLRDATA* conshdlrdata;
1803 
1804  SCIPdebugMsg(scip, "method SCIP_DECL_CONSCHECK(consCheckCountsols)\n");
1805 
1806  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1807  assert( conshdlrdata != NULL );
1808 
1809  if( conshdlrdata->active )
1810  {
1811  /* count empty solution */
1812  if( SCIPgetNVars(scip) == 0 )
1813  SCIP_CALL( checkSolution(scip, sol, conshdlrdata, result) );
1814  else if( !conshdlrdata->warning )
1815  {
1816  SCIPwarningMessage(scip, "a non-trivial solution comes in over <SCIP_DECL_CONSCHECK(consCheckCountsols)>; currently these solutions are ignored.\n");
1817  conshdlrdata->warning = TRUE;
1818  }
1819 
1820  *result = SCIP_INFEASIBLE;
1821  }
1822  else
1823  *result = SCIP_FEASIBLE;
1824 
1825  return SCIP_OKAY;
1826 }
1827 
1828 
1829 /** variable rounding lock method of constraint handler */
1830 static
1831 SCIP_DECL_CONSLOCK(consLockCountsols)
1832 { /*lint --e{715}*/
1833  return SCIP_OKAY;
1834 }
1835 
1836 
1837 /*
1838  * Callback methods and local method for dialogs
1839  */
1840 
1841 /** dialog execution method for the count command */
1842 SCIP_DECL_DIALOGEXEC(SCIPdialogExecCountPresolve)
1843 { /*lint --e{715}*/
1844  SCIP_Bool active;
1845  int usesymmetry;
1846 
1847  SCIP_CALL( SCIPgetIntParam(scip, "misc/usesymmetry", &usesymmetry) );
1848 
1849  if ( usesymmetry != 0 )
1850  {
1851  int symcomptiming = 2;
1852 
1853  /* get timing of symmetry computation */
1854  if ( ((unsigned) usesymmetry & SYM_HANDLETYPE_SYMCONS) != 0 )
1855  {
1856  SCIP_CALL( SCIPgetIntParam(scip, "propagating/symmetry/addconsstiming", &symcomptiming) );
1857  }
1858  else if ( usesymmetry == 2 )
1859  {
1860  SCIP_CALL( SCIPgetIntParam(scip, "propagating/symmetry/ofsymcomptiming", &symcomptiming) );
1861  }
1862 
1863  if ( symcomptiming < SYM_TIMING_AFTERPRESOL &&
1865  {
1866  SCIPerrorMessage("Symmetry handling and solution counting are not compatible. " \
1867  "You might want to disable symmetry by setting parameter <misc/usesymmetry> to 0.\n");
1868 
1869  return SCIP_INVALIDCALL;
1870  }
1871 
1872  SCIPwarningMessage(scip, "Symmetry handling has been deactivated since it is not compatible with counting.\n");
1873  SCIPwarningMessage(scip, "=> counting forces parameter <misc/usesymmetry> to 0.\n");
1874 
1875  SCIP_CALL( SCIPsetIntParam(scip, "misc/usesymmetry", 0) );
1876  }
1877 
1878  SCIP_CALL( SCIPdialoghdlrAddHistory(dialoghdlr, dialog, NULL, FALSE) );
1879  SCIPdialogMessage(scip, NULL, "\n");
1880  SCIP_CALL( SCIPgetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", &active) );
1881 
1882  switch( SCIPgetStage(scip) )
1883  {
1884  case SCIP_STAGE_INIT:
1885  SCIPdialogMessage(scip, NULL, "no problem exists\n");
1886  break;
1887 
1888  case SCIP_STAGE_PROBLEM:
1889  /* activate constraint handler cons_countsols */
1890  if( !active )
1891  {
1892  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", TRUE) );
1893  }
1894  /*lint -fallthrough*/
1896  case SCIP_STAGE_PRESOLVING:
1897  /* presolve problem */
1898  SCIP_CALL( SCIPpresolve(scip) );
1899 
1900  /* reset cons_countsols activation */
1901  if( !active )
1902  {
1903  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", FALSE) );
1904  }
1905  break;
1906 
1907  case SCIP_STAGE_PRESOLVED:
1908  case SCIP_STAGE_SOLVING:
1909  SCIPdialogMessage(scip, NULL, "problem is already presolved\n");
1910  break;
1911 
1912  case SCIP_STAGE_SOLVED:
1913  SCIPdialogMessage(scip, NULL, "problem is already (pre)solved\n");
1914  break;
1915 
1919  case SCIP_STAGE_INITSOLVE:
1920  case SCIP_STAGE_EXITSOLVE:
1921  case SCIP_STAGE_FREETRANS:
1922  case SCIP_STAGE_FREE:
1923  default:
1924  SCIPerrorMessage("invalid SCIP stage\n");
1925  return SCIP_INVALIDCALL;
1926  } /*lint --e{616}*/
1927 
1928  SCIPdialogMessage(scip, NULL, "\n");
1929  *nextdialog = SCIPdialoghdlrGetRoot(dialoghdlr);
1930 
1931  return SCIP_OKAY;
1932 }
1933 
1934 /** dialog execution method for the count command */
1935 SCIP_DECL_DIALOGEXEC(SCIPdialogExecCount)
1936 { /*lint --e{715}*/
1937  SCIP_RETCODE retcode;
1938  SCIP_Bool active;
1939 
1940  SCIP_Bool valid;
1941  SCIP_Longint nsols;
1942  int displayprimalbound;
1943  int displaygap;
1944  int displaysols;
1945  int displayfeasST;
1946  int nrestarts;
1947  int usesymmetry;
1948 
1949  SCIP_CALL( SCIPdialoghdlrAddHistory(dialoghdlr, dialog, NULL, FALSE) );
1950  SCIPdialogMessage(scip, NULL, "\n");
1951  SCIP_CALL( SCIPgetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", &active) );
1952  SCIP_CALL( SCIPgetIntParam(scip, "presolving/maxrestarts", &nrestarts) );
1953 
1954  if( nrestarts != 0 )
1955  {
1956  /* need to disable restarts, since collecting solutions won't work, but also the capturing for variables is not
1957  * correctly handled
1958  */
1959  SCIPwarningMessage(scip, "counting forces parameter <presolving/maxrestarts> to 0.\n");
1960  if( SCIPisParamFixed(scip, "presolving/maxrestarts") )
1961  {
1962  SCIP_CALL( SCIPunfixParam(scip, "presolving/maxrestarts") );
1963  }
1964  SCIP_CALL( SCIPsetIntParam(scip, "presolving/maxrestarts", 0) );
1965  }
1966 
1967  SCIP_CALL( SCIPgetIntParam(scip, "misc/usesymmetry", &usesymmetry) );
1968 
1969  if ( usesymmetry != 0 )
1970  {
1971  int symcomptiming = 2;
1972 
1973  /* get timing of symmetry computation */
1974  if ( ((unsigned) usesymmetry & SYM_HANDLETYPE_SYMCONS) != 0 )
1975  {
1976  SCIP_CALL( SCIPgetIntParam(scip, "propagating/symmetry/addconsstiming", &symcomptiming) );
1977  }
1978  else if ( usesymmetry == 2 )
1979  {
1980  SCIP_CALL( SCIPgetIntParam(scip, "propagating/symmetry/ofsymcomptiming", &symcomptiming) );
1981  }
1982 
1983  if ( symcomptiming < SYM_TIMING_AFTERPRESOL &&
1985  {
1986  SCIPerrorMessage("Symmetry handling and solution counting are not compatible. " \
1987  "You might want to disable symmetry by setting parameter <misc/usesymmetry> to 0.\n");
1988 
1989  return SCIP_INVALIDCALL;
1990  }
1991 
1992  SCIPwarningMessage(scip, "Symmetry handling has been deactivated since it is not compatible with counting.\n");
1993  SCIPwarningMessage(scip, "=> counting forces parameter <misc/usesymmetry> to 0.\n");
1994 
1995  SCIP_CALL( SCIPsetIntParam(scip, "misc/usesymmetry", 0) );
1996  }
1997 
1998  switch( SCIPgetStage(scip) )
1999  {
2000  case SCIP_STAGE_INIT:
2001  SCIPdialogMessage(scip, NULL, "no problem exists\n");
2002  break;
2003 
2004  case SCIP_STAGE_PROBLEM:
2005  /* activate constraint handler cons_countsols */
2006  if( !active )
2007  {
2008  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", TRUE) );
2009  }
2010  /*lint -fallthrough*/
2012  case SCIP_STAGE_PRESOLVING:
2013  /* presolve problem */
2014  SCIP_CALL( SCIPpresolve(scip) );
2015  /*lint -fallthrough*/
2016  case SCIP_STAGE_PRESOLVED:
2017  /* reset activity status of constraint handler cons_countsols */
2018  if( !active )
2019  {
2020  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", FALSE) );
2021  }
2022  /*lint -fallthrough*/
2023  case SCIP_STAGE_SOLVING:
2024  /* check if the problem contains continuous variables */
2025  if( SCIPgetNContVars(scip) != 0 )
2026  {
2028  "Problem contains continuous variables (after presolving). Counting projection to integral variables!\n");
2029  }
2030 
2031  /* turn off primal bound and gap column */
2032  SCIP_CALL( SCIPgetIntParam(scip, "display/primalbound/active", &displayprimalbound) );
2033  if( displayprimalbound != 0 )
2034  {
2035  SCIP_CALL( SCIPsetIntParam(scip, "display/primalbound/active", 0) );
2036  }
2037  SCIP_CALL( SCIPgetIntParam(scip, "display/gap/active", &displaygap) );
2038  if( displaygap != 0 )
2039  {
2040  SCIP_CALL( SCIPsetIntParam(scip, "display/gap/active", 0) );
2041  }
2042 
2043  /* turn on sols and feasST column */
2044  SCIP_CALL( SCIPgetIntParam(scip, "display/sols/active", &displaysols) );
2045  if( displayprimalbound != 2 )
2046  {
2047  SCIP_CALL( SCIPsetIntParam(scip, "display/sols/active", 2) );
2048  }
2049  SCIP_CALL( SCIPgetIntParam(scip, "display/feasST/active", &displayfeasST) );
2050  if( displayprimalbound != 2 )
2051  {
2052  SCIP_CALL( SCIPsetIntParam(scip, "display/feasST/active", 2) );
2053  }
2054 
2055  /* find the countsols constraint handler */
2056  assert( SCIPfindConshdlr(scip, CONSHDLR_NAME) != NULL );
2057 
2058  retcode = SCIPcount(scip);
2059 
2060  valid = FALSE;
2061  nsols = SCIPgetNCountedSols(scip, &valid);
2062 
2063  if( valid )
2064  SCIPdialogMessage(scip, NULL, "Feasible Solutions : %" SCIP_LONGINT_FORMAT "", nsols);
2065  else
2066  {
2067  char* buffer;
2068  int buffersize = SCIP_MAXSTRLEN;
2069  int requiredsize;
2070 
2071  SCIP_CALL( SCIPallocBufferArray(scip, &buffer, buffersize) );
2072  SCIPgetNCountedSolsstr(scip, &buffer, buffersize, &requiredsize);
2073 
2074  if( requiredsize > buffersize )
2075  {
2076  SCIP_CALL( SCIPreallocBufferArray(scip, &buffer, requiredsize) );
2077  SCIPgetNCountedSolsstr(scip, &buffer, buffersize, &requiredsize);
2078  }
2079 
2080  assert( buffersize >= requiredsize );
2081  SCIPdialogMessage(scip, NULL, "Feasible Solutions : %s", buffer);
2082 
2083  SCIPfreeBufferArray(scip, &buffer);
2084  }
2085 
2086  SCIPdialogMessage(scip, NULL, " (%" SCIP_LONGINT_FORMAT " non-trivial feasible subtrees)\n", SCIPgetNCountedFeasSubtrees(scip));
2087 
2088  *nextdialog = SCIPdialoghdlrGetRoot(dialoghdlr);
2089 
2090  /* reset display columns */
2091  if( displayprimalbound != 0 )
2092  {
2093  SCIP_CALL( SCIPsetIntParam(scip, "display/primalbound/active", displayprimalbound) );
2094  }
2095  if( displaygap != 0 )
2096  {
2097  SCIP_CALL( SCIPsetIntParam(scip, "display/gap/active", displaygap) );
2098  }
2099 
2100  /* reset sols and feasST column */
2101  if( displaysols != 2 )
2102  {
2103  SCIP_CALL( SCIPsetIntParam(scip, "display/sols/active", displaysols) );
2104  }
2105  if( displayfeasST != 2 )
2106  {
2107  SCIP_CALL( SCIPsetIntParam(scip, "display/feasST/active", displayfeasST) );
2108  }
2109 
2110  /* reset cons_countsols activation */
2111  if( !active )
2112  {
2113  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", FALSE) );
2114  }
2115 
2116  /* evaluate retcode */
2117  SCIP_CALL( retcode );
2118  break;
2119 
2120  case SCIP_STAGE_SOLVED:
2121  SCIPdialogMessage(scip, NULL, "problem is already solved\n");
2122  break;
2123 
2127  case SCIP_STAGE_INITSOLVE:
2128  case SCIP_STAGE_EXITSOLVE:
2129  case SCIP_STAGE_FREETRANS:
2130  case SCIP_STAGE_FREE:
2131  default:
2132  SCIPerrorMessage("invalid SCIP stage\n");
2133  return SCIP_INVALIDCALL;
2134  } /*lint --e{616}*/
2135 
2136  SCIPdialogMessage(scip, NULL, "\n");
2137  *nextdialog = SCIPdialoghdlrGetRoot(dialoghdlr);
2138 
2139  return SCIP_OKAY;
2140 }
2141 
2142 /** comparison method for sorting variables by non-decreasing w.r.t. problem index */
2143 static
2144 SCIP_DECL_SORTPTRCOMP(varCompProbindex)
2146  SCIP_VAR* var1;
2147  SCIP_VAR* var2;
2148 
2149  var1 = (SCIP_VAR*)elem1;
2150  var2 = (SCIP_VAR*)elem2;
2151 
2152  assert(var1 != NULL);
2153  assert(var2 != NULL);
2154 
2155  if( SCIPvarGetProbindex(var1) < SCIPvarGetProbindex(var2) )
2156  return -1;
2157  else if( SCIPvarGetProbindex(var1) > SCIPvarGetProbindex(var2) )
2158  return +1;
2159  else
2160  {
2161  assert(var1 == var2 || (SCIPvarGetProbindex(var1) == -1 && SCIPvarGetProbindex(var2) == -1));
2162  return 0;
2163  }
2164 }
2165 
2166 /** expands the sparse solutions and writes them to the file */
2167 static
2169  SCIP* scip, /**< SCIP data structure */
2170  FILE* file, /**< file handler */
2171  SCIP_VAR** allvars, /**< SCIP variables */
2172  int nallvars, /**< number of all variables */
2173  SCIP_VAR** activevars, /**< SCIP variables */
2174  int nactivevars, /**< number of active variables */
2175  SCIP_HASHMAP* hashmap, /**< hashmap from active solution variable to the position in the active
2176  * variables array
2177  */
2178  SCIP_SPARSESOL** sols, /**< sparse solutions to expands and write */
2179  int nsols /**< number of sparse solutions */
2180  )
2181 {
2182  SCIP_SPARSESOL* sparsesol;
2183  SCIP_VAR** vars;
2184  SCIP_Real* scalars;
2185  SCIP_Longint* sol;
2186  SCIP_Longint solcnt;
2187  int s;
2188  int v;
2189 
2190  assert(scip != NULL);
2191  assert(file != NULL);
2192  assert(hashmap != NULL);
2193  assert(allvars != NULL || nallvars == 0);
2194  assert(activevars != NULL || nactivevars == 0);
2195  assert(sols != NULL || nsols == 0);
2196 
2197  solcnt = 0;
2198 
2199  /* get memory to store active solution */
2200  SCIP_CALL( SCIPallocBufferArray(scip, &sol, nactivevars) );
2201  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nactivevars) );
2202  SCIP_CALL( SCIPallocBufferArray(scip, &scalars, nactivevars) );
2203 
2204  /* loop over all sparse solutions */
2205  for( s = 0; s < nsols; ++s )
2206  {
2207  sparsesol = sols[s]; /*lint !e613*/
2208  assert(sparsesol != NULL);
2209  assert(SCIPsparseSolGetNVars(sparsesol) == nactivevars);
2210 
2211  /* get first solution of the sparse solution */
2212  SCIPsparseSolGetFirstSol(sparsesol, sol, nactivevars);
2213 
2214  do
2215  {
2216  SCIP_Real objval;
2217 
2218  solcnt++;
2219 
2220  /* print solution number */
2221  SCIPinfoMessage(scip, file, "%d(%" SCIP_LONGINT_FORMAT "), ", s+1, solcnt);
2222 
2223  objval = 0.0;
2224 
2225  /* write none active variables */
2226  for( v = 0; v < nallvars; ++v )
2227  {
2228  SCIP_Real constant;
2229  SCIP_Real realvalue;
2230  int requiredsize;
2231  int nvars;
2232  int idx;
2233  int i;
2234 
2235  vars[0] = allvars[v]; /*lint !e613*/
2236  scalars[0] = 1.0;
2237  nvars = 1;
2238  constant = 0.0;
2239 
2240  SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, scalars, &nvars, nallvars, &constant, &requiredsize, TRUE) );
2241  assert(requiredsize <= nallvars);
2242  assert(nvars <= nactivevars);
2243 
2244  realvalue = constant;
2245 
2246  for( i = 0; i < nvars; ++i )
2247  {
2248  assert(SCIPhashmapExists(hashmap, vars[i]));
2249  idx = SCIPhashmapGetImageInt(hashmap, vars[i]) - 1;
2250  assert(0 <= idx && idx < nactivevars);
2251  assert(activevars[idx] == vars[i]); /*lint !e613*/
2252 
2253  objval += SCIPvarGetObj(vars[i]) * sol[idx];
2254  realvalue += scalars[i] * sol[idx];
2255  }
2256  assert(SCIPisIntegral(scip, realvalue));
2257 
2258  SCIPinfoMessage(scip, file, "%g, ", realvalue);
2259  }
2260 
2261  /* transform objective value into original problem space */
2262  objval = SCIPretransformObj(scip, objval);
2263 
2264  /* output the objective value of the solution */
2265  SCIPinfoMessage(scip, file, "%g\n", objval);
2266  }
2267  while( SCIPsparseSolGetNextSol(sparsesol, sol, nactivevars) );
2268  }
2269 
2270  /* free buffer arrays */
2271  SCIPfreeBufferArray(scip, &scalars);
2272  SCIPfreeBufferArray(scip, &vars);
2273  SCIPfreeBufferArray(scip, &sol);
2274 
2275  return SCIP_OKAY;
2276 }
2277 
2278 /** execution method of dialog for writing all solutions */
2279 SCIP_DECL_DIALOGEXEC(SCIPdialogExecWriteAllsolutions)
2280 { /*lint --e{715}*/
2281  FILE* file;
2282  SCIP_Longint nsols;
2283  char* filename;
2284  char* word;
2285  SCIP_Bool endoffile;
2286  SCIP_Bool valid;
2287 
2288  assert( scip != NULL );
2289 
2290  SCIP_CALL( SCIPdialoghdlrAddHistory(dialoghdlr, dialog, NULL, FALSE) );
2291 
2292  switch( SCIPgetStage(scip) )
2293  {
2294  case SCIP_STAGE_INIT:
2295  SCIPdialogMessage(scip, NULL, "no problem available\n");
2296  break;
2297  case SCIP_STAGE_PROBLEM:
2299  case SCIP_STAGE_FREETRANS:
2300  SCIPdialogMessage(scip, NULL, "the counting process was not started yet\n");
2301  break;
2304  case SCIP_STAGE_PRESOLVING:
2306  case SCIP_STAGE_PRESOLVED:
2307  case SCIP_STAGE_INITSOLVE:
2308  case SCIP_STAGE_SOLVING:
2309  case SCIP_STAGE_SOLVED:
2310  case SCIP_STAGE_EXITSOLVE:
2311  {
2312  SCIP_CONSHDLR* conshdlr;
2313  SCIP_CONSHDLRDATA* conshdlrdata;
2314  int nsparsesols;
2315 
2316  valid = FALSE;
2317  nsols = SCIPgetNCountedSols(scip, &valid);
2318 
2319  /* find the countsols constraint handler */
2320  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2321  assert( conshdlr != NULL );
2322 
2323  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2324  assert( conshdlrdata != NULL );
2325 
2326  nsparsesols = conshdlrdata->nsolutions;
2327 
2328  if( !valid )
2329  {
2330  /* too many solutions, output not "possible" */
2331  char* buffer;
2332  int buffersize;
2333  int requiredsize;
2334 
2335  buffersize = SCIP_MAXSTRLEN;
2336 
2337  SCIP_CALL( SCIPallocBufferArray(scip, &buffer, buffersize) );
2338  SCIPgetNCountedSolsstr(scip, &buffer, buffersize, &requiredsize);
2339 
2340  if( requiredsize > buffersize )
2341  {
2342  buffersize = requiredsize;
2343  SCIP_CALL( SCIPreallocBufferArray(scip, &buffer, requiredsize) );
2344  SCIPgetNCountedSolsstr(scip, &buffer, buffersize, &requiredsize);
2345  }
2346 
2347  assert( buffersize >= requiredsize );
2348  SCIPdialogMessage(scip, NULL, "no output, because of too many feasible solutions : %s\n", buffer);
2349 
2350  SCIPfreeBufferArray(scip, &buffer);
2351  }
2352  else if( nsols == 0 )
2353  {
2354  SCIPdialogMessage(scip, NULL, "there are no counted solutions\n");
2355  }
2356  else if( nsparsesols == 0 )
2357  {
2358  SCIPdialogMessage(scip, NULL, "there is no solution collect (set parameter <constraints/countsols/collect> to TRUE)\n");
2359  }
2360  else
2361  {
2362  SCIP_CALL( SCIPdialoghdlrGetWord(dialoghdlr, dialog, "enter filename: ", &word, &endoffile) );
2363 
2364  /* copy the filename for later use */
2365  SCIP_CALL( SCIPduplicateBufferArray(scip, &filename, word, (int)strlen(word)+1) );
2366 
2367  if( endoffile )
2368  {
2369  *nextdialog = NULL;
2370  return SCIP_OKAY;
2371  }
2372 
2373  SCIP_CALL( SCIPdialoghdlrAddHistory(dialoghdlr, dialog, filename, TRUE) );
2374 
2375  if( filename[0] != '\0' )
2376  {
2377  file = fopen(filename, "w");
2378 
2379  if( file == NULL )
2380  {
2381  SCIPdialogMessage(scip, NULL, "error creating file <%s>\n", filename);
2382  SCIPdialoghdlrClearBuffer(dialoghdlr);
2383  }
2384  else
2385  {
2386  SCIP_SPARSESOL** sparsesols;
2387  SCIP_VAR** origvars;
2388  SCIP_VAR** allvars;
2389  int norigvars;
2390  int nvars;
2391  int v;
2392 
2393  SCIP_RETCODE retcode;
2394 
2395  /* get sparse solutions defined over the active variables */
2396  nvars = conshdlrdata->nvars;
2397  sparsesols = conshdlrdata->solutions;
2398 
2399  /* get original problem variables */
2400  retcode = SCIPallocBufferArray(scip, &origvars, SCIPgetNOrigVars(scip));
2401  if( retcode != SCIP_OKAY )
2402  {
2403  fclose(file);
2404  SCIP_CALL( retcode );
2405  }
2406 
2407  norigvars = 0;
2408 
2409  for( v = 0; v < SCIPgetNOrigVars(scip); ++v )
2410  {
2412  {
2413  origvars[norigvars] = SCIPgetOrigVars(scip)[v];
2414  norigvars++;
2415  }
2416  }
2417  assert(norigvars == conshdlrdata->nallvars);
2418 
2419  retcode = SCIPduplicateBufferArray(scip, &allvars, conshdlrdata->allvars, norigvars);
2420  if( retcode != SCIP_OKAY )
2421  {
2422  fclose(file); /*lint !e449*/
2423  SCIP_CALL( retcode );
2424  }
2425 
2426  /* sort original variables array and the corresponding transformed variables w.r.t. the problem index */
2427  SCIPsortDownPtrPtr((void**)allvars, (void**)origvars, varCompProbindex, norigvars);
2428 
2429  SCIPdialogMessage(scip, NULL, "saving %" SCIP_LONGINT_FORMAT " (%d) feasible solutions\n", nsols, nsparsesols);
2430 
2431  /* first row: output the names of the variables in the given ordering */
2432  SCIPinfoMessage(scip, file, "#, ");
2433 
2434  for( v = 0; v < norigvars; ++v )
2435  {
2436 #ifndef NDEBUG
2437  {
2438  /* check if the original variable fits to the transformed variable the constraint handler has stored */
2439  SCIP_VAR* transvar;
2440  SCIP_CALL( SCIPgetTransformedVar(scip, origvars[v], &transvar) );
2441  assert(transvar != NULL);
2442  assert(transvar == allvars[v]);
2443  }
2444 #endif
2445  SCIPinfoMessage(scip, file, "%s, ", SCIPvarGetName(origvars[v]));
2446  }
2447 
2448  SCIPinfoMessage(scip, file, "objval\n");
2449 
2450  /* expand and write solution */
2451  retcode = writeExpandedSolutions(scip, file, allvars, conshdlrdata->nallvars, conshdlrdata->vars, nvars, conshdlrdata->hashmap, sparsesols, nsparsesols);
2452  if( retcode != SCIP_OKAY )
2453  {
2454  fclose(file);
2455  SCIP_CALL( retcode );
2456  }
2457  SCIPdialogMessage(scip, NULL, "written solutions information to file <%s>\n", filename);
2458 
2459  SCIPfreeBufferArray(scip, &allvars);
2460  SCIPfreeBufferArray(scip, &origvars);
2461 
2462  fclose(file);
2463  }
2464 
2465  /* free buffer array */
2466  SCIPfreeBufferArray(scip, &filename);
2467  }
2468  }
2469  break;
2470  }
2471  case SCIP_STAGE_FREE:
2472  SCIPerrorMessage("invalid call during SCIP_STAGE_FREE\n");
2473  return SCIP_ERROR;
2474  }
2475 
2476  *nextdialog = SCIPdialoghdlrGetRoot(dialoghdlr);
2477 
2478  return SCIP_OKAY;
2479 }
2480 
2481 /** create the interactive shell dialogs for the counting process */
2482 static
2484  SCIP* scip /**< SCIP data structure */
2485  )
2486 {
2487  SCIP_DIALOG* root;
2488  SCIP_DIALOG* dialog;
2489  SCIP_DIALOG* submenu;
2490 
2491  root = SCIPgetRootDialog(scip);
2492 
2493  /* skip dialogs if they seem to be disabled */
2494  if( root == NULL )
2495  return SCIP_OKAY;
2496 
2497  /* add dialog entry for counting */
2498  if( !SCIPdialogHasEntry(root, "count") )
2499  {
2500  SCIP_CALL( SCIPincludeDialog(scip, &dialog, NULL, SCIPdialogExecCount, NULL, NULL,
2501  "count", "count number of feasible solutions", FALSE, NULL) );
2502  SCIP_CALL( SCIPaddDialogEntry(scip, root, dialog) );
2503  SCIP_CALL( SCIPreleaseDialog(scip, &dialog) );
2504  }
2505 
2506  /* add dialog entry for counting */
2507  if( !SCIPdialogHasEntry(root, "countpresolve") )
2508  {
2509  SCIP_CALL( SCIPincludeDialog(scip, &dialog, NULL, SCIPdialogExecCountPresolve, NULL, NULL,
2510  "countpresolve", "presolve instance before counting number of feasible solutions", FALSE, NULL) );
2511  SCIP_CALL( SCIPaddDialogEntry(scip, root, dialog) );
2512  SCIP_CALL( SCIPreleaseDialog(scip, &dialog) );
2513  }
2514 
2515  /* search for the "write" sub menu to add "allsolutions" dialog */
2516  if( SCIPdialogFindEntry(root, "write", &submenu) != 1 )
2517  {
2518  SCIPerrorMessage("write sub menu not found\n");
2519  return SCIP_PLUGINNOTFOUND;
2520  }
2521  assert(submenu != NULL);
2522 
2523  /* add dialog "allsolutions" to sub menu "write" */
2524  if( !SCIPdialogHasEntry(submenu, "allsolutions") )
2525  {
2526  SCIP_CALL( SCIPincludeDialog(scip, &dialog, NULL, SCIPdialogExecWriteAllsolutions, NULL, NULL,
2527  "allsolutions", "write all counted primal solutions to file", FALSE, NULL) );
2528  SCIP_CALL( SCIPaddDialogEntry(scip, submenu, dialog) );
2529  SCIP_CALL( SCIPreleaseDialog(scip, &dialog) );
2530  }
2531 
2532  return SCIP_OKAY;
2533 }
2534 
2535 /*
2536  * Callback methods for columns
2537  */
2538 
2539 /** output method of display column to output file stream 'file' */
2540 static
2541 SCIP_DECL_DISPOUTPUT(dispOutputSols)
2542 { /*lint --e{715}*/
2543 #ifndef NDEBUG
2544  SCIP_CONSHDLR* conshdlr;
2545 #endif
2546  SCIP_Longint sols;
2547  SCIP_Bool valid;
2548 
2549  assert(disp != NULL);
2550  assert(strcmp(SCIPdispGetName(disp), DISP_SOLS_NAME) == 0);
2551  assert(scip != NULL);
2552 
2553 #ifndef NDEBUG
2554  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2555  assert( conshdlr != NULL );
2556  assert( SCIPconshdlrGetNConss(conshdlr) == 0 );
2557 #endif
2558 
2559  sols = SCIPgetNCountedSols(scip, &valid);
2560 
2561  if( !valid )
2562  {
2563  SCIPinfoMessage(scip, file, "TooMany");
2564  }
2565  else
2566  {
2568  }
2569 
2570  return SCIP_OKAY;
2571 }
2572 
2573 
2574 /** output method of display column to output file stream 'file' */
2575 static
2576 SCIP_DECL_DISPOUTPUT(dispOutputFeasSubtrees)
2577 { /*lint --e{715}*/
2578 #ifndef NDEBUG
2579  SCIP_CONSHDLR* conshdlr;
2580 #endif
2581 
2582  assert(disp != NULL);
2583  assert(scip != NULL);
2584  assert(strcmp(SCIPdispGetName(disp), DISP_CUTS_NAME) == 0);
2585 
2586 #ifndef NDEBUG
2587  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2588  assert( conshdlr != NULL );
2589  assert( SCIPconshdlrGetNConss(conshdlr) == 0 );
2590 #endif
2591 
2593 
2594  return SCIP_OKAY;
2595 }
2596 
2597 
2598 /*
2599  * Interface methods of constraint handler
2600  */
2601 
2602 /** creates the handler for countsols constraints and includes it in SCIP */
2603 static
2605  SCIP* scip, /**< SCIP data structure */
2606  SCIP_Bool dialogs /**< sould count dialogs be added */
2607  )
2608 {
2609  /* create countsol constraint handler data */
2610  SCIP_CONSHDLRDATA* conshdlrdata;
2611  SCIP_CONSHDLR* conshdlr;
2612 
2613 #ifdef SCIP_WITH_GMP
2614  char gmpversion[20];
2615 #endif
2616 
2617  /* create constraint handler specific data here */
2618  SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata) );
2619 
2620  /* include constraint handler */
2623  consEnfolpCountsols, consEnfopsCountsols, consCheckCountsols, consLockCountsols,
2624  conshdlrdata) );
2625 
2626  assert(conshdlr != NULL);
2627 
2628  /* set non-fundamental callbacks via specific setter functions */
2629  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyCountsols, consCopyCountsols) );
2630  SCIP_CALL( SCIPsetConshdlrExit(scip, conshdlr, consExitCountsols) );
2631  SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolCountsols) );
2632  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeCountsols) );
2633  SCIP_CALL( SCIPsetConshdlrInit(scip, conshdlr, consInitCountsols) );
2634  SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolCountsols) );
2635  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxCountsols) );
2636 
2637  /* add countsols constraint handler parameters */
2639  "constraints/" CONSHDLR_NAME "/active",
2640  "is the constraint handler active?",
2641  &conshdlrdata->active, FALSE, DEFAULT_ACTIVE, NULL, NULL));
2643  "constraints/" CONSHDLR_NAME "/sparsetest",
2644  "should the sparse solution test be turned on?",
2645  &conshdlrdata->sparsetest, FALSE, DEFAULT_SPARSETEST, NULL, NULL));
2647  "constraints/" CONSHDLR_NAME "/discardsols",
2648  "is it allowed to discard solutions?",
2649  &conshdlrdata->discardsols, FALSE, DEFAULT_DISCARDSOLS, NULL, NULL));
2651  "constraints/" CONSHDLR_NAME "/collect",
2652  "should the solutions be collected?",
2653  &conshdlrdata->collect, FALSE, DEFAULT_COLLECT, NULL, NULL));
2655  "constraints/" CONSHDLR_NAME "/sollimit",
2656  "counting stops, if the given number of solutions were found (-1: no limit)",
2657  &conshdlrdata->sollimit, FALSE, DEFAULT_SOLLIMIT, -1LL, SCIP_LONGINT_MAX, NULL, NULL));
2658 
2659  /* create the interactive shell dialogs for the counting process */
2660  if( dialogs )
2661  {
2662  SCIP_CALL( createCountDialog(scip) );
2663  }
2664 
2665  /* include display column */
2667  NULL, NULL, NULL, NULL, NULL, NULL, dispOutputSols,
2670  NULL, NULL, NULL, NULL, NULL, NULL, dispOutputFeasSubtrees,
2672 
2673 #ifdef SCIP_WITH_GMP
2674 #ifdef mpir_version
2675  /* add info about using MPIR to external codes information */
2676  (void) SCIPsnprintf(gmpversion, (int) sizeof(gmpversion), "MPIR %s", mpir_version);
2677  SCIP_CALL( SCIPincludeExternalCodeInformation(scip, gmpversion, "Multiple Precision Integers and Rationals Library developed by W. Hart (mpir.org)") );
2678 #else
2679  /* add info about using GMP to external codes information */
2680  (void) SCIPsnprintf(gmpversion, (int) sizeof(gmpversion), "GMP %s", gmp_version);
2681  SCIP_CALL( SCIPincludeExternalCodeInformation(scip, gmpversion, "GNU Multiple Precision Arithmetic Library developed by T. Granlund (gmplib.org)") );
2682 #endif
2683 #endif
2684 
2685  return SCIP_OKAY;
2686 }
2687 
2688 /** creates the handler for countsols constraints and includes it in SCIP */
2690  SCIP* scip /**< SCIP data structure */
2691  )
2692 {
2693  /* include constraint handler including the count dialog */
2695 
2696  return SCIP_OKAY;
2697 }
2698 
2699 
2700 /** execute counting */
2702  SCIP* scip /**< SCIP data structure */
2703  )
2704 {
2705  SCIP_Bool active;
2706 
2707  /* activate constraint handler cons_countsols */
2708  SCIP_CALL( SCIPgetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", &active) );
2709  if( !active )
2710  {
2711  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", TRUE) );
2712  }
2713 
2714  /* check if the parameter setting allows a valid counting process */
2715  SCIP_CALL( checkParameters(scip) );
2716 
2717  /* start the solving process */
2718  SCIP_CALL( SCIPsolve(scip) );
2719 
2720  /* reset activity status of constraint handler cons_countsols */
2721  if( !active )
2722  {
2723  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", FALSE) );
2724  }
2725 
2726  return SCIP_OKAY;
2727 }
2728 
2729 
2730 /** returns number of feasible solutions found as SCIP_Longint; if the number does not fit into
2731  * a SCIP_Longint the valid flag is set to FALSE
2732  */
2734  SCIP* scip, /**< SCIP data structure */
2735  SCIP_Bool* valid /**< pointer to store if the return value is valid */
2736  )
2737 {
2738  SCIP_CONSHDLR* conshdlr;
2739  SCIP_CONSHDLRDATA* conshdlrdata;
2740 
2741  /* find the countsols constraint handler */
2742  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2743  assert( conshdlr != NULL );
2744 
2745  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2746  assert( conshdlrdata != NULL );
2747 
2748  return getNCountedSols(conshdlrdata->nsols, valid);
2749 }
2750 
2751 
2752 /** puts the number of counted solutions in the given char* buffer */
2754  SCIP* scip, /**< SCIP data structure */
2755  char** buffer, /**< buffer to store the number for counted solutions */
2756  int buffersize, /**< buffer size */
2757  int* requiredsize /**< pointer to store the required size */
2758  )
2759 {
2760  SCIP_CONSHDLR* conshdlr;
2761  SCIP_CONSHDLRDATA* conshdlrdata;
2762 
2763  /* find the countsols constraint handler */
2764  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2765  assert( conshdlr != NULL );
2766 
2767  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2768  assert( conshdlrdata != NULL );
2769 
2770 #ifdef SCIP_WITH_GMP
2771  /* size must be by two larger than the length of the string, since there need to be storage for a sign and a
2772  * null-termination
2773  */
2774  assert(0 <= (int) (mpz_sizeinbase( conshdlrdata->nsols, 10 ) + 2));
2775  *requiredsize = (int) (mpz_sizeinbase( conshdlrdata->nsols, 10 ) + 2);
2776  if( *requiredsize <= buffersize)
2777  toString(conshdlrdata->nsols, buffer, buffersize);
2778 #else
2779  if( conshdlrdata->nsols < pow(10.0, (double)buffersize) )
2780  {
2781  toString(conshdlrdata->nsols, buffer, buffersize);
2782  *requiredsize = (int)strlen(*buffer);
2783  }
2784  else
2785  *requiredsize = 21;
2786 #endif
2787 }
2788 
2789 
2790 /** returns number of counted non trivial feasible subtrees */
2792  SCIP* scip /**< SCIP data structure */
2793  )
2794 {
2795  SCIP_CONSHDLR* conshdlr;
2796  SCIP_CONSHDLRDATA* conshdlrdata;
2797 
2798  assert( scip != NULL );
2799 
2800  /* find the countsols constraint handler */
2801  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2802  assert( conshdlr != NULL );
2803 
2804  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2805  assert( conshdlrdata != NULL );
2806 
2807  return conshdlrdata->feasST;
2808 }
2809 
2810 
2811 /** Method to get the sparse solution.
2812  *
2813  * @note You get the pointer to the sparse solutions stored in the constraint handler (not a copy).
2814  *
2815  * @note The sparse solutions are stored w.r.t. the active variables. There are the variables which have not been removed
2816  * during presolving. For none active variables the value has to be computed depending on their aggregation
2817  * type. See for more details about that \ref COLLECTALLFEASEBLES.
2818  */
2820  SCIP* scip, /**< SCIP data structure */
2821  SCIP_VAR*** vars, /**< pointer to active variable array defining to variable order */
2822  int* nvars, /**< number of active variables */
2823  SCIP_SPARSESOL*** sols, /**< pointer to the solutions */
2824  int* nsols /**< pointer to number of solutions */
2825  )
2826 {
2827  SCIP_CONSHDLR* conshdlr;
2828  SCIP_CONSHDLRDATA* conshdlrdata;
2829 
2830  assert( scip != NULL );
2831 
2832  /* find the countsols constraint handler */
2833  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2834  assert( conshdlr != NULL );
2835 
2836  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2837  assert( conshdlrdata != NULL );
2838 
2839  *vars = conshdlrdata->vars;
2840  *nvars = conshdlrdata->nvars;
2841  *sols = conshdlrdata->solutions;
2842  *nsols = conshdlrdata->nsolutions;
2843 }
2844 
2845 /** setting SCIP parameters for such that a valid counting process is possible */
2847  SCIP* scip /**< SCIP data structure */
2848  )
2849 {
2851  return SCIP_OKAY;
2852 }
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:1438
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:1247
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
#define SYM_TIMING_AFTERPRESOL
Definition: type_symmetry.h:52
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
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:4258
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:2498
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:2328
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:1737
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:1213
#define SCIP_Real
Definition: def.h:173
#define DISP_CUTS_POSITION
SCIP_Longint Int
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:734
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:3430
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:9993
public methods for display handler plugins
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip_var.c:1526
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