Scippy

SCIP

Solving Constraint Integer Programs

cons_lop.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-2018 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /* uncomment for debug output: */
17 /* #define SCIP_DEBUG */
18 
19 /**@file cons_lop.c
20  * @brief example constraint handler for linear ordering constraints
21  * @author Marc Pfetsch
22  *
23  * We handle the following system of linear constraints:
24  * - \f$ x_{ij} + x_{ji} = 1 \f$ (symmetry equations - added initially)
25  * \f$ x_{ij} + x_{jk} + x_{ki} \leq 2 \f$ (triangle inequalities)
26  */
27 
28 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
29 
30 #include "cons_lop.h"
31 
32 #include <assert.h>
33 #include <string.h>
34 
35 
36 /* constraint handler properties */
37 #define CONSHDLR_NAME "lop"
38 #define CONSHDLR_DESC "linear ordering constraint handler"
39 #define CONSHDLR_SEPAPRIORITY 100 /**< priority of the constraint handler for separation */
40 #define CONSHDLR_ENFOPRIORITY -100 /**< priority of the constraint handler for constraint enforcing */
41 #define CONSHDLR_CHECKPRIORITY -100 /**< priority of the constraint handler for checking feasibility */
42 #define CONSHDLR_SEPAFREQ 10 /**< frequency for separating cuts; zero means to separate only in the root node */
43 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
44 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
45  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
46 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
47 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
48 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
49 
50 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
51 
52 
53 /** constraint data for linear ordering constraints */
54 struct SCIP_ConsData
55 {
56  int n; /**< number of elements */
57  SCIP_VAR*** vars; /**< variables */
58 };
59 
60 
61 /** separate symmetry equations and triangle inequalities */
62 static
64  SCIP* scip, /**< SCIP pointer */
65  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
66  int n, /**< number of elements */
67  SCIP_VAR*** vars, /**< n x n matrix of variables */
68  SCIP_SOL* sol, /**< solution to be separated */
69  int* nGen, /**< output: pointer to store number of added rows */
70  SCIP_Bool* cutoff /**< output: pointer to store whether we detected a cutoff */
71  )
72 {
73  char s[SCIP_MAXSTRLEN];
74  int i;
75  int j;
76  int k;
77 
78  assert( scip != NULL );
79  assert( vars != NULL );
80  assert( nGen != NULL );
81  assert( cutoff != NULL );
82 
83  *cutoff = FALSE;
84  for (i = 0; i < n && ! (*cutoff); ++i)
85  {
86  for (j = 0; j < n && ! (*cutoff); ++j)
87  {
88  SCIP_Real valIJ;
89  if (j == i)
90  continue;
91 
92  valIJ = SCIPgetSolVal(scip, sol, vars[i][j]);
93 
94  /* if symmetry equations are violated - should not be the case, if they are added in the beginning */
95  if ( ! SCIPisFeasEQ(scip, valIJ + SCIPgetSolVal(scip, sol, vars[j][i]), 1.0) )
96  {
97  SCIP_ROW *row;
98 
99  (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "sym#%d#%d", i, j);
100 
101  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, conshdlr, s, 1.0, 1.0, FALSE, FALSE, TRUE) );
102  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
103  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[i][j], 1.0) );
104  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[j][i], 1.0) );
105  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
106 #ifdef SCIP_DEBUG
107  SCIPdebug( SCIPprintRow(scip, row, NULL) );
108 #endif
109  SCIP_CALL( SCIPaddRow(scip, row, FALSE, cutoff) );
110  SCIP_CALL( SCIPreleaseRow(scip, &row));
111  ++(*nGen);
112 
113  if ( *cutoff )
114  break;
115  }
116 
117  /* check triangle inequalities */
118  for (k = 0; k < n; ++k)
119  {
120  SCIP_Real sum;
121 
122  if (k == i || k == j)
123  continue;
124 
125  sum = valIJ + SCIPgetSolVal(scip, sol, vars[j][k]) + SCIPgetSolVal(scip, sol, vars[k][i]);
126 
127  /* if sum - 2.0 > 0, i.e., the cut is violated */
128  if ( SCIPisEfficacious(scip, sum - 2.0) )
129  {
130  SCIP_ROW *row;
131 
132  (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "triangle#%d#%d#%d", i, j, k);
133 
134  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, conshdlr, s, -SCIPinfinity(scip), 2.0, FALSE, FALSE, TRUE) );
135  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
136  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[i][j], 1.0) );
137  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[j][k], 1.0) );
138  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[k][i], 1.0) );
139  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
140 #ifdef SCIP_DEBUG
141  SCIPdebug( SCIPprintRow(scip, row, NULL) );
142 #endif
143  SCIP_CALL( SCIPaddRow(scip, row, FALSE, cutoff) );
144  SCIP_CALL( SCIPreleaseRow(scip, &row));
145  ++(*nGen);
146 
147  if ( *cutoff )
148  break;
149  }
150  }
151  }
152  }
153 
154  return SCIP_OKAY;
155 }
156 
157 
158 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
159 static
160 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyLOP)
161 { /*lint --e{715}*/
162  assert( scip != NULL );
163  assert( conshdlr != NULL );
164  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
165  assert( valid != NULL );
166 
167  /* call inclusion method of constraint handler */
169 
170  *valid = TRUE;
171 
172  return SCIP_OKAY;
173 }
174 
175 /** frees specific constraint data */
176 static
177 SCIP_DECL_CONSDELETE(consDeleteLOP)
178 { /*lint --e{715}*/
179  int i;
180  int n;
181 
182  assert( scip != NULL );
183  assert( conshdlr != NULL );
184  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
185  assert( cons != NULL );
186  assert( consdata != NULL);
187  assert( *consdata != NULL);
188  assert( (*consdata)->vars != NULL );
189 
190  SCIPdebugMsg(scip, "deleting linear ordering constraint <%s>.\n", SCIPconsGetName(cons));
191 
192  n = (*consdata)->n;
193  for (i = 0; i < n; ++i)
194  SCIPfreeBlockMemoryArray(scip, &((*consdata)->vars[i]), n); /*lint !e866*/
195  SCIPfreeBlockMemoryArray(scip, &((*consdata)->vars), n);
196  SCIPfreeBlockMemory(scip, consdata);
197 
198  return SCIP_OKAY;
199 }
200 
201 /** deinitialization method of constraint handler (called before transformed problem is freed)
202  *
203  * We output the final linear ordering.
204  */
205 static
206 SCIP_DECL_CONSEXIT(consExitLOP)
207 { /*lint --e{715}*/
208  SCIP_SOL* sol;
209  int c;
210  int i;
211  int j;
212  int n;
213 
214  assert( scip != NULL );
215  assert( conshdlr != NULL );
216  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
217 
218  SCIPdebugMsg(scip, "exiting linear ordering constraint handler <%s>.\n", SCIPconshdlrGetName(conshdlr));
219 
220  /* avoid output for subscips */
221  if ( SCIPgetSubscipDepth(scip) > 0 )
222  return SCIP_OKAY;
223 
224  /* get best solution */
225  sol = SCIPgetBestSol(scip);
226  if ( sol == NULL )
227  return SCIP_OKAY;
228 
229  /* loop through all constraints */
230  for (c = 0; c < nconss; ++c)
231  {
232  SCIP_CONSDATA* consdata;
233  SCIP_VAR*** vars;
234  int* outdeg;
235  int* indices;
236 
237  assert( conss != NULL );
238  assert( conss[c] != NULL );
239  SCIPdebugMsg(scip, "solution for for linear ordering constraint <%s>.\n", SCIPconsGetName(conss[c]));
240 
241  consdata = SCIPconsGetData(conss[c]);
242  assert( consdata != NULL );
243  assert( consdata->vars != NULL );
244  n = consdata->n;
245  vars = consdata->vars;
246 
247  SCIP_CALL( SCIPallocBufferArray(scip, &outdeg, n) );
248  SCIP_CALL( SCIPallocBufferArray(scip, &indices, n) );
249 
250  /* compute out-degree */
251  for (i = 0; i < n; ++i)
252  {
253  int deg = 0;
254  for (j = 0; j < n; ++j)
255  {
256  SCIP_Real val;
257 
258  if (j == i)
259  continue;
260 
261  val = SCIPgetSolVal(scip, sol, vars[i][j]);
262  assert( SCIPisFeasIntegral(scip, val) );
263  if ( val < 0.5 )
264  ++deg;
265  }
266  outdeg[i] = deg;
267  indices[i] = i;
268  }
269 
270  /* sort such that degrees are non-decreasing */
271  SCIPsortIntInt(outdeg, indices, n);
272 
273  /* output */
274  SCIPinfoMessage(scip, NULL, "\nFinal order of linear ordering constraint <%s>:\n", SCIPconsGetName(conss[c]));
275  for (i = 0; i < n; ++i)
276  SCIPinfoMessage(scip, NULL, "%d ", indices[i]);
277  SCIPinfoMessage(scip, NULL, "\n");
278 
279  SCIPfreeBufferArray(scip, &indices);
280  SCIPfreeBufferArray(scip, &outdeg);
281  }
282 
283  return SCIP_OKAY;
284 }
285 
286 /** transforms constraint data into data belonging to the transformed problem */
287 static
288 SCIP_DECL_CONSTRANS(consTransLOP)
289 { /*lint --e{715}*/
290  SCIP_CONSDATA* consdata;
291  SCIP_CONSDATA* sourcedata;
292  int i;
293  int j;
294  int n;
295  char s[SCIP_MAXSTRLEN];
296 
297  assert( scip != NULL );
298  assert( conshdlr != NULL );
299  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
300  assert( sourcecons != NULL );
301  assert( targetcons != NULL );
302 
303  SCIPdebugMsg(scip, "transforming linear ordering constraint <%s>.\n", SCIPconsGetName(sourcecons) );
304 
305  /* get data of original constraint */
306  sourcedata = SCIPconsGetData(sourcecons);
307  assert( sourcedata != NULL);
308 
309  /* create constraint data */
310  SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
311 
312  n = sourcedata->n;
313  consdata->n = n;
314 
315  /* transform variables */
316  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->vars, n) );
317  for (i = 0; i < n; ++i)
318  {
319  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->vars[i]), n) ); /*lint !e866*/
320  for (j = 0; j < n; ++j)
321  {
322  if (j != i)
323  {
324  assert( sourcedata->vars[i][j] != NULL );
325  SCIP_CALL( SCIPgetTransformedVar(scip, sourcedata->vars[i][j], &(consdata->vars[i][j])) );
326  }
327  }
328  }
329 
330  /* create constraint */
331  (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "t_%s", SCIPconsGetName(sourcecons));
332 
333  SCIP_CALL( SCIPcreateCons(scip, targetcons, s, conshdlr, consdata,
334  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons),
335  SCIPconsIsEnforced(sourcecons), SCIPconsIsChecked(sourcecons),
336  SCIPconsIsPropagated(sourcecons), SCIPconsIsLocal(sourcecons),
337  SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons),
338  SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
339 
340  return SCIP_OKAY;
341 }
342 
343 /** LP initialization method of constraint handler */
344 static
345 SCIP_DECL_CONSINITLP(consInitlpLOP)
346 { /*lint --e{715}*/
347  char s[SCIP_MAXSTRLEN];
348  int c;
349  int nGen = 0;
350 
351  assert( scip != NULL );
352  assert( conshdlr != NULL );
353  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
354  assert( infeasible != NULL );
355 
356  *infeasible = FALSE;
357 
358  /* loop through all constraints */
359  for (c = 0; c < nconss; ++c)
360  {
361  SCIP_CONSDATA* consdata;
362  int i, j, n;
363  SCIP_VAR*** vars;
364 
365  assert( conss != NULL );
366  assert( conss[c] != NULL );
367  SCIPdebugMsg(scip, "adding initial rows for linear ordering constraint <%s>.\n", SCIPconsGetName(conss[c]));
368 
369  consdata = SCIPconsGetData(conss[c]);
370  assert( consdata != NULL );
371  assert( consdata->vars != NULL );
372  n = consdata->n;
373  vars = consdata->vars;
374 
375  /* add symmetry equation */
376  for (i = 0; i < n; ++i)
377  {
378  for (j = i+1; j < n; ++j)
379  {
380  SCIP_ROW* row;
381 
382  (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "sym#%d#%d", i, j);
383  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, conshdlr, s, 1.0, 1.0, FALSE, FALSE, FALSE) );
384  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
385  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[i][j], 1.0) );
386  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[j][i], 1.0) );
387  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
388 #ifdef SCIP_DEBUG
389  SCIPdebug( SCIPprintRow(scip, row, NULL) );
390 #endif
391  SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
392  SCIP_CALL( SCIPreleaseRow(scip, &row));
393  ++nGen;
394 
395  /* cannot handle infeasible case here - just exit */
396  if ( *infeasible )
397  return SCIP_OKAY;
398  }
399  }
400  }
401  SCIPdebugMsg(scip, "added %d equations.\n", nGen);
402 
403  return SCIP_OKAY;
404 }
405 
406 /** separation method of constraint handler for LP solutions */
407 static
408 SCIP_DECL_CONSSEPALP(consSepalpLOP)
409 { /*lint --e{715}*/
410  int nGen = 0;
411  int c;
412 
413  assert( scip != NULL );
414  assert( conshdlr != NULL );
415  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
416  assert( conss != NULL );
417  assert( result != NULL );
418 
419  *result = SCIP_DIDNOTRUN;
420 
421  /* loop through all constraints */
422  for (c = 0; c < nconss; ++c)
423  {
424  SCIP_CONSDATA* consdata;
425  SCIP_CONS* cons;
426  SCIP_Bool cutoff;
427 
428  cons = conss[c];
429  assert( cons != NULL );
430  SCIPdebugMsg(scip, "separating LP solution for linear ordering constraint <%s>.\n", SCIPconsGetName(cons));
431 
432  consdata = SCIPconsGetData(cons);
433  assert( consdata != NULL );
434 
435  *result = SCIP_DIDNOTFIND;
436  SCIP_CALL( LOPseparate(scip, conshdlr, consdata->n, consdata->vars, NULL, &nGen, &cutoff) );
437  if ( cutoff )
438  {
439  *result = SCIP_CUTOFF;
440  return SCIP_OKAY;
441  }
442  }
443  if (nGen > 0)
444  *result = SCIP_SEPARATED;
445  SCIPdebugMsg(scip, "separated %d cuts.\n", nGen);
446 
447  return SCIP_OKAY;
448 }
449 
450 /** separation method of constraint handler for arbitrary primal solutions */
451 static
452 SCIP_DECL_CONSSEPASOL(consSepasolLOP)
453 { /*lint --e{715}*/
454  int nGen = 0;
455  int c;
456 
457  assert( scip != NULL );
458  assert( conshdlr != NULL );
459  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
460  assert( conss != NULL );
461  assert( result != NULL );
462 
463  *result = SCIP_DIDNOTRUN;
464 
465  /* loop through all constraints */
466  for (c = 0; c < nconss; ++c)
467  {
468  SCIP_CONSDATA* consdata;
469  SCIP_CONS* cons;
470  SCIP_Bool cutoff;
471 
472  cons = conss[c];
473  assert( cons != NULL );
474  SCIPdebugMsg(scip, "separating solution for linear ordering constraint <%s>.\n", SCIPconsGetName(cons));
475 
476  consdata = SCIPconsGetData(cons);
477  assert( consdata != NULL );
478 
479  *result = SCIP_DIDNOTFIND;
480  SCIP_CALL( LOPseparate(scip, conshdlr, consdata->n, consdata->vars, sol, &nGen, &cutoff) );
481  if ( cutoff )
482  {
483  *result = SCIP_CUTOFF;
484  return SCIP_OKAY;
485  }
486  }
487  if (nGen > 0)
488  *result = SCIP_SEPARATED;
489 
490  return SCIP_OKAY;
491 }
492 
493 /** constraint enforcing method of constraint handler for LP solutions */
494 static
495 SCIP_DECL_CONSENFOLP(consEnfolpLOP)
496 { /*lint --e{715}*/
497  char s[SCIP_MAXSTRLEN];
498  int nGen = 0;
499  int c;
500 
501  assert( scip != NULL );
502  assert( conshdlr != NULL );
503  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
504  assert( conss != NULL );
505  assert( result != NULL );
506 
507  *result = SCIP_DIDNOTRUN;
508 
509  /* loop through all constraints */
510  for (c = 0; c < nconss; ++c)
511  {
512  SCIP_CONSDATA* consdata;
513  SCIP_CONS* cons;
514  SCIP_VAR*** vars;
515  int i;
516  int j;
517  int k;
518  int n;
519 
520  cons = conss[c];
521  assert( cons != NULL );
522  SCIPdebugMsg(scip, "enforcing lp solution for linear ordering constraint <%s>.\n", SCIPconsGetName(cons));
523 
524  consdata = SCIPconsGetData(cons);
525  assert( consdata != NULL );
526 
527  n = consdata->n;
528  vars = consdata->vars;
529  assert( vars != NULL );
530 
531  for (i = 0; i < n; ++i)
532  {
533  for (j = 0; j < n; ++j)
534  {
535  SCIP_Real valIJ;
536  if (j == i)
537  continue;
538 
539  valIJ = SCIPgetSolVal(scip, NULL, vars[i][j]);
540 
541  /* if symmetry equations are violated - should not be the case, if they are added in the beginning */
542  if ( ! SCIPisFeasEQ(scip, 1.0 - valIJ, SCIPgetSolVal(scip, NULL, vars[j][i])) )
543  {
544  SCIP_ROW *row;
545  SCIP_Bool infeasible;
546 
547  (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "sym#%d#%d", i, j);
548 
549  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, conshdlr, s, 1.0, 1.0, FALSE, FALSE, TRUE) );
550  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
551  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[i][j], 1.0) );
552  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[j][i], 1.0) );
553  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
554 #ifdef SCIP_DEBUG
555  SCIPdebug( SCIPprintRow(scip, row, NULL) );
556 #endif
557  SCIP_CALL( SCIPaddRow(scip, row, FALSE, &infeasible) );
558  SCIP_CALL( SCIPreleaseRow(scip, &row));
559  ++nGen;
560 
561  if ( infeasible )
562  {
563  *result = SCIP_CUTOFF;
564  return SCIP_OKAY;
565  }
566  }
567 
568  /* enforce triangle inequalities */
569  for (k = 0; k < n; ++k)
570  {
571  SCIP_Real sum;
572 
573  if (k == i || k == j)
574  continue;
575 
576  sum = valIJ + SCIPgetSolVal(scip, NULL, vars[j][k]) + SCIPgetSolVal(scip, NULL, vars[k][i]);
577 
578  /* if sum > 2.0, i.e., the cut is violated */
579  if ( SCIPisFeasGT(scip, sum, 2.0) ) /* this is the only difference to the separation call */
580  {
581  SCIP_ROW *row;
582  SCIP_Bool infeasible;
583 
584  (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "triangle#%d#%d#%d", i, j, k);
585 
586  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, conshdlr, s, -SCIPinfinity(scip), 2.0, FALSE, FALSE, TRUE) );
587  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
588  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[i][j], 1.0) );
589  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[j][k], 1.0) );
590  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[k][i], 1.0) );
591  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
592 #ifdef SCIP_DEBUG
593  SCIPdebug( SCIPprintRow(scip, row, NULL) );
594 #endif
595  SCIP_CALL( SCIPaddRow(scip, row, FALSE, &infeasible) );
596  SCIP_CALL( SCIPreleaseRow(scip, &row));
597  ++nGen;
598 
599  if ( infeasible )
600  {
601  *result = SCIP_CUTOFF;
602  return SCIP_OKAY;
603  }
604  }
605  }
606  }
607  }
608  if (nGen > 0)
609  {
610  *result = SCIP_SEPARATED;
611  return SCIP_OKAY;
612  }
613  }
614  SCIPdebugMsg(scip, "all linear ordering constraints are feasible.\n");
615  *result = SCIP_FEASIBLE;
616  return SCIP_OKAY;
617 }
618 
619 /** constraint enforcing method of constraint handler for pseudo solutions */
620 static
621 SCIP_DECL_CONSENFOPS(consEnfopsLOP)
622 { /*lint --e{715}*/
623  int c;
624 
625  assert( scip != NULL );
626  assert( conshdlr != NULL );
627  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
628  assert( conss != NULL );
629  assert( result != NULL );
630 
631  /* loop through all constraints */
632  for (c = 0; c < nconss; ++c)
633  {
634  SCIP_CONSDATA* consdata;
635  SCIP_CONS* cons;
636  SCIP_VAR*** vars;
637  int i;
638  int j;
639  int k;
640  int n;
641 
642  cons = conss[c];
643  assert( cons != NULL );
644  SCIPdebugMsg(scip, "enforcing pseudo solution for linear ordering constraint <%s>.\n", SCIPconsGetName(cons));
645 
646  consdata = SCIPconsGetData(cons);
647  assert( consdata != NULL );
648  assert( consdata->vars != NULL );
649  vars = consdata->vars;
650  n = consdata->n;
651 
652  /* check triangle inequalities */
653  for (i = 0; i < n; ++i)
654  {
655  for (j = 0; j < n; ++j)
656  {
657  SCIP_Bool oneIJ;
658  if (j == i)
659  continue;
660 
661  /* the priorities should ensure that the solution is integral */
662  assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, NULL, vars[i][j])) );
663  assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, NULL, vars[j][i])) );
664  oneIJ = SCIPisGT(scip, SCIPgetSolVal(scip, NULL, vars[i][j]), 0.5);
665 
666  if ( oneIJ == SCIPisGT(scip, SCIPgetSolVal(scip, NULL, vars[j][i]), 0.5) )
667  {
668  SCIPdebugMsg(scip, "constraint <%s> infeasible (violated equation).\n", SCIPconsGetName(cons));
669  *result = SCIP_INFEASIBLE;
670  return SCIP_OKAY;
671  }
672 
673  for (k = 0; k < n; ++k)
674  {
675  SCIP_Bool oneJK, oneKI;
676  if (k == i || k == j)
677  continue;
678 
679  assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, NULL, vars[j][k])) );
680  assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, NULL, vars[k][i])) );
681  oneJK = SCIPisGT(scip, SCIPgetSolVal(scip, NULL, vars[j][k]), 0.5);
682  oneKI = SCIPisGT(scip, SCIPgetSolVal(scip, NULL, vars[k][i]), 0.5);
683 
684  /* if triangle inequality is violated */
685  if ( oneIJ && oneJK && oneKI )
686  {
687  SCIPdebugMsg(scip, "constraint <%s> infeasible (violated triangle ineq.).\n", SCIPconsGetName(cons));
688  *result = SCIP_INFEASIBLE;
689  return SCIP_OKAY;
690  }
691  }
692  }
693  }
694  }
695  SCIPdebugMsg(scip, "all linear ordering constraints are feasible.\n");
696  *result = SCIP_FEASIBLE;
697  return SCIP_OKAY;
698 }
699 
700 /** feasibility check method of constraint handler for integral solutions */
701 static
702 SCIP_DECL_CONSCHECK(consCheckLOP)
703 { /*lint --e{715}*/
704  int c;
705 
706  assert( scip != NULL );
707  assert( conshdlr != NULL );
708  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
709  assert( conss != NULL );
710  assert( result != NULL );
711 
712  /* loop through all constraints */
713  for (c = 0; c < nconss; ++c)
714  {
715  SCIP_CONSDATA* consdata;
716  SCIP_CONS* cons;
717  SCIP_VAR*** vars;
718  int i;
719  int j;
720  int k;
721  int n;
722 
723  cons = conss[c];
724  assert( cons != NULL );
725  SCIPdebugMsg(scip, "checking linear ordering constraint <%s>.\n", SCIPconsGetName(cons));
726 
727  consdata = SCIPconsGetData(cons);
728  assert( consdata != NULL );
729  assert( consdata->vars != NULL );
730  vars = consdata->vars;
731  n = consdata->n;
732 
733  /* check triangle inequalities and symmetry equations */
734  for (i = 0; i < n; ++i)
735  {
736  for (j = 0; j < n; ++j)
737  {
738  SCIP_Bool oneIJ;
739  if (j == i)
740  continue;
741 
742  /* the priorities should ensure that the solution is integral */
743  assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, vars[i][j])) );
744  assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, vars[j][i])) );
745  oneIJ = SCIPisGT(scip, SCIPgetSolVal(scip, sol, vars[i][j]), 0.5);
746 
747  /* check symmetry equations */
748  if ( oneIJ == SCIPisGT(scip, SCIPgetSolVal(scip, sol, vars[j][i]), 0.5) )
749  {
750  SCIPdebugMsg(scip, "constraint <%s> infeasible (violated equation).\n", SCIPconsGetName(cons));
751  *result = SCIP_INFEASIBLE;
752  if( printreason )
753  {
754  SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
755  SCIPinfoMessage(scip, NULL, "violation: symmetry equation violated <%s> = %.15g and <%s> = %.15g\n",
756  SCIPvarGetName(vars[i][j]), SCIPgetSolVal(scip, sol, vars[i][j]), 0.5,
757  SCIPvarGetName(vars[j][i]), SCIPgetSolVal(scip, sol, vars[j][i]), 0.5);
758  }
759  return SCIP_OKAY;
760  }
761 
762  for (k = 0; k < n; ++k)
763  {
764  SCIP_Bool oneJK, oneKI;
765  if (k == i || k == j)
766  continue;
767 
768  assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, vars[j][k])) );
769  assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, vars[k][i])) );
770  oneJK = SCIPisGT(scip, SCIPgetSolVal(scip, sol, vars[j][k]), 0.5);
771  oneKI = SCIPisGT(scip, SCIPgetSolVal(scip, sol, vars[k][i]), 0.5);
772 
773  /* if triangle inequality is violated */
774  if ( oneIJ && oneJK && oneKI )
775  {
776  SCIPdebugMsg(scip, "constraint <%s> infeasible (violated triangle ineq.).\n", SCIPconsGetName(cons));
777  *result = SCIP_INFEASIBLE;
778  if( printreason )
779  {
780  SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
781  SCIPinfoMessage(scip, NULL,
782  "violation: triangle inequality violated <%s> = %.15g, <%s> = %.15g, <%s> = %.15g\n",
783  SCIPvarGetName(vars[i][j]), SCIPgetSolVal(scip, sol, vars[i][j]), 0.5,
784  SCIPvarGetName(vars[j][k]), SCIPgetSolVal(scip, sol, vars[j][k]), 0.5,
785  SCIPvarGetName(vars[k][i]), SCIPgetSolVal(scip, sol, vars[k][i]), 0.5);
786  }
787  return SCIP_OKAY;
788  }
789  }
790  }
791  }
792  }
793  SCIPdebugMsg(scip, "all linear ordering constraints are feasible.\n");
794  *result = SCIP_FEASIBLE;
795  return SCIP_OKAY;
796 }
797 
798 /** domain propagation method of constraint handler */
799 static
800 SCIP_DECL_CONSPROP(consPropLOP)
801 { /*lint --e{715}*/
802  int c;
803  int nGen = 0;
804 
805  assert( scip != NULL );
806  assert( conshdlr != NULL );
807  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
808  assert( conss != NULL );
809  assert( result != NULL );
810 
811  *result = SCIP_DIDNOTRUN;
812 
813  /* loop through all constraints */
814  for (c = 0; c < nconss; ++c)
815  {
816  SCIP_CONSDATA* consdata;
817  SCIP_CONS* cons;
818  SCIP_VAR*** vars;
819  int i;
820  int j;
821  int k;
822  int n;
823 
824  cons = conss[c];
825  assert( cons != NULL );
826  SCIPdebugMsg(scip, "propagating linear ordering constraint <%s>.\n", SCIPconsGetName(cons));
827 
828  *result = SCIP_DIDNOTFIND;
829 
830  consdata = SCIPconsGetData(cons);
831  assert( consdata != NULL );
832  assert( consdata->vars != NULL );
833 
834  vars = consdata->vars;
835  n = consdata->n;
836 
837  /* check triangle inequalities */
838  for (i = 0; i < n; ++i)
839  {
840  for (j = 0; j < n; ++j)
841  {
842  if (j == i)
843  continue;
844 
845  /* if x[i][j] == 1 then x[j][i] = 0 */
846  if ( SCIPvarGetLbLocal(vars[i][j]) > 0.5 )
847  {
848  SCIP_Bool infeasible, tightened;
849  SCIP_CALL( SCIPinferBinvarCons(scip, vars[j][i], FALSE, cons, i*n + j, &infeasible, &tightened) );
850  if ( infeasible )
851  {
852  SCIPdebugMsg(scip, " -> node infeasible.\n");
854  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][j]) );
855  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[j][i]) );
856  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
857  *result = SCIP_CUTOFF;
858  return SCIP_OKAY;
859  }
860  if ( tightened )
861  ++nGen;
862  }
863 
864  /* if x[i][j] == 0 then x[j][i] = 1 */
865  if ( SCIPvarGetUbLocal(vars[i][j]) < 0.5 )
866  {
867  SCIP_Bool infeasible, tightened;
868  SCIP_CALL( SCIPinferBinvarCons(scip, vars[j][i], TRUE, cons, i*n + j, &infeasible, &tightened) );
869  if ( infeasible )
870  {
871  SCIPdebugMsg(scip, " -> node infeasible.\n");
873  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][j]) );
874  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[j][i]) );
875  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
876  *result = SCIP_CUTOFF;
877  return SCIP_OKAY;
878  }
879  if ( tightened )
880  ++nGen;
881  }
882 
883  for (k = 0; k < n; ++k)
884  {
885  if (k == i || k == j)
886  continue;
887 
888  /* if x[i][j] == 1 and x[j][k] == 1 then x[k][i] = 0 */
889  if ( SCIPvarGetLbLocal(vars[i][j]) > 0.5 && SCIPvarGetLbLocal(vars[j][k]) > 0.5 )
890  {
891  SCIP_Bool infeasible, tightened;
892  SCIP_CALL( SCIPinferBinvarCons(scip, vars[k][i], FALSE, cons, n*n + i*n*n + j*n + k, &infeasible, &tightened) );
893  if ( infeasible )
894  {
895  SCIPdebugMsg(scip, " -> node infeasible.\n");
897  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][j]) );
898  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[j][k]) );
899  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[k][i]) );
900  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
901  *result = SCIP_CUTOFF;
902  return SCIP_OKAY;
903  }
904  if ( tightened )
905  ++nGen;
906  }
907 
908  /* all other implications occur with other indices i, j, k */
909  }
910  }
911  }
912  }
913  if (nGen > 0)
914  *result = SCIP_REDUCEDDOM;
915  SCIPdebugMsg(scip, "propagated %d domains.\n", nGen);
916 
917  return SCIP_OKAY;
918 }
919 
920 /** propagation conflict resolving method of constraint handler */
921 static
922 SCIP_DECL_CONSRESPROP(consRespropLOP)
923 { /*lint --e{715}*/
924  SCIP_CONSDATA* consdata;
925  SCIP_VAR*** vars;
926  int n;
927 
928  assert( scip != NULL );
929  assert( conshdlr != NULL );
930  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
931  assert( cons != NULL );
932  assert( infervar != NULL );
933  assert( bdchgidx != NULL );
934  assert( result != NULL );
935 
936  SCIPdebugMsg(scip, "Propagation resolution of constraint <%s>.\n", SCIPconsGetName(cons));
937  *result = SCIP_DIDNOTFIND;
938 
939  consdata = SCIPconsGetData(cons);
940  assert( consdata != NULL);
941  assert( consdata->vars != NULL );
942 
943  n = consdata->n;
944  vars = consdata->vars;
945 
946  assert( 0 <= inferinfo && inferinfo < n*n + n*n*n );
947 
948  /* if the conflict came from an equation */
949  if ( inferinfo < (n*n) )
950  {
951  int index1;
952  int index2;
953 
954  index1 = inferinfo/n;
955  index2 = inferinfo % n;
956  assert( 0 <= index1 && index1 < n );
957  assert( 0 <= index2 && index2 < n );
958  assert( vars[index2][index1] == infervar );
959 
960  /* if the variable was fixed to 0 */
961  if ( SCIPvarGetUbAtIndex(infervar, bdchgidx, FALSE) > 0.5 && SCIPvarGetUbAtIndex(infervar, bdchgidx, TRUE) < 0.5 )
962  {
963  SCIPdebugMsg(scip, " -> reason for x[%d][%d] == 0 was x[%d][%d] = 1.\n", index2, index1, index1, index2);
964  /* the reason was that x[i][j] was fixed to 1 */
965  SCIP_CALL( SCIPaddConflictLb(scip, vars[index1][index2], bdchgidx) );
966  *result = SCIP_SUCCESS;
967  return SCIP_OKAY;
968  }
969 
970  /* if the variable was fixed to 1 */
971  if ( SCIPvarGetLbAtIndex(infervar, bdchgidx, FALSE) < 0.5 && SCIPvarGetLbAtIndex(infervar, bdchgidx, TRUE) > 0.5 )
972  {
973  SCIPdebugMsg(scip, " -> reason for x[%d][%d] == 1 was x[%d][%d] = 0.\n", index2, index1, index1, index2);
974  /* the reason was that x[i][j] was fixed to 0 */
975  SCIP_CALL( SCIPaddConflictUb(scip, vars[index1][index2], bdchgidx) );
976  *result = SCIP_SUCCESS;
977  return SCIP_OKAY;
978  }
979  }
980  else
981  {
982  /* otherwise the conflict came from a triangle inequality */
983  int index1;
984  int index2;
985  int index3;
986 
987  index1 = (inferinfo - n*n)/(n*n);
988  index2 = (inferinfo - n*n - index1 * n*n)/n;
989  index3 = (inferinfo - n*n) % n;
990 
991  assert( 0 <= index1 && index1 < n );
992  assert( 0 <= index2 && index2 < n );
993  assert( 0 <= index3 && index3 < n );
994  assert( index1 != index2 && index2 != index3 && index1 != index3 );
995  assert( vars[index3][index1] == infervar );
996 
997  /* the variable should have been fixed to 0 */
998  assert( SCIPvarGetUbAtIndex(infervar, bdchgidx, FALSE) > 0.5 && SCIPvarGetUbAtIndex(infervar, bdchgidx, TRUE) < 0.5 );
999 
1000  /* the reason was that x[index1][index2] and x[index2][index3] were fixed to 1 */
1001  SCIPdebugMsg(scip, " -> reason for x[%d][%d] == 0 was x[%d][%d] = x[%d][%d] = 1.\n", index3, index1, index1, index2, index2, index3);
1002  SCIP_CALL( SCIPaddConflictLb(scip, vars[index1][index2], bdchgidx) );
1003  SCIP_CALL( SCIPaddConflictLb(scip, vars[index2][index3], bdchgidx) );
1004  *result = SCIP_SUCCESS;
1005  }
1006 
1007  return SCIP_OKAY;
1008 }
1009 
1010 /** variable rounding lock method of constraint handler */
1011 static
1012 SCIP_DECL_CONSLOCK(consLockLOP)
1013 { /*lint --e{715}*/
1014  int i;
1015  int j;
1016  SCIP_CONSDATA* consdata;
1017  SCIP_VAR*** vars;
1018  int n;
1019 
1020  assert( scip != NULL );
1021  assert( conshdlr != NULL );
1022  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1023  assert( cons != NULL );
1024 
1025  SCIPdebugMsg(scip, "Locking linear ordering constraint <%s>.\n", SCIPconsGetName(cons));
1026 
1027  /* get data of constraint */
1028  consdata = SCIPconsGetData(cons);
1029  assert( consdata != NULL);
1030  assert( consdata->vars != NULL );
1031  n = consdata->n;
1032  vars = consdata->vars;
1033 
1034  for (i = 0; i < n; ++i)
1035  {
1036  for (j = 0; j < n; ++j)
1037  {
1038  if (i != j)
1039  {
1040  /* the constaint may be violated in any way */
1041  SCIP_CALL( SCIPaddVarLocksType(scip, vars[i][j], SCIP_LOCKTYPE_MODEL, nlockspos + nlocksneg, nlockspos + nlocksneg) );
1042  }
1043  }
1044  }
1045 
1046  return SCIP_OKAY;
1047 }
1048 
1049 /** constraint display method of constraint handler */
1050 static
1051 SCIP_DECL_CONSPRINT(consPrintLOP)
1052 { /*lint --e{715}*/
1053  SCIP_CONSDATA* consdata;
1054  SCIP_VAR*** vars;
1055  int i;
1056  int j;
1057  int n;
1058 
1059  assert( scip != NULL );
1060  assert( conshdlr != NULL );
1061  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1062  assert( cons != NULL );
1063 
1064  consdata = SCIPconsGetData(cons);
1065  assert( consdata != NULL );
1066  assert( consdata->vars != NULL );
1067  n = consdata->n;
1068  vars = consdata->vars;
1069 
1070  SCIPinfoMessage(scip, file, "LOP[");
1071  for (i = 0; i < n; ++i)
1072  {
1073  if ( i > 0 )
1074  SCIPinfoMessage(scip, file, ", ");
1075  SCIPinfoMessage(scip, file, "(");
1076  for (j = 0; j < n; ++j)
1077  {
1078  if (j != i)
1079  {
1080  if ( j > 0 && (i > 0 || j > 1) )
1081  SCIPinfoMessage(scip, file, ",");
1082  SCIPinfoMessage(scip, file, "%s", SCIPvarGetName(vars[i][j]));
1083  }
1084  }
1085  SCIPinfoMessage(scip, file, ")");
1086  }
1087  SCIPinfoMessage(scip, file, "]\n");
1088 
1089  return SCIP_OKAY;
1090 }
1091 
1092 /** constraint copying method of constraint handler */
1093 static
1094 SCIP_DECL_CONSCOPY(consCopyLOP)
1095 { /*lint --e{715}*/
1096  SCIP_CONSDATA* sourcedata;
1097  SCIP_VAR*** sourcevars;
1098  SCIP_VAR*** vars;
1099  int i;
1100  int j;
1101  int n;
1102 
1103  assert( scip != 0 );
1104  assert( sourceconshdlr != 0 );
1105  assert( strcmp(SCIPconshdlrGetName(sourceconshdlr), CONSHDLR_NAME) == 0 );
1106  assert( cons != 0 );
1107  assert( sourcescip != 0 );
1108  assert( sourcecons != 0 );
1109  assert( varmap != 0 );
1110 
1111  *valid = TRUE;
1112 
1113  SCIPdebugMsg(scip, "Copying method for linear ordering constraint handler.\n");
1114 
1115  sourcedata = SCIPconsGetData(sourcecons);
1116  assert( sourcedata != NULL );
1117 
1118  n = sourcedata->n;
1119  sourcevars = sourcedata->vars;
1120  assert( sourcevars != NULL );
1121 
1122  SCIP_CALL( SCIPallocBufferArray(scip, &vars, n) );
1123  BMSclearMemoryArray(vars, n);
1124 
1125  for (i = 0; i < n; ++i)
1126  {
1127  SCIP_CALL( SCIPallocBufferArray(scip, &(vars[i]), n) ); /*lint !e866*/
1128 
1129  for (j = 0; j < n && *valid; ++j)
1130  {
1131  if ( i != j )
1132  {
1133  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[i][j], &vars[i][j], varmap, consmap, global, valid) );
1134  assert( !(*valid) || vars[i][j] != NULL );
1135  }
1136  }
1137  }
1138 
1139  if ( *valid )
1140  {
1141  /* create copied constraint */
1142  if ( name == 0 )
1143  name = SCIPconsGetName(sourcecons);
1144 
1145  SCIP_CALL( SCIPcreateConsLOP(scip, cons, name, n, vars,
1146  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
1147  }
1148 
1149  /* free memory in reverse order */
1150  for (i = n-1; i >= 0; --i)
1151  SCIPfreeBufferArrayNull(scip, &vars[i]);
1152  SCIPfreeBufferArray(scip, &vars);
1153 
1154  return SCIP_OKAY;
1155 }
1156 
1157 /** creates the handler for linear ordering constraints and includes it in SCIP */
1159  SCIP* scip /**< SCIP data structure */
1160  )
1161 {
1162  SCIP_CONSHDLR* conshdlr;
1163 
1164  /* include constraint handler */
1165  conshdlr = NULL;
1168  consEnfolpLOP, consEnfopsLOP, consCheckLOP, consLockLOP, NULL) );
1169  assert( conshdlr != NULL );
1170 
1171  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteLOP) );
1172  SCIP_CALL( SCIPsetConshdlrExit(scip, conshdlr, consExitLOP) );
1173  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyLOP, consCopyLOP) );
1174  SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransLOP) );
1175  SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpLOP) );
1176  SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpLOP, consSepasolLOP,
1178  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropLOP, CONSHDLR_PROPFREQ,
1180  SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropLOP) );
1181  SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintLOP) );
1182 
1183  return SCIP_OKAY;
1184 }
1185 
1186 /** creates and captures a linear ordering constraint */
1188  SCIP* scip, /**< SCIP data structure */
1189  SCIP_CONS** cons, /**< pointer to hold the created constraint */
1190  const char* name, /**< name of constraint */
1191  int n, /**< number of elements */
1192  SCIP_VAR*** vars, /**< n x n matrix of binary variables */
1193  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? */
1194  SCIP_Bool separate, /**< should the constraint be separated during LP processing? */
1195  SCIP_Bool enforce, /**< should the constraint be enforced during node processing? */
1196  SCIP_Bool check, /**< should the constraint be checked for feasibility? */
1197  SCIP_Bool propagate, /**< should the constraint be propagated during node processing? */
1198  SCIP_Bool local, /**< is constraint only valid locally? */
1199  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)? */
1200  SCIP_Bool dynamic, /**< is constraint subject to aging? */
1201  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? */
1202  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
1203  * if it may be moved to a more global node? */
1204  )
1205 {
1206  SCIP_CONSHDLR* conshdlr;
1207  SCIP_CONSDATA* consdata;
1208  int i;
1209  int j;
1210 
1211  /* find the linear ordering constraint handler */
1212  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
1213  if (conshdlr == NULL)
1214  {
1215  SCIPerrorMessage("linear ordering constraint handler not found\n");
1216  return SCIP_PLUGINNOTFOUND;
1217  }
1218 
1219  /* create constraint data */
1220  SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
1221 
1222  consdata->n = n;
1223  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->vars, n) );
1224  for (i = 0; i < n; ++i)
1225  {
1226  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->vars[i]), n) ); /*lint !e866*/
1227  for (j = 0; j < n; ++j)
1228  {
1229  if (j != i)
1230  {
1231  assert( vars[i][j] != NULL );
1232  consdata->vars[i][j] = vars[i][j];
1233  }
1234  }
1235  }
1236 
1237  /* create constraint */
1238  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
1239  local, modifiable, dynamic, removable, stickingatnode) );
1240 
1241  return SCIP_OKAY;
1242 }
static SCIP_DECL_CONSPRINT(consPrintLOP)
Definition: cons_lop.c:1052
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:116
#define CONSHDLR_DELAYSEPA
Definition: cons_lop.c:47
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:640
#define NULL
Definition: def.h:239
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyLOP)
Definition: cons_lop.c:161
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:99
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1547
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPcreateConsLOP(SCIP *scip, SCIP_CONS **cons, const char *name, int n, 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_lop.c:1188
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8335
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip_cons.c:663
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:954
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1570
#define SCIP_MAXSTRLEN
Definition: def.h:260
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1602
static SCIP_DECL_CONSENFOPS(consEnfopsLOP)
Definition: cons_lop.c:622
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17399
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1442
#define CONSHDLR_SEPAFREQ
Definition: cons_lop.c:42
#define CONSHDLR_DELAYPROP
Definition: cons_lop.c:48
static SCIP_DECL_CONSRESPROP(consRespropLOP)
Definition: cons_lop.c:923
#define FALSE
Definition: def.h:65
int SCIPgetSubscipDepth(SCIP *scip)
Definition: scip_copy.c:2354
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:243
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10017
#define TRUE
Definition: def.h:64
#define SCIPdebug(x)
Definition: pub_message.h:74
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8355
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:114
#define CONSHDLR_PROPFREQ
Definition: cons_lop.c:43
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
Definition: scip_cons.c:297
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:97
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8345
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
Definition: scip_cons.c:686
#define SCIPdebugMsg
Definition: scip_message.h:88
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:279
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, 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: scip_cons.c:1011
#define CONSHDLR_NAME
Definition: cons_lop.c:37
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
static SCIP_DECL_CONSINITLP(consInitlpLOP)
Definition: cons_lop.c:346
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4199
#define CONSHDLR_DESC
Definition: cons_lop.c:38
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:409
#define SCIPerrorMessage
Definition: pub_message.h:45
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4191
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
#define CONSHDLR_EAGERFREQ
Definition: cons_lop.c:44
static SCIP_DECL_CONSSEPALP(consSepalpLOP)
Definition: cons_lop.c:409
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:143
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip_cut.c:179
constraint handler for linear ordering constraints
SCIP_Real SCIPvarGetUbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: var.c:16138
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8076
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8295
static SCIP_DECL_CONSTRANS(consTransLOP)
Definition: cons_lop.c:289
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16729
#define SCIP_CALL(x)
Definition: def.h:351
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
#define CONSHDLR_CHECKPRIORITY
Definition: cons_lop.c:41
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8315
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:294
static SCIP_DECL_CONSEXIT(consExitLOP)
Definition: cons_lop.c:207
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip_cons.c:709
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:51
static SCIP_DECL_CONSCOPY(consCopyLOP)
Definition: cons_lop.c:1095
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
#define SCIP_Bool
Definition: def.h:62
static SCIP_DECL_CONSCHECK(consCheckLOP)
Definition: cons_lop.c:703
SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1336
SCIP_Real SCIPvarGetLbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: var.c:16014
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip_cons.c:2550
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8275
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8245
static SCIP_DECL_CONSSEPASOL(consSepasolLOP)
Definition: cons_lop.c:453
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip_cons.c:847
static SCIP_DECL_CONSPROP(consPropLOP)
Definition: cons_lop.c:801
SCIP_RETCODE SCIPincludeConshdlrLOP(SCIP *scip)
Definition: cons_lop.c:1159
#define CONSHDLR_ENFOPRIORITY
Definition: cons_lop.c:40
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1474
static SCIP_DECL_CONSDELETE(consDeleteLOP)
Definition: cons_lop.c:178
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2379
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define CONSHDLR_PROP_TIMING
Definition: cons_lop.c:51
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
Definition: scip_copy.c:737
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8106
SCIP_RETCODE SCIPsetConshdlrExit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXIT((*consexit)))
Definition: scip_cons.c:482
#define CONSHDLR_SEPAPRIORITY
Definition: cons_lop.c:39
#define SCIP_Real
Definition: def.h:150
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8325
#define CONSHDLR_NEEDSCONS
Definition: cons_lop.c:49
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8265
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8255
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2094
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17409
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
static SCIP_DECL_CONSENFOLP(consEnfolpLOP)
Definition: cons_lop.c:496
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:112
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1410
static SCIP_RETCODE LOPseparate(SCIP *scip, SCIP_CONSHDLR *conshdlr, int n, SCIP_VAR ***vars, SCIP_SOL *sol, int *nGen, SCIP_Bool *cutoff)
Definition: cons_lop.c:64
SCIP_RETCODE SCIPinferBinvarCons(SCIP *scip, SCIP_VAR *var, SCIP_Bool fixedval, SCIP_CONS *infercons, int inferinfo, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5636
static SCIP_DECL_CONSLOCK(consLockLOP)
Definition: cons_lop.c:1013
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip_cons.c:343