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   heur_indicator.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  handle partial solutions for linear problems with indicators and otherwise continuous variables
28   	 * @author Marc Pfetsch
29   	 *
30   	 * For linear problems with indicators and otherwise continuous variables, the indicator constraint handler can produce
31   	 * partial solutions, i.e., values for the indicator variables. This partial solution can be passed to this heuristic,
32   	 * which then fixes these values and solves an LP. Additionally a local search for a better solution is added.
33   	 */
34   	
35   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
36   	
37   	#include "blockmemshell/memory.h"
38   	#include "scip/cons_indicator.h"
39   	#include "scip/heur_indicator.h"
40   	#include "scip/pub_cons.h"
41   	#include "scip/pub_heur.h"
42   	#include "scip/pub_message.h"
43   	#include "scip/pub_sol.h"
44   	#include "scip/pub_var.h"
45   	#include "scip/scip_cons.h"
46   	#include "scip/scip_copy.h"
47   	#include "scip/scip_general.h"
48   	#include "scip/scip_heur.h"
49   	#include "scip/scip_lp.h"
50   	#include "scip/scip_mem.h"
51   	#include "scip/scip_message.h"
52   	#include "scip/scip_numerics.h"
53   	#include "scip/scip_param.h"
54   	#include "scip/scip_prob.h"
55   	#include "scip/scip_probing.h"
56   	#include "scip/scip_sol.h"
57   	#include "scip/scip_tree.h"
58   	#include <string.h>
59   	
60   	#define HEUR_NAME             "indicator"
61   	#define HEUR_DESC             "indicator heuristic to create feasible solutions from values for indicator variables"
62   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_LNS
63   	#define HEUR_PRIORITY         -20200
64   	#define HEUR_FREQ             1
65   	#define HEUR_FREQOFS          0
66   	#define HEUR_MAXDEPTH         -1
67   	#define HEUR_TIMING           SCIP_HEURTIMING_DURINGLPLOOP
68   	#define HEUR_USESSUBSCIP      FALSE          /**< does the heuristic use a secondary SCIP instance? */
69   	
70   	#define DEFAULT_ONEOPT        FALSE          /**< whether the one-opt heuristic should be started */
71   	#define DEFAULT_IMPROVESOLS   FALSE          /**< Try to improve other solutions by one-opt? */
72   	
73   	
74   	/** primal heuristic data */
75   	struct SCIP_HeurData
76   	{
77   	   int                   nindconss;          /**< number of indicator constraints */
78   	   SCIP_CONS**           indconss;           /**< indicator constraints */
79   	   SCIP_Bool*            solcand;            /**< bitset of indicator variables in solution candidate */
80   	   SCIP_Real             obj;                /**< objective of previously stored solution */
81   	   SCIP_Bool             oneopt;             /**< whether the one-opt heuristic should be started */
82   	   SCIP_CONSHDLR*        indicatorconshdlr;  /**< indicator constraint handler */
83   	   SCIP_SOL*             lastsol;            /**< last solution considered for improvement */
84   	   SCIP_Bool             improvesols;        /**< Try to improve other solutions by one-opt? */
85   	};
86   	
87   	/*
88   	 * Local methods
89   	 */
90   	
91   	/** try one-opt on given solution */
92   	static
93   	SCIP_RETCODE tryOneOpt(
94   	   SCIP*                 scip,               /**< SCIP data structure */
95   	   SCIP_HEUR*            heur,               /**< indicator heuristic */
96   	   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
97   	   int                   nindconss,          /**< number of indicator constraints */
98   	   SCIP_CONS**           indconss,           /**< indicator constraints */
99   	   SCIP_Bool*            solcand,            /**< values for indicator variables in partial solution */
100  	   int*                  nfoundsols          /**< number of solutions found */
101  	   )
102  	{
103  	   SCIP_Bool cutoff;
104  	   SCIP_Bool lperror;
105  	   SCIP_Bool stored;
106  	   SCIP_SOL* sol;
107  	   int cnt = 0;
108  	   int i;
109  	   int c;
110  	
111  	   assert( scip != NULL );
112  	   assert( heur != NULL );
113  	   assert( heurdata != NULL );
114  	   assert( nindconss == 0 || indconss != NULL );
115  	   assert( solcand != NULL );
116  	   assert( nfoundsols != NULL );
117  	
118  	   SCIPdebugMsg(scip, "Performing one-opt ...\n");
119  	   *nfoundsols = 0;
120  	
121  	   SCIP_CALL( SCIPstartProbing(scip) );
122  	
123  	   for (i = 0; i < nindconss && ! SCIPisStopped(scip); ++i)
124  	   {
125  	      SCIP_VAR* binvar;
126  	
127  	      /* skip nonactive constraints */
128  	      if ( ! SCIPconsIsActive(indconss[i]) )
129  	         continue;
130  	
131  	      binvar = SCIPgetBinaryVarIndicator(indconss[i]);
132  	      assert( binvar != NULL );
133  	
134  	      /* skip constraints with fixed variables */
135  	      if ( SCIPvarGetUbLocal(binvar) < 0.5 || SCIPvarGetLbLocal(binvar) > 0.5 )
136  	         continue;
137  	
138  	      /* return if the we would exceed the depth limit of the tree */
139  	      if( SCIP_MAXTREEDEPTH <= SCIPgetDepth(scip) )
140  	         break;
141  	
142  	      if ( solcand[i] )
143  	         continue;
144  	
145  	      /* get rid of all bound changes */
146  	      SCIP_CALL( SCIPnewProbingNode(scip) );
147  	      ++cnt;
148  	
149  	      /* fix variables */
150  	      for (c = 0; c < nindconss; ++c)
151  	      {
152  	         SCIP_Bool s;
153  	
154  	         /* skip nonactive constraints */
155  	         if ( ! SCIPconsIsActive(indconss[c]) )
156  	            continue;
157  	
158  	         binvar = SCIPgetBinaryVarIndicator(indconss[c]);
159  	         assert( binvar != NULL );
160  	
161  	         /* fix variables according to solution candidate, except constraint i */
162  	         if ( c == i )
163  	            s = ! solcand[c];
164  	         else
165  	            s = solcand[c];
166  	
167  	         if ( ! s )
168  	         {
169  	            if ( SCIPvarGetLbLocal(binvar) < 0.5 && SCIPvarGetUbLocal(binvar) > 0.5 )
170  	            {
171  	               SCIP_CALL( SCIPchgVarLbProbing(scip, binvar, 1.0) );
172  	            }
173  	         }
174  	         else
175  	         {
176  	            if ( SCIPvarGetUbLocal(binvar) > 0.5 && SCIPvarGetLbLocal(binvar) < 0.5 )
177  	            {
178  	               SCIP_CALL( SCIPchgVarUbProbing(scip, binvar, 0.0) );
179  	            }
180  	         }
181  	      }
182  	
183  	      /* propagate variables */
184  	      SCIP_CALL( SCIPpropagateProbing(scip, -1, &cutoff, NULL) );
185  	      if ( cutoff )
186  	      {
187  	         SCIP_CALL( SCIPbacktrackProbing(scip, 0) );
188  	         continue;
189  	      }
190  	
191  	      /* solve LP to move continuous variables */
192  	      SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, &cutoff) );
193  	
194  	      /* the LP often reaches the objective limit - we currently do not use such solutions */
195  	      if ( lperror || cutoff || SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
196  	      {
197  	#ifdef SCIP_DEBUG
198  	         if ( lperror )
199  	            SCIPdebugMsg(scip, "An LP error occurred.\n");
200  	#endif
201  	         SCIP_CALL( SCIPbacktrackProbing(scip, 0) );
202  	         continue;
203  	      }
204  	
205  	      /* create solution */
206  	      SCIP_CALL( SCIPcreateSol(scip, &sol, heur) );
207  	
208  	      /* copy the current LP solution to the working solution */
209  	      SCIP_CALL( SCIPlinkLPSol(scip, sol) );
210  	
211  	      /* check solution for feasibility */
212  	      SCIPdebugMsg(scip, "One-opt found solution candidate with value %g.\n", SCIPgetSolTransObj(scip, sol));
213  	
214  	      /* only check integrality, because we solved an LP */
215  	      SCIP_CALL( SCIPtrySolFree(scip, &sol, FALSE, FALSE, FALSE, TRUE, FALSE, &stored) );
216  	      if ( stored )
217  	         ++(*nfoundsols);
218  	      SCIP_CALL( SCIPbacktrackProbing(scip, 0) );
219  	   }
220  	   SCIP_CALL( SCIPendProbing(scip) );
221  	
222  	   SCIPdebugMsg(scip, "Finished one-opt (tried variables: %d, found sols: %d).\n", cnt, *nfoundsols);
223  	
224  	   return SCIP_OKAY;
225  	}
226  	
227  	
228  	/** try given solution */
229  	static
230  	SCIP_RETCODE trySolCandidate(
231  	   SCIP*                 scip,               /**< SCIP data structure */
232  	   SCIP_HEUR*            heur,               /**< indicator heuristic */
233  	   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
234  	   int                   nindconss,          /**< number of indicator constraints */
235  	   SCIP_CONS**           indconss,           /**< indicator constraints */
236  	   SCIP_Bool*            solcand,            /**< values for indicator variables in partial solution */
237  	   int*                  nfoundsols          /**< number of solutions found */
238  	   )
239  	{
240  	   SCIP_Bool cutoff;
241  	   SCIP_Bool lperror;
242  	   SCIP_Bool stored;
243  	   SCIP_SOL* sol;
244  	   int c;
245  	
246  	   assert( scip != NULL );
247  	   assert( heur != NULL );
248  	   assert( heurdata != NULL );
249  	   assert( nindconss == 0 || indconss != NULL );
250  	   assert( solcand != NULL );
251  	   assert( nfoundsols != NULL );
252  	
253  	   SCIPdebugMsg(scip, "Trying to generate feasible solution with indicators from solution candidate (obj: %f) ...\n", heurdata->obj);
254  	   *nfoundsols = 0;
255  	
256  	   SCIP_CALL( SCIPstartProbing(scip) );
257  	
258  	   /* we can stop here if we have already reached the maximal depth */
259  	   if( SCIP_MAXTREEDEPTH <= SCIPgetDepth(scip) )
260  	   {
261  	      SCIP_CALL( SCIPendProbing(scip) );
262  	      return SCIP_OKAY;
263  	   }
264  	
265  	   SCIP_CALL( SCIPnewProbingNode(scip) );
266  	
267  	   /* fix variables */
268  	   for (c = 0; c < nindconss; ++c)
269  	   {
270  	      SCIP_VAR* binvar;
271  	
272  	      /* skip nonactive constraints */
273  	      if ( ! SCIPconsIsActive(indconss[c]) )
274  	         continue;
275  	
276  	      binvar = SCIPgetBinaryVarIndicator(indconss[c]);
277  	      assert( binvar != NULL );
278  	
279  	      /* Fix binary variables not in cover to 1 and corresponding slack variables to 0. The other binary variables are fixed to 0. */
280  	      if ( ! solcand[c] )
281  	      {
282  	         /* to be sure, check for non-fixed variables */
283  	         if ( SCIPvarGetLbLocal(binvar) < 0.5 && SCIPvarGetUbLocal(binvar) > 0.5 )
284  	         {
285  	            SCIP_CALL( SCIPchgVarLbProbing(scip, binvar, 1.0) );
286  	         }
287  	      }
288  	      else
289  	      {
290  	         if ( SCIPvarGetUbLocal(binvar) > 0.5 && SCIPvarGetLbLocal(binvar) < 0.5 )
291  	         {
292  	            SCIP_CALL( SCIPchgVarUbProbing(scip, binvar, 0.0) );
293  	         }
294  	      }
295  	   }
296  	
297  	   /* propagate variables */
298  	   SCIP_CALL( SCIPpropagateProbing(scip, -1, &cutoff, NULL) );
299  	   if ( cutoff )
300  	   {
301  	      SCIPdebugMsg(scip, "Solution candidate reaches cutoff (in propagation).\n");
302  	      SCIP_CALL( SCIPendProbing(scip) );
303  	      return SCIP_OKAY;
304  	   }
305  	
306  	   /* solve LP to move continuous variables */
307  	   SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, &cutoff) );
308  	
309  	   /* the LP often reaches the objective limit - we currently do not use such solutions */
310  	   if ( lperror || cutoff || SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
311  	   {
312  	#ifdef SCIP_DEBUG
313  	      if ( lperror )
314  	      {
315  	         SCIPdebugMsg(scip, "An LP error occurred.\n");
316  	      }
317  	      else
318  	      {
319  	         SCIPdebugMsg(scip, "Solution candidate reaches cutoff (in LP solving).\n");
320  	      }
321  	#endif
322  	      SCIP_CALL( SCIPendProbing(scip) );
323  	      return SCIP_OKAY;
324  	   }
325  	
326  	   /* create solution */
327  	   SCIP_CALL( SCIPcreateSol(scip, &sol, heur) );
328  	
329  	   /* copy the current LP solution to the working solution */
330  	   SCIP_CALL( SCIPlinkLPSol(scip, sol) );
331  	
332  	   /* check solution for feasibility */
333  	#ifdef SCIP_DEBUG
334  	   SCIPdebugMsg(scip, "Found solution candidate with value %g.\n", SCIPgetSolTransObj(scip, sol));
335  	#ifdef SCIP_MORE_DEBUG
336  	   SCIP_CALL( SCIPprintSol(scip, sol, NULL, FALSE) );
337  	#endif
338  	   SCIP_CALL( SCIPtrySolFree(scip, &sol, TRUE, TRUE, TRUE, TRUE, TRUE, &stored) );
339  	   if ( stored )
340  	   {
341  	      ++(*nfoundsols);
342  	      SCIPdebugMsg(scip, "Solution is feasible and stored.\n");
343  	   }
344  	   else
345  	      SCIPdebugMsg(scip, "Solution was not stored.\n");
346  	#else
347  	   /* only check integrality, because we solved an LP */
348  	   SCIP_CALL( SCIPtrySolFree(scip, &sol, FALSE, FALSE, FALSE, TRUE, FALSE, &stored) );
349  	   if ( stored )
350  	      ++(*nfoundsols);
351  	#endif
352  	   SCIP_CALL( SCIPendProbing(scip) );
353  	
354  	   /* possibly perform one-opt */
355  	   if ( stored && heurdata->oneopt )
356  	   {
357  	      int nfound = 0;
358  	      assert( *nfoundsols > 0 );
359  	      SCIP_CALL( tryOneOpt(scip, heur, heurdata, nindconss, indconss, solcand, &nfound) );
360  	   }
361  	
362  	   return SCIP_OKAY;
363  	}
364  	
365  	
366  	/*
367  	 * Callback methods of primal heuristic
368  	 */
369  	
370  	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
371  	static
372  	SCIP_DECL_HEURCOPY(heurCopyIndicator)
373  	{  /*lint --e{715}*/
374  	   assert( scip != NULL );
375  	   assert( heur != NULL );
376  	   assert( strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0 );
377  	
378  	   /* call inclusion method of primal heuristic */
379  	   SCIP_CALL( SCIPincludeHeurIndicator(scip) );
380  	
381  	   return SCIP_OKAY;
382  	}
383  	
384  	/** initialization method of primal heuristic (called after problem was transformed) */
385  	static
386  	SCIP_DECL_HEURINIT(heurInitIndicator)
387  	{  /*lint --e{715}*/
388  	   SCIP_HEURDATA* heurdata;
389  	
390  	   assert( heur != NULL );
391  	   assert( scip != NULL );
392  	
393  	   /* get heuristic data */
394  	   heurdata = SCIPheurGetData(heur);
395  	   assert( heurdata != NULL );
396  	
397  	   if ( heurdata->indicatorconshdlr == NULL )
398  	   {
399  	      heurdata->indicatorconshdlr = SCIPfindConshdlr(scip, "indicator");
400  	      if ( heurdata->indicatorconshdlr == NULL )
401  	      {
402  	         SCIPwarningMessage(scip, "Could not find indicator constraint handler.\n");
403  	      }
404  	   }
405  	
406  	   return SCIP_OKAY;
407  	}
408  	
409  	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
410  	static
411  	SCIP_DECL_HEURFREE(heurFreeIndicator)
412  	{  /*lint --e{715}*/
413  	   SCIP_HEURDATA* heurdata;
414  	
415  	   assert( heur != NULL );
416  	   assert( scip != NULL );
417  	
418  	   /* get heuristic data */
419  	   heurdata = SCIPheurGetData(heur);
420  	   assert( heurdata != NULL );
421  	
422  	   SCIPfreeBlockMemoryArrayNull(scip, &(heurdata->indconss), heurdata->nindconss);
423  	   SCIPfreeBlockMemoryArrayNull(scip, &(heurdata->solcand), heurdata->nindconss);
424  	
425  	   /* free heuristic data */
426  	   SCIPfreeBlockMemory(scip, &heurdata);
427  	   SCIPheurSetData(heur, NULL);
428  	
429  	   return SCIP_OKAY;
430  	}
431  	
432  	
433  	/** execution method of primal heuristic */
434  	static
435  	SCIP_DECL_HEUREXEC(heurExecIndicator)
436  	{  /*lint --e{715}*/
437  	   SCIP_HEURDATA* heurdata;
438  	   int nfoundsols = 0;
439  	
440  	   assert( heur != NULL );
441  	   assert( scip != NULL );
442  	   assert( result != NULL );
443  	
444  	   *result = SCIP_DIDNOTRUN;
445  	
446  	   if ( SCIPgetSubscipDepth(scip) > 0 )
447  	      return SCIP_OKAY;
448  	
449  	   /* get heuristic's data */
450  	   heurdata = SCIPheurGetData(heur);
451  	   assert( heurdata != NULL );
452  	
453  	   /* call heuristic, if solution candidate is available */
454  	   if ( heurdata->solcand != NULL )
455  	   {
456  	      assert( heurdata->nindconss > 0 );
457  	      assert( heurdata->indconss != NULL );
458  	
459  	      /* The heuristic will only be successful if there are no integral variables and no binary variables except the
460  	       * indicator variables. */
461  	      if ( SCIPgetNIntVars(scip) > 0 || heurdata->nindconss < SCIPgetNBinVars(scip) )
462  	         return SCIP_OKAY;
463  	
464  	      SCIP_CALL( trySolCandidate(scip, heur, heurdata, heurdata->nindconss, heurdata->indconss, heurdata->solcand, &nfoundsols) );
465  	
466  	      if ( nfoundsols > 0 )
467  	         *result = SCIP_FOUNDSOL;
468  	      else
469  	         *result = SCIP_DIDNOTFIND;
470  	
471  	      /* free memory */
472  	      SCIPfreeBlockMemoryArray(scip, &(heurdata->solcand), heurdata->nindconss);
473  	      SCIPfreeBlockMemoryArray(scip, &(heurdata->indconss), heurdata->nindconss);
474  	   }
475  	
476  	   /* try to improve solutions generated by other heuristics */
477  	   if ( heurdata->improvesols )
478  	   {
479  	      SCIP_CONS** indconss;
480  	      SCIP_Bool* solcand;
481  	      SCIP_SOL* bestsol;
482  	      int nindconss;
483  	      int i;
484  	
485  	      if ( heurdata->indicatorconshdlr == NULL )
486  	         return SCIP_OKAY;
487  	
488  	      /* check whether a new best solution has been found */
489  	      bestsol = SCIPgetBestSol(scip);
490  	      if ( bestsol == heurdata->lastsol )
491  	         return SCIP_OKAY;
492  	      heurdata->lastsol = bestsol;
493  	
494  	      /* avoid solutions produced by this heuristic */
495  	      if ( SCIPsolGetHeur(bestsol) == heur )
496  	         return SCIP_OKAY;
497  	
498  	      /* The heuristic will only be successful if there are no integral variables and no binary variables except the
499  	       * indicator variables. */
500  	      nindconss = SCIPconshdlrGetNConss(heurdata->indicatorconshdlr);
501  	      if ( SCIPgetNIntVars(scip) > 0 || nindconss < SCIPgetNBinVars(scip) )
502  	         return SCIP_OKAY;
503  	
504  	      if ( nindconss == 0 )
505  	         return SCIP_OKAY;
506  	
507  	      indconss = SCIPconshdlrGetConss(heurdata->indicatorconshdlr);
508  	      assert( indconss != NULL );
509  	
510  	      /* fill solution candidate */
511  	      SCIP_CALL( SCIPallocBufferArray(scip, &solcand, nindconss) );
512  	      for (i = 0; i < nindconss; ++i)
513  	      {
514  	         SCIP_VAR* binvar;
515  	         SCIP_Real val;
516  	
517  	         solcand[i] = FALSE;
518  	         if ( SCIPconsIsActive(indconss[i]) )
519  	         {
520  	            binvar = SCIPgetBinaryVarIndicator(indconss[i]);
521  	            assert( binvar != NULL );
522  	
523  	            val = SCIPgetSolVal(scip, bestsol, binvar);
524  	            assert( SCIPisFeasIntegral(scip, val) );
525  	            if ( val > 0.5 )
526  	               solcand[i] = TRUE;
527  	         }
528  	      }
529  	
530  	      SCIPdebugMsg(scip, "Trying to improve best solution of value %f.\n", SCIPgetSolOrigObj(scip, bestsol) );
531  	
532  	      /* try one-opt heuristic */
533  	      SCIP_CALL( tryOneOpt(scip, heur, heurdata, nindconss, indconss, solcand, &nfoundsols) );
534  	
535  	      if ( nfoundsols > 0 )
536  	         *result = SCIP_FOUNDSOL;
537  	      else
538  	         *result = SCIP_DIDNOTFIND;
539  	
540  	      SCIPfreeBufferArray(scip, &solcand);
541  	   }
542  	
543  	   return SCIP_OKAY;
544  	}
545  	
546  	
547  	/*
548  	 * primal heuristic specific interface methods
549  	 */
550  	
551  	/** creates the indicator primal heuristic and includes it in SCIP */
552  	SCIP_RETCODE SCIPincludeHeurIndicator(
553  	   SCIP*                 scip                /**< SCIP data structure */
554  	   )
555  	{
556  	   SCIP_HEURDATA* heurdata;
557  	   SCIP_HEUR* heur;
558  	
559  	   /* create Indicator primal heuristic data */
560  	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
561  	   heurdata->nindconss = 0;
562  	   heurdata->indconss = NULL;
563  	   heurdata->solcand = NULL;
564  	   heurdata->lastsol = NULL;
565  	   heurdata->indicatorconshdlr = NULL;
566  	   heurdata->obj = SCIPinfinity(scip);
567  	
568  	   /* include primal heuristic */
569  	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
570  	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
571  	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecIndicator, heurdata) );
572  	
573  	   assert( heur != NULL );
574  	
575  	   /* set non-NULL pointers to callback methods */
576  	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyIndicator) );
577  	   SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitIndicator) );
578  	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeIndicator) );
579  	
580  	   /* add parameters */
581  	   SCIP_CALL( SCIPaddBoolParam(scip,
582  	         "heuristics/" HEUR_NAME "/oneopt",
583  	         "whether the one-opt heuristic should be started",
584  	         &heurdata->oneopt, TRUE, DEFAULT_ONEOPT, NULL, NULL) );
585  	
586  	   SCIP_CALL( SCIPaddBoolParam(scip,
587  	         "heuristics/" HEUR_NAME "/improvesols",
588  	         "Try to improve other solutions by one-opt?",
589  	         &heurdata->improvesols, TRUE, DEFAULT_IMPROVESOLS, NULL, NULL) );
590  	
591  	   return SCIP_OKAY;
592  	}
593  	
594  	
595  	/** pass partial solution for indicator variables to heuristic */
596  	SCIP_RETCODE SCIPheurPassIndicator(
597  	   SCIP*                 scip,               /**< SCIP data structure */
598  	   SCIP_HEUR*            heur,               /**< indicator heuristic */
599  	   int                   nindconss,          /**< number of indicator constraints */
600  	   SCIP_CONS**           indconss,           /**< indicator constraints */
601  	   SCIP_Bool*            solcand,            /**< values for indicator variables in partial solution */
602  	   SCIP_Real             obj                 /**< objective of solution */
603  	   )
604  	{
605  	   SCIP_HEURDATA* heurdata;
606  	
607  	   assert( scip != NULL );
608  	   assert( heur != NULL );
609  	   assert( strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0 );
610  	   assert( nindconss > 0 );
611  	   assert( indconss != NULL );
612  	   assert( solcand != NULL );
613  	
614  	   /* get heuristic's data */
615  	   heurdata = SCIPheurGetData(heur);
616  	   assert( heurdata != NULL );
617  	
618  	   if ( obj >= heurdata->obj )
619  	      return SCIP_OKAY;
620  	
621  	   /* copy indicator information */
622  	   if ( heurdata->indconss != NULL )
623  	      SCIPfreeBlockMemoryArray(scip, &(heurdata->indconss), heurdata->nindconss);
624  	
625  	   SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(heurdata->indconss), indconss, nindconss) );
626  	   heurdata->nindconss = nindconss;
627  	
628  	   /* copy partial solution */
629  	   if ( heurdata->solcand != NULL )
630  	      BMScopyMemoryArray(heurdata->solcand, solcand, nindconss);
631  	   else
632  	      SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(heurdata->solcand), solcand, nindconss) );
633  	   heurdata->obj = obj;
634  	
635  	   return SCIP_OKAY;
636  	}
637