1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 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_conjunction.c
26   	 * @ingroup DEFPLUGINS_CONS
27   	 * @brief  constraint handler for conjunction constraints
28   	 * @author Tobias Achterberg
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#include "blockmemshell/memory.h"
34   	#include "scip/cons_conjunction.h"
35   	#include "scip/pub_cons.h"
36   	#include "scip/pub_message.h"
37   	#include "scip/scip_cons.h"
38   	#include "scip/scip_copy.h"
39   	#include "scip/scip_general.h"
40   	#include "scip/scip_mem.h"
41   	#include "scip/scip_message.h"
42   	#include "scip/scip_prob.h"
43   	#include "scip/scip_sol.h"
44   	#include <string.h>
45   	
46   	
47   	
48   	/* constraint handler properties */
49   	#define CONSHDLR_NAME          "conjunction"
50   	#define CONSHDLR_DESC          "conjunction of constraints"
51   	#define CONSHDLR_ENFOPRIORITY   +900000 /**< priority of the constraint handler for constraint enforcing */
52   	#define CONSHDLR_CHECKPRIORITY  -900000 /**< priority of the constraint handler for checking feasibility */
53   	#define CONSHDLR_EAGERFREQ          100 /**< frequency for using all instead of only the useful constraints in separation,
54   	                                              *   propagation and enforcement, -1 for no eager evaluations, 0 for first only */
55   	#define CONSHDLR_MAXPREROUNDS        -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
56   	#define CONSHDLR_NEEDSCONS         TRUE /**< should the constraint handler be skipped, if no constraints are available? */
57   	
58   	#define CONSHDLR_PRESOLTIMING            SCIP_PRESOLTIMING_FAST
59   	
60   	/*
61   	 * Data structures
62   	 */
63   	
64   	/** constraint data for conjunction constraints */
65   	struct SCIP_ConsData
66   	{
67   	   SCIP_CONS**           conss;              /**< constraints in conjunction */
68   	   int                   consssize;          /**< size of conss array */
69   	   int                   nconss;             /**< number of constraints in conjunction */
70   	};
71   	
72   	
73   	/*
74   	 * Local methods
75   	 */
76   	
77   	/** creates conjunction constraint data, captures initial constraints of conjunction */
78   	static
79   	SCIP_RETCODE consdataCreate(
80   	   SCIP*                 scip,               /**< SCIP data structure */
81   	   SCIP_CONSDATA**       consdata,           /**< pointer to constraint data */
82   	   SCIP_CONS**           conss,              /**< initial constraint in conjunction */
83   	   int                   nconss              /**< number of initial constraints in conjunction */
84   	   )
85   	{
86   	   assert(consdata != NULL);
87   	
88   	   SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
89   	   if( nconss > 0 )
90   	   {
91   	      SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->conss, conss, nconss) );
92   	      (*consdata)->consssize = nconss;
93   	      (*consdata)->nconss = nconss;
94   	
95   	      if( SCIPisTransformed(scip) )
96   	      {
97   	         SCIP_CALL( SCIPtransformConss(scip, nconss, (*consdata)->conss, (*consdata)->conss) );
98   	      }
99   	      else
100  	      {
101  		 int c;
102  	
103  		 for( c = 0; c < nconss; ++c )
104  		 {
105  		    SCIP_CALL( SCIPcaptureCons(scip, conss[c]) );
106  		 }
107  	      }
108  	   }
109  	   else
110  	   {
111  	      (*consdata)->conss = NULL;
112  	      (*consdata)->consssize = 0;
113  	      (*consdata)->nconss = 0;
114  	   }
115  	
116  	   return SCIP_OKAY;
117  	}
118  	
119  	/** frees constraint data and releases all constraints in conjunction */
120  	static
121  	SCIP_RETCODE consdataFree(
122  	   SCIP*                 scip,               /**< SCIP data structure */
123  	   SCIP_CONSDATA**       consdata            /**< pointer to constraint data */
124  	   )
125  	{
126  	   int c;
127  	
128  	   assert(consdata != NULL);
129  	   assert(*consdata != NULL);
130  	
131  	   /* release constraints */
132  	   for( c = 0; c < (*consdata)->nconss; ++c )
133  	   {
134  	      SCIP_CALL( SCIPreleaseCons(scip, &(*consdata)->conss[c]) );
135  	   }
136  	
137  	   /* free memory */
138  	   SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->conss, (*consdata)->consssize);
139  	   SCIPfreeBlockMemory(scip, consdata);
140  	
141  	   return SCIP_OKAY;
142  	}
143  	
144  	/** adds constraint to conjunction */
145  	static
146  	SCIP_RETCODE consdataAddCons(
147  	   SCIP*                 scip,               /**< SCIP data structure */
148  	   SCIP_CONSDATA*        consdata,           /**< constraint data */
149  	   SCIP_CONS*            cons                /**< constraint to add to the conjunction */
150  	   )
151  	{
152  	   assert(consdata != NULL);
153  	
154  	   /* get memory for additional constraint */
155  	   SCIP_CALL( SCIPensureBlockMemoryArray(scip, &consdata->conss, &consdata->consssize, consdata->nconss+1) );
156  	   assert(consdata->conss != NULL);
157  	   assert(consdata->nconss < consdata->consssize);
158  	
159  	   /* insert constraint in array */
160  	   consdata->conss[consdata->nconss] = cons;
161  	   consdata->nconss++;
162  	
163  	   if( SCIPisTransformed(scip) )
164  	   {
165  	      SCIP_CALL( SCIPtransformCons(scip, consdata->conss[consdata->nconss - 1], &(consdata->conss[consdata->nconss - 1])) );
166  	   }
167  	   else
168  	   {
169  	      /* capture constraint */
170  	      SCIP_CALL( SCIPcaptureCons(scip, cons) );
171  	   }
172  	
173  	   return SCIP_OKAY;
174  	}
175  	
176  	/** adds all constraints in conjunction constraints to the problem; disables unmodifiable conjunction constraints */
177  	static
178  	SCIP_RETCODE addAllConss(
179  	   SCIP*                 scip,               /**< SCIP data structure */
180  	   SCIP_CONS**           conss,              /**< active conjunction constraints */
181  	   int                   nconss,             /**< number of active conjunction constraints */
182  	   SCIP_RESULT*          result              /**< pointer to store the result */
183  	   )
184  	{
185  	   SCIP_CONSDATA* consdata;
186  	   int c;
187  	   int i;
188  	
189  	   assert(result != NULL);
190  	
191  	   for( c = 0; c < nconss; ++c )
192  	   {
193  	      consdata = SCIPconsGetData(conss[c]);
194  	      assert(consdata != NULL);
195  	
196  	      /* add all inactive constraints to local subproblem */
197  	      for( i = 0; i < consdata->nconss; ++i )
198  	      {
199  		 /* update check flag for sub constraints when upgrade takes place */
200  		 if( SCIPconsIsChecked(conss[c]) )
201  		 {
202  		    /* make sure, the constraint is checked for feasibility */
203  		    SCIP_CALL( SCIPsetConsChecked(scip, consdata->conss[i], TRUE) );
204  		 }
205  	
206  	         if( !SCIPconsIsActive(consdata->conss[i]) )
207  	         {
208  	            SCIPdebugMsg(scip, "adding constraint <%s> from add conjunction <%s>\n",
209  	               SCIPconsGetName(consdata->conss[i]), SCIPconsGetName(conss[c]));
210  	            SCIP_CALL( SCIPaddConsLocal(scip, consdata->conss[i], NULL) );
211  	            *result = SCIP_CONSADDED;
212  	         }
213  	      }
214  	
215  	      /* disable conjunction constraint, if it is unmodifiable */
216  	      if( !SCIPconsIsModifiable(conss[c]) )
217  	      {
218  	         SCIP_CALL( SCIPdelConsLocal(scip, conss[c]) );
219  	      }
220  	   }
221  	
222  	   return SCIP_OKAY;
223  	}
224  	
225  	/** checks all constraints in conjunction constraints for feasibility */
226  	static
227  	SCIP_RETCODE checkAllConss(
228  	   SCIP*                 scip,               /**< SCIP data structure */
229  	   SCIP_CONS**           conss,              /**< active conjunction constraints */
230  	   int                   nconss,             /**< number of active conjunction constraints */
231  	   SCIP_SOL*             sol,                /**< solution to check */
232  	   SCIP_Bool             checkintegrality,   /**< Has integrality to be checked? */
233  	   SCIP_Bool             checklprows,        /**< Do constraints represented by rows in the current LP have to be checked? */
234  	   SCIP_Bool             printreason,        /**< Should the reason for the violation be printed? */
235  	   SCIP_Bool             completely,         /**< Should all violations be checked? */
236  	   SCIP_RESULT*          result              /**< pointer to store the result */
237  	   )
238  	{
239  	   SCIP_CONSDATA* consdata;
240  	   int c;
241  	   int i;
242  	
243  	   assert(result != NULL);
244  	
245  	   *result = SCIP_FEASIBLE;
246  	
247  	   for( c = 0; c < nconss && (*result == SCIP_FEASIBLE || completely); ++c )
248  	   {
249  	      SCIP_RESULT subresult = SCIP_FEASIBLE;
250  	
251  	      consdata = SCIPconsGetData(conss[c]);
252  	      assert(consdata != NULL);
253  	
254  	      /* check all constraints */
255  	      for( i = 0; i < consdata->nconss && subresult == SCIP_FEASIBLE; ++i )
256  	      {
257  	         SCIP_CALL( SCIPcheckCons(scip, consdata->conss[i], sol, checkintegrality, checklprows, printreason, &subresult) );
258  	         assert(subresult == SCIP_FEASIBLE || subresult == SCIP_INFEASIBLE);
259  	      }
260  	
261  	      if( subresult == SCIP_INFEASIBLE )
262  	      {
263  	         /* mark solution as violated */
264  	         *result = SCIP_INFEASIBLE;
265  	         /* update constraint violation in solution */
266  	         if ( sol != NULL )
267  	            SCIPupdateSolConsViolation(scip, sol, 1.0, 1.0);
268  	         if( printreason )
269  	         {
270  	            assert( 0 < i && i <= consdata->nconss );
271  	            SCIPinfoMessage(scip, NULL, "Conjunction constraint %s is violated, at least the sub-constraint %s is violated by this given solution.\n",
272  	               SCIPconsGetName(conss[c]), SCIPconsGetName(consdata->conss[i-1]));
273  	            SCIPdebug( SCIP_CALL( SCIPprintCons(scip, conss[c], NULL) ) );
274  	         }
275  	      }
276  	   }
277  	
278  	   return SCIP_OKAY;
279  	}
280  	
281  	
282  	/*
283  	 * Callback methods of constraint handler
284  	 */
285  	
286  	
287  	 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
288  	static
289  	SCIP_DECL_CONSHDLRCOPY(conshdlrCopyConjunction)
290  	{  /*lint --e{715}*/
291  	   assert(scip != NULL);
292  	   assert(conshdlr != NULL);
293  	   assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
294  	
295  	   /* call inclusion method of constraint handler */
296  	   SCIP_CALL( SCIPincludeConshdlrConjunction(scip) );
297  	
298  	   *valid = TRUE;
299  	
300  	   return SCIP_OKAY;
301  	}
302  	
303  	
304  	/** frees specific constraint data */
305  	static
306  	SCIP_DECL_CONSDELETE(consDeleteConjunction)
307  	{  /*lint --e{715}*/
308  	   SCIP_CALL( consdataFree(scip, consdata) );
309  	
310  	   return SCIP_OKAY;
311  	}
312  	
313  	/** transforms constraint data into data belonging to the transformed problem */
314  	static
315  	SCIP_DECL_CONSTRANS(consTransConjunction)
316  	{  /*lint --e{715}*/
317  	   SCIP_CONSDATA* sourcedata;
318  	   SCIP_CONSDATA* targetdata;
319  	   int c;
320  	
321  	   /* create constraint data for target constraint */
322  	   SCIP_CALL( SCIPallocBlockMemory(scip, &targetdata) );
323  	
324  	   /* get constraint data of source constraint */
325  	   sourcedata = SCIPconsGetData(sourcecons);
326  	
327  	   if( sourcedata->nconss > 0 )
328  	   {
329  	      targetdata->consssize = sourcedata->nconss;
330  	      targetdata->nconss = sourcedata->nconss;
331  	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &targetdata->conss, targetdata->consssize) );
332  	      for( c = 0; c < sourcedata->nconss; ++c )
333  	      {
334  	         SCIP_CALL( SCIPtransformCons(scip, sourcedata->conss[c], &targetdata->conss[c]) );
335  	      }
336  	   }
337  	   else
338  	   {
339  	      targetdata->conss = NULL;
340  	      targetdata->consssize = 0;
341  	      targetdata->nconss = 0;
342  	   }
343  	
344  	   /* create target constraint */
345  	   SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
346  	         SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
347  	         SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
348  	         SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons), 
349  	         SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
350  	
351  	   return SCIP_OKAY;
352  	}
353  	
354  	
355  	/** constraint enforcing method of constraint handler for LP solutions */
356  	static
357  	SCIP_DECL_CONSENFOLP(consEnfolpConjunction)
358  	{  /*lint --e{715}*/
359  	   *result = SCIP_FEASIBLE;
360  	
361  	   /* add all constraints to the current node */
362  	   SCIP_CALL( addAllConss(scip, conss, nconss, result) );
363  	
364  	   return SCIP_OKAY;
365  	}
366  	
367  	
368  	/** constraint enforcing method of constraint handler for relaxation solutions */
369  	static
370  	SCIP_DECL_CONSENFORELAX(consEnforelaxConjunction)
371  	{  /*lint --e{715}*/
372  	   *result = SCIP_FEASIBLE;
373  	
374  	   /* add all constraints to the current node */
375  	   SCIP_CALL( addAllConss(scip, conss, nconss, result) );
376  	
377  	   return SCIP_OKAY;
378  	}
379  	
380  	
381  	/** constraint enforcing method of constraint handler for pseudo solutions */
382  	static
383  	SCIP_DECL_CONSENFOPS(consEnfopsConjunction)
384  	{  /*lint --e{715}*/
385  	   *result = SCIP_FEASIBLE;
386  	
387  	   /* add all constraints to the current node */
388  	   SCIP_CALL( addAllConss(scip, conss, nconss, result) );
389  	
390  	   return SCIP_OKAY;
391  	}
392  	
393  	
394  	/** feasibility check method of constraint handler for integral solutions */
395  	static
396  	SCIP_DECL_CONSCHECK(consCheckConjunction)
397  	{  /*lint --e{715}*/
398  	   *result = SCIP_FEASIBLE;
399  	
400  	   /* check all constraints of the conjunction */
401  	   SCIP_CALL( checkAllConss(scip, conss, nconss, sol, checkintegrality, checklprows, printreason, completely, result) );
402  	
403  	   return SCIP_OKAY;
404  	}
405  	
406  	
407  	/** presolving method of constraint handler */
408  	static
409  	SCIP_DECL_CONSPRESOL(consPresolConjunction)
410  	{  /*lint --e{715}*/
411  	   SCIP_CONSDATA* consdata;
412  	   int c;
413  	   int i;
414  	
415  	   assert(result != NULL);
416  	
417  	   *result = SCIP_DIDNOTFIND;
418  	
419  	   /* all constraints in a conjunction constraint of the global problem can be added directly to the problem and
420  	    * removed from the conjunction constraint;
421  	    * an unmodifiable conjunction constraint can be deleted
422  	    */
423  	   for( c = 0; c < nconss; ++c )
424  	   {
425  	      consdata = SCIPconsGetData(conss[c]);
426  	      assert(consdata != NULL);
427  	
428  	      /* add all inactive constraints to the global problem */
429  	      for( i = 0; i < consdata->nconss; ++i )
430  	      {
431  		 /* update check flag for sub constraints when upgrade takes place */
432  		 if( SCIPconsIsChecked(conss[c]) )
433  		 {
434  		    /* make sure, the constraint is checked for feasibility */
435  		    SCIP_CALL( SCIPsetConsChecked(scip, consdata->conss[i], TRUE) );
436  		 }
437  	
438  	         /* add constraint, if it is not active yet */
439  	         if( !SCIPconsIsActive(consdata->conss[i]) )
440  	         {
441  	            SCIPdebugMsg(scip, "adding constraint <%s> from add conjunction <%s>\n",
442  	               SCIPconsGetName(consdata->conss[i]), SCIPconsGetName(conss[c]));
443  	            SCIP_CALL( SCIPaddCons(scip, consdata->conss[i]) );
444  	            *result = SCIP_SUCCESS;
445  	         }
446  	         /* release constraint because it will be removed from the conjunction constraint */
447  	         SCIP_CALL( SCIPreleaseCons(scip, &(consdata->conss[i])) );
448  	      }
449  	      /* all constraints where removed, so we need to clear the array */
450  	      consdata->nconss = 0;
451  	
452  	      /* delete conjunction constraint, if it is unmodifiable */
453  	      if( !SCIPconsIsModifiable(conss[c]) )
454  	      {
455  	         SCIP_CALL( SCIPdelCons(scip, conss[c]) );
456  	      }
457  	   }
458  	
459  	   return SCIP_OKAY;
460  	}
461  	
462  	
463  	/** variable rounding lock method of constraint handler */
464  	static
465  	SCIP_DECL_CONSLOCK(consLockConjunction)
466  	{  /*lint --e{715}*/
467  	   SCIP_CONSDATA* consdata;
468  	   int c;
469  	
470  	   assert(locktype == SCIP_LOCKTYPE_MODEL);
471  	
472  	   consdata = SCIPconsGetData(cons);
473  	   assert(consdata != NULL);
474  	
475  	   /* lock sub constraints */
476  	   for( c = 0; c < consdata->nconss; ++c )
477  	   {
478  	      SCIP_CALL( SCIPaddConsLocksType(scip, consdata->conss[c], locktype, nlockspos, nlocksneg) );
479  	   }
480  	
481  	   return SCIP_OKAY;
482  	}
483  	
484  	
485  	/** constraint display method of constraint handler */
486  	static
487  	SCIP_DECL_CONSPRINT(consPrintConjunction)
488  	{  /*lint --e{715}*/
489  	   SCIP_CONSDATA* consdata;
490  	   int i;
491  	
492  	   assert( scip != NULL );
493  	   assert( conshdlr != NULL );
494  	   assert( cons != NULL );
495  	
496  	   consdata = SCIPconsGetData(cons);
497  	   assert(consdata != NULL);
498  	
499  	   SCIPinfoMessage(scip, file, "conjunction(");
500  	
501  	   for( i = 0; i < consdata->nconss; ++i )
502  	   {
503  	      if( i > 0 )
504  	         SCIPinfoMessage(scip, file, ", ");
505  	      SCIP_CALL( SCIPprintCons(scip, consdata->conss[i], file) );
506  	   }
507  	   SCIPinfoMessage(scip, file, ")");
508  	
509  	   return SCIP_OKAY;
510  	}
511  	
512  	/** constraint parsing method of constraint handler */
513  	static
514  	SCIP_DECL_CONSPARSE(consParseConjunction)
515  	{  /*lint --e{715}*/
516  	   SCIP_CONS** conss;
517  	   int nconss;
518  	   int sconss;
519  	   char* token;
520  	   char* saveptr;
521  	   char* nexttokenstart;
522  	   char* copystr;
523  	
524  	   assert(scip != NULL);
525  	   assert(conshdlr != NULL);
526  	   assert(cons != NULL);
527  	   assert(success != NULL);
528  	   assert(str != NULL);
529  	   assert(name != NULL);
530  	
531  	   SCIPdebugMsg(scip, "parsing conjunction <%s>\n", name);
532  	
533  	   *success = TRUE;
534  	
535  	   /* allocate memory for constraint in conjunction, initial size is set to 10 */
536  	   nconss = 0;
537  	   sconss = 10;
538  	   SCIP_CALL( SCIPallocBufferArray(scip, &conss, sconss) );
539  	   SCIP_CALL( SCIPduplicateBufferArray(scip, &copystr, str, (int)strlen(str)+1) );
540  	
541  	   /* find '(' at the beginning, string should start with 'conjunction(' */
542  	   saveptr = strpbrk(copystr, "("); /*lint !e158*/
543  	
544  	   if( saveptr == NULL )
545  	   {
546  	      SCIPdebugMsg(scip, "error parsing conjunctive constraint: \"%s\"\n", str);
547  	      *success = FALSE;
548  	      goto TERMINATE;
549  	   }
550  	   assert(saveptr != NULL); /* for lint */
551  	
552  	   /* skip '(' */
553  	   ++saveptr;
554  	   /* remember token start position */
555  	   nexttokenstart = saveptr;
556  	
557  	   /* brackets '(' and ')' can exist co we check for them and the constraint delimeter */
558  	   saveptr = strpbrk(saveptr, "(,");
559  	
560  	   /* brackets '(' and ')' can exist in the rest of the string so we need to skip them to find the end of the first
561  	    * sub-constraint marked by a ','
562  	    */
563  	   if( saveptr != NULL )
564  	   {
565  	      do
566  	      {
567  		 int bracketcounter = 0;
568  	
569  		 if( *saveptr == '(' )
570  		 {
571  		    do
572  		    {
573  		       ++bracketcounter;
574  		       ++saveptr;
575  	
576  		       /* find last ending bracket */
577  		       while( bracketcounter > 0 )
578  		       {
579  			  saveptr = strpbrk(saveptr, "()");
580  	
581  			  if( saveptr != NULL )
582  			  {
583  			     if( *saveptr == '(' )
584  				++bracketcounter;
585  			     else
586  				--bracketcounter;
587  	
588  			     ++saveptr;
589  			  }
590  			  else
591  			  {
592  			     SCIPdebugMsg(scip, "error parsing conjunctive constraint: \"%s\"\n", str);
593  			     *success = FALSE;
594  			     goto TERMINATE;
595  			  }
596  		       }
597  	
598  		       saveptr = strpbrk(saveptr, "(,");
599  		    }
600  		    while( saveptr != NULL && *saveptr == '(' );
601  		 }
602  	
603  		 /* we found a ',' so the end of the first sub-constraint is determined */
604  		 if( saveptr != NULL )
605  		 {
606  		    assert(*saveptr == ',');
607  	
608  		    /* resize constraint array if necessary */
609  		    if( nconss == sconss )
610  		    {
611  		       sconss = SCIPcalcMemGrowSize(scip, nconss+1);
612  		       assert(nconss < sconss);
613  	
614  		       SCIP_CALL( SCIPreallocBufferArray(scip, &conss, sconss) );
615  		    }
616  	            assert(nexttokenstart != NULL); /* for lint */
617  		    assert(saveptr > nexttokenstart);
618  	
619  		    /* extract token for parsing */
620  		    SCIP_CALL( SCIPduplicateBufferArray(scip, &token, nexttokenstart, saveptr - nexttokenstart + 1) );
621  		    token[saveptr - nexttokenstart] = '\0';
622  	
623  		    SCIPdebugMsg(scip, "conjunctive parsing token(constraint): %s\n", token);
624  	
625  		    /* parsing a constraint, part of the conjunction */
626  		    SCIP_CALL( SCIPparseCons(scip, &(conss[nconss]), token, initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode, success) );
627  	
628  		    SCIPfreeBufferArray(scip, &token);
629  	
630  		    if( *success )
631  		       ++nconss;
632  		    else
633  		    {
634  		       SCIPdebugMsg(scip, "error parsing conjunctive constraint: \"%s\"\n", str);
635  		       goto TERMINATE;
636  		    }
637  		    /* skip ',' delimeter */
638  		    ++saveptr;
639  		    /* remember token start position */
640  		    nexttokenstart = saveptr;
641  	
642  		    saveptr = strpbrk(saveptr, "(,");
643  		 }
644  	      }
645  	      while( saveptr != NULL );
646  	   }
647  	
648  	   /* find end of conjunction constraint */
649  	   saveptr = strrchr(nexttokenstart, ')');
650  	
651  	   if( saveptr == NULL )
652  	   {
653  	      SCIPdebugMsg(scip, "error parsing conjunctive constraint: \"%s\"\n", str);
654  	      *success = FALSE;
655  	      goto TERMINATE;
656  	   }
657  	   /* parse last sub-constraint */
658  	   else
659  	   {
660  	      /* resize constraint array if necessary */
661  	      if( nconss == sconss )
662  	      {
663  		 ++sconss;
664  		 SCIP_CALL( SCIPreallocBufferArray(scip, &conss, sconss) );
665  	      }
666  	
667  	      assert(saveptr > nexttokenstart);
668  	
669  	      /* extract token for parsing */
670  	      SCIP_CALL( SCIPduplicateBufferArray(scip, &token, nexttokenstart, saveptr - nexttokenstart + 1) );
671  	      token[saveptr - nexttokenstart] = '\0';
672  	
673  	      SCIPdebugMsg(scip, "conjunctive parsing token(constraint): %s\n", token);
674  	
675  	      /* parsing a constraint, part of the conjunction */
676  	      SCIP_CALL( SCIPparseCons(scip, &(conss[nconss]), token, initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode, success) );
677  	
678  	      if( *success )
679  		 ++nconss;
680  	
681  	      SCIPfreeBufferArray(scip, &token);
682  	   }
683  	   assert(nconss > 0 || !(*success));
684  	
685  	   /* if parsing sub-constraints was fine, create the conjunctive constraint */
686  	   if( *success )
687  	   {
688  	      /* create conjunctive constraint */
689  	      SCIP_CALL( SCIPcreateConsConjunction(scip, cons, name, nconss, conss,
690  		    enforce, check, local, modifiable, dynamic) );
691  	   }
692  	
693  	   /* free parsed constraints */
694  	   for( --nconss; nconss >= 0; --nconss )
695  	   {
696  	      SCIP_CALL( SCIPreleaseCons(scip, &conss[nconss]) );
697  	   }
698  	
699  	 TERMINATE:
700  	   /* free temporary memory */
701  	   SCIPfreeBufferArray(scip, &copystr);
702  	   SCIPfreeBufferArray(scip, &conss);
703  	
704  	   return SCIP_OKAY;
705  	}
706  	
707  	/** constraint copying method of constraint handler */
708  	static
709  	SCIP_DECL_CONSCOPY(consCopyConjunction)
710  	{  /*lint --e{715}*/
711  	   SCIP_CONSDATA* sourcedata;
712  	   SCIP_CONS** sourceconss;
713  	   SCIP_CONS** conss;
714  	   int nconss;
715  	   int c;
716  	
717  	   *valid = TRUE;
718  	
719  	   sourcedata = SCIPconsGetData(sourcecons);
720  	   assert(sourcedata != NULL);
721  	
722  	   sourceconss = sourcedata->conss;
723  	   nconss = sourcedata->nconss;
724  	
725  	   if( nconss > 0 )
726  	   {
727  	      assert(sourceconss != NULL);
728  	
729  	      SCIP_CALL( SCIPallocBufferArray(scip, &conss, nconss) );
730  	
731  	      /* copy each constraint one by one */
732  	      for( c = 0; c < nconss && (*valid); ++c )
733  	      {
734  	         SCIP_CALL( SCIPgetConsCopy(sourcescip, scip, sourceconss[c], &conss[c], SCIPconsGetHdlr(sourceconss[c]),
735  	               varmap, consmap, SCIPconsGetName(sourceconss[c]),
736  	               SCIPconsIsInitial(sourceconss[c]), SCIPconsIsSeparated(sourceconss[c]), SCIPconsIsEnforced(sourceconss[c]),
737  	               SCIPconsIsChecked(sourceconss[c]), SCIPconsIsPropagated(sourceconss[c]),
738  	               SCIPconsIsLocal(sourceconss[c]), SCIPconsIsModifiable(sourceconss[c]),
739  	               SCIPconsIsDynamic(sourceconss[c]), SCIPconsIsRemovable(sourceconss[c]), SCIPconsIsStickingAtNode(sourceconss[c]),
740  	               global, valid) );
741  	         assert(!(*valid) || conss[c] != NULL);
742  	      }
743  	
744  	      if( *valid )
745  	      {
746  	         if( name == NULL )
747  	         {
748  	            SCIP_CALL( SCIPcreateConsConjunction(scip, cons, SCIPconsGetName(sourcecons), nconss, conss,
749  	                  enforce, check, local, modifiable, dynamic) );
750  	         }
751  	         else
752  	         {
753  	            SCIP_CALL( SCIPcreateConsConjunction(scip, cons, name, nconss, conss,
754  	                  enforce, check, local, modifiable, dynamic) );
755  	         }
756  	      }
757  	
758  	      /* release the copied constraints */
759  	      for( c = (*valid ? c - 1 : c - 2); c >= 0; --c )
760  	      {
761  	         assert(conss[c] != NULL);
762  	         SCIP_CALL( SCIPreleaseCons(scip, &conss[c]) );
763  	      }
764  	
765  	      SCIPfreeBufferArray(scip, &conss);
766  	   }
767  	
768  	   return SCIP_OKAY;
769  	}
770  	
771  	
772  	/*
773  	 * constraint specific interface methods
774  	 */
775  	
776  	/** creates the handler for conjunction constraints and includes it in SCIP */
777  	SCIP_RETCODE SCIPincludeConshdlrConjunction(
778  	   SCIP*                 scip                /**< SCIP data structure */
779  	   )
780  	{
781  	   SCIP_CONSHDLR* conshdlr;
782  	
783  	   /* include constraint handler */
784  	   SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC,
785  	         CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY, CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS,
786  	         consEnfolpConjunction, consEnfopsConjunction, consCheckConjunction, consLockConjunction,
787  	         NULL) );
788  	
789  	   assert(conshdlr != NULL);
790  	
791  	   /* set non-fundamental callbacks via specific setter functions */
792  	   SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyConjunction, consCopyConjunction) );
793  	   SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteConjunction) );
794  	   SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseConjunction) );
795  	   SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolConjunction, CONSHDLR_MAXPREROUNDS,
796  	         CONSHDLR_PRESOLTIMING) );
797  	   SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintConjunction) );
798  	   SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransConjunction) );
799  	   SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxConjunction) );
800  	
801  	   return SCIP_OKAY;
802  	}
803  	
804  	/** creates and captures a conjunction constraint
805  	 *
806  	 *  @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
807  	 */
808  	SCIP_RETCODE SCIPcreateConsConjunction(
809  	   SCIP*                 scip,               /**< SCIP data structure */
810  	   SCIP_CONS**           cons,               /**< pointer to hold the created constraint */
811  	   const char*           name,               /**< name of constraint */
812  	   int                   nconss,             /**< number of initial constraints in conjunction */
813  	   SCIP_CONS**           conss,              /**< initial constraint in conjunction */
814  	   SCIP_Bool             enforce,            /**< should the constraint be enforced during node processing?
815  	                                              *   TRUE for model constraints, FALSE for additional, redundant constraints. */
816  	   SCIP_Bool             check,              /**< should the constraint be checked for feasibility?
817  	                                              *   TRUE for model constraints, FALSE for additional, redundant constraints. */
818  	   SCIP_Bool             local,              /**< is constraint only valid locally?
819  	                                              *   Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
820  	   SCIP_Bool             modifiable,         /**< is constraint modifiable (subject to column generation)?
821  	                                              *   Usually set to FALSE. In column generation applications, set to TRUE if pricing
822  	                                              *   adds coefficients to this constraint. */
823  	   SCIP_Bool             dynamic             /**< is constraint subject to aging?
824  	                                              *   Usually set to FALSE. Set to TRUE for own cuts which 
825  	                                              *   are separated as constraints. */
826  	   )
827  	{
828  	   SCIP_CONSHDLR* conshdlr;
829  	   SCIP_CONSDATA* consdata;
830  	
831  	   /* find the conjunction constraint handler */
832  	   conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
833  	   if( conshdlr == NULL )
834  	   {
835  	      SCIPerrorMessage("conjunction constraint handler not found\n");
836  	      return SCIP_PLUGINNOTFOUND;
837  	   }
838  	
839  	   /* create constraint data */
840  	   SCIP_CALL( consdataCreate(scip, &consdata, conss, nconss) );
841  	
842  	   /* create constraint */
843  	   SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, FALSE, FALSE, enforce, check, FALSE,
844  	         local, modifiable, dynamic, FALSE, FALSE) );
845  	
846  	   return SCIP_OKAY;
847  	}
848  	
849  	/** creates and captures an and constraint
850  	 *  in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
851  	 *  method SCIPcreateConsConjunction(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
852  	 *
853  	 *  @see SCIPcreateConsConjunction() for information about the basic constraint flag configuration
854  	 *
855  	 *  @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
856  	 */
857  	SCIP_RETCODE SCIPcreateConsBasicConjunction(
858  	   SCIP*                 scip,               /**< SCIP data structure */
859  	   SCIP_CONS**           cons,               /**< pointer to hold the created constraint */
860  	   const char*           name,               /**< name of constraint */
861  	   int                   nconss,             /**< number of initial constraints in conjunction */
862  	   SCIP_CONS**           conss               /**< initial constraint in conjunction */
863  	   )
864  	{
865  	   assert(scip != NULL);
866  	
867  	   SCIP_CALL( SCIPcreateConsConjunction(scip, cons, name, nconss, conss,
868  	         TRUE, TRUE, FALSE, FALSE, FALSE) );
869  	
870  	   return SCIP_OKAY;
871  	}
872  	
873  	/** adds constraint to the conjunction of constraints */
874  	SCIP_RETCODE SCIPaddConsElemConjunction(
875  	   SCIP*                 scip,               /**< SCIP data structure */
876  	   SCIP_CONS*            cons,               /**< conjunction constraint */
877  	   SCIP_CONS*            addcons             /**< additional constraint in conjunction */
878  	   )
879  	{
880  	   SCIP_CONSDATA* consdata;
881  	
882  	   assert(cons != NULL);
883  	   assert(addcons != NULL);
884  	
885  	   if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
886  	   {
887  	      SCIPerrorMessage("constraint is not a conjunction constraint\n");
888  	      return SCIP_INVALIDDATA;
889  	   }
890  	
891  	   consdata = SCIPconsGetData(cons);
892  	   assert(consdata != NULL);
893  	
894  	   SCIP_CALL( consdataAddCons(scip, consdata, addcons) );
895  	
896  	   return SCIP_OKAY;
897  	}
898