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-2022 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 scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /* uncomment for debug output: */
17 /* #define SCIP_DEBUG */
18 
19 /**@file cons_lop.c
20  * @brief 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$ for \f$i < j\f$ (symmetry equations - added initially)
25  * - \f$ x_{ij} + x_{jk} + x_{ki} \leq 2 \f$ for \f$i < j, i < k, j \neq k\f$ (triangle inequalities - separated)
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 1 /**< 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 = i+1; j < n && ! (*cutoff); ++j)
87  {
88  SCIP_Real valIJ;
89 
90  valIJ = SCIPgetSolVal(scip, sol, vars[i][j]);
91 
92  /* if symmetry equations are violated - should not be the case, if they are added in the beginning */
93  if ( ! SCIPisFeasEQ(scip, valIJ + SCIPgetSolVal(scip, sol, vars[j][i]), 1.0) )
94  {
95  SCIP_ROW *row;
96 
97  (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "sym#%d#%d", i, j);
98 
99  SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, s, 1.0, 1.0, FALSE, FALSE, TRUE) );
100  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
101  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[i][j], 1.0) );
102  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[j][i], 1.0) );
103  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
104 #ifdef SCIP_DEBUG
105  SCIPdebug( SCIPprintRow(scip, row, NULL) );
106 #endif
107  SCIP_CALL( SCIPaddRow(scip, row, FALSE, cutoff) );
108  SCIP_CALL( SCIPreleaseRow(scip, &row));
109  ++(*nGen);
110 
111  if ( *cutoff )
112  break;
113  }
114 
115  /* check triangle inequalities */
116  for (k = i+1; k < n; ++k)
117  {
118  SCIP_Real sum;
119 
120  if ( k == j )
121  continue;
122 
123  sum = valIJ + SCIPgetSolVal(scip, sol, vars[j][k]) + SCIPgetSolVal(scip, sol, vars[k][i]);
124 
125  /* if sum - 2.0 > 0, i.e., the cut is violated */
126  if ( SCIPisEfficacious(scip, sum - 2.0) )
127  {
128  SCIP_ROW *row;
129 
130  (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "triangle#%d#%d#%d", i, j, k);
131 
132  SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, s, -SCIPinfinity(scip), 2.0, FALSE, FALSE, TRUE) );
133  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
134  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[i][j], 1.0) );
135  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[j][k], 1.0) );
136  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[k][i], 1.0) );
137  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
138 #ifdef SCIP_DEBUG
139  SCIPdebug( SCIPprintRow(scip, row, NULL) );
140 #endif
141  SCIP_CALL( SCIPaddRow(scip, row, FALSE, cutoff) );
142  SCIP_CALL( SCIPreleaseRow(scip, &row));
143  ++(*nGen);
144 
145  if ( *cutoff )
146  break;
147  }
148  }
149  }
150  }
151 
152  return SCIP_OKAY;
153 }
154 
155 
156 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
157 static
158 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyLOP)
159 { /*lint --e{715}*/
160  assert( scip != NULL );
161  assert( conshdlr != NULL );
162  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
163  assert( valid != NULL );
164 
165  /* call inclusion method of constraint handler */
167 
168  *valid = TRUE;
169 
170  return SCIP_OKAY;
171 }
172 
173 /** frees specific constraint data */
174 static
175 SCIP_DECL_CONSDELETE(consDeleteLOP)
176 { /*lint --e{715}*/
177  int i;
178  int n;
179 
180  assert( scip != NULL );
181  assert( conshdlr != NULL );
182  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
183  assert( cons != NULL );
184  assert( consdata != NULL);
185  assert( *consdata != NULL);
186  assert( (*consdata)->vars != NULL );
187 
188  SCIPdebugMsg(scip, "deleting linear ordering constraint <%s>.\n", SCIPconsGetName(cons));
189 
190  n = (*consdata)->n;
191  for (i = 0; i < n; ++i)
192  SCIPfreeBlockMemoryArray(scip, &((*consdata)->vars[i]), n); /*lint !e866*/
193  SCIPfreeBlockMemoryArray(scip, &((*consdata)->vars), n);
194  SCIPfreeBlockMemory(scip, consdata);
195 
196  return SCIP_OKAY;
197 }
198 
199 /** deinitialization method of constraint handler (called before transformed problem is freed)
200  *
201  * We output the final linear ordering.
202  */
203 static
204 SCIP_DECL_CONSEXIT(consExitLOP)
205 { /*lint --e{715}*/
206  SCIP_SOL* sol;
207  int c;
208  int i;
209  int j;
210  int n;
211 
212  assert( scip != NULL );
213  assert( conshdlr != NULL );
214  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
215 
216  SCIPdebugMsg(scip, "exiting linear ordering constraint handler <%s>.\n", SCIPconshdlrGetName(conshdlr));
217 
218  /* avoid output for subscips */
219  if ( SCIPgetSubscipDepth(scip) > 0 )
220  return SCIP_OKAY;
221 
222  /* get best solution */
223  sol = SCIPgetBestSol(scip);
224  if ( sol == NULL )
225  return SCIP_OKAY;
226 
227  /* loop through all constraints */
228  for (c = 0; c < nconss; ++c)
229  {
230  SCIP_CONSDATA* consdata;
231  SCIP_VAR*** vars;
232  int* outdeg;
233  int* indices;
234 
235  assert( conss != NULL );
236  assert( conss[c] != NULL );
237  SCIPdebugMsg(scip, "solution for for linear ordering constraint <%s>.\n", SCIPconsGetName(conss[c]));
238 
239  consdata = SCIPconsGetData(conss[c]);
240  assert( consdata != NULL );
241  assert( consdata->vars != NULL );
242  n = consdata->n;
243  vars = consdata->vars;
244 
245  SCIP_CALL( SCIPallocBufferArray(scip, &outdeg, n) );
246  SCIP_CALL( SCIPallocBufferArray(scip, &indices, n) );
247 
248  /* compute out-degree */
249  for (i = 0; i < n; ++i)
250  {
251  int deg = 0;
252  for (j = 0; j < n; ++j)
253  {
254  SCIP_Real val;
255 
256  if (j == i)
257  continue;
258 
259  val = SCIPgetSolVal(scip, sol, vars[i][j]);
260  assert( SCIPisFeasIntegral(scip, val) );
261  if ( val < 0.5 )
262  ++deg;
263  }
264  outdeg[i] = deg;
265  indices[i] = i;
266  }
267 
268  /* sort such that degrees are non-decreasing */
269  SCIPsortIntInt(outdeg, indices, n);
270 
271  /* output */
272  SCIPinfoMessage(scip, NULL, "\nFinal order of linear ordering constraint <%s>:\n", SCIPconsGetName(conss[c]));
273  for (i = 0; i < n; ++i)
274  SCIPinfoMessage(scip, NULL, "%d ", indices[i]);
275  SCIPinfoMessage(scip, NULL, "\n");
276 
277  SCIPfreeBufferArray(scip, &indices);
278  SCIPfreeBufferArray(scip, &outdeg);
279  }
280 
281  return SCIP_OKAY;
282 }
283 
284 /** transforms constraint data into data belonging to the transformed problem */
285 static
286 SCIP_DECL_CONSTRANS(consTransLOP)
287 { /*lint --e{715}*/
288  SCIP_CONSDATA* consdata;
289  SCIP_CONSDATA* sourcedata;
290  int i;
291  int j;
292  int n;
293  char s[SCIP_MAXSTRLEN];
294 
295  assert( scip != NULL );
296  assert( conshdlr != NULL );
297  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
298  assert( sourcecons != NULL );
299  assert( targetcons != NULL );
300 
301  SCIPdebugMsg(scip, "transforming linear ordering constraint <%s>.\n", SCIPconsGetName(sourcecons) );
302 
303  /* get data of original constraint */
304  sourcedata = SCIPconsGetData(sourcecons);
305  assert( sourcedata != NULL);
306 
307  /* create constraint data */
308  SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
309 
310  n = sourcedata->n;
311  consdata->n = n;
312 
313  /* transform variables */
314  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->vars, n) );
315  for (i = 0; i < n; ++i)
316  {
317  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->vars[i]), n) ); /*lint !e866*/
318  for (j = 0; j < n; ++j)
319  {
320  if (j != i)
321  {
322  assert( sourcedata->vars[i][j] != NULL );
323  SCIP_CALL( SCIPgetTransformedVar(scip, sourcedata->vars[i][j], &(consdata->vars[i][j])) );
324  }
325  }
326  }
327 
328  /* create constraint */
329  (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "t_%s", SCIPconsGetName(sourcecons));
330 
331  SCIP_CALL( SCIPcreateCons(scip, targetcons, s, conshdlr, consdata,
332  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons),
333  SCIPconsIsEnforced(sourcecons), SCIPconsIsChecked(sourcecons),
334  SCIPconsIsPropagated(sourcecons), SCIPconsIsLocal(sourcecons),
335  SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons),
336  SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
337 
338  return SCIP_OKAY;
339 }
340 
341 /** LP initialization method of constraint handler */
342 static
343 SCIP_DECL_CONSINITLP(consInitlpLOP)
344 { /*lint --e{715}*/
345  char s[SCIP_MAXSTRLEN];
346  int c;
347  int nGen = 0;
348 
349  assert( scip != NULL );
350  assert( conshdlr != NULL );
351  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
352  assert( infeasible != NULL );
353 
354  *infeasible = FALSE;
355 
356  /* loop through all constraints */
357  for (c = 0; c < nconss; ++c)
358  {
359  SCIP_CONSDATA* consdata;
360  SCIP_VAR*** vars;
361  int i;
362  int j;
363  int n;
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( SCIPcreateEmptyRowConshdlr(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 = i + 1; j < n; ++j)
534  {
535  SCIP_Real valIJ;
536 
537  valIJ = SCIPgetSolVal(scip, NULL, vars[i][j]);
538 
539  /* if symmetry equations are violated - should not be the case, if they are added in the beginning */
540  if ( ! SCIPisFeasEQ(scip, 1.0 - valIJ, SCIPgetSolVal(scip, NULL, vars[j][i])) )
541  {
542  SCIP_ROW *row;
543  SCIP_Bool infeasible;
544 
545  (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "sym#%d#%d", i, j);
546 
547  SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, s, 1.0, 1.0, FALSE, FALSE, TRUE) );
548  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
549  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[i][j], 1.0) );
550  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[j][i], 1.0) );
551  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
552 #ifdef SCIP_DEBUG
553  SCIPdebug( SCIPprintRow(scip, row, NULL) );
554 #endif
555  SCIP_CALL( SCIPaddRow(scip, row, FALSE, &infeasible) );
556  SCIP_CALL( SCIPreleaseRow(scip, &row));
557  ++nGen;
558 
559  if ( infeasible )
560  {
561  *result = SCIP_CUTOFF;
562  return SCIP_OKAY;
563  }
564  }
565 
566  /* enforce triangle inequalities */
567  for (k = i + 1; k < n; ++k)
568  {
569  SCIP_Real sum;
570 
571  if ( k == j )
572  continue;
573 
574  sum = valIJ + SCIPgetSolVal(scip, NULL, vars[j][k]) + SCIPgetSolVal(scip, NULL, vars[k][i]);
575 
576  /* if sum > 2.0, i.e., the cut is violated */
577  if ( SCIPisFeasGT(scip, sum, 2.0) ) /* this is the only difference to the separation call */
578  {
579  SCIP_ROW *row;
580  SCIP_Bool infeasible;
581 
582  (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "triangle#%d#%d#%d", i, j, k);
583 
584  SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, s, -SCIPinfinity(scip), 2.0, FALSE, FALSE, TRUE) );
585  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
586  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[i][j], 1.0) );
587  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[j][k], 1.0) );
588  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[k][i], 1.0) );
589  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
590 #ifdef SCIP_DEBUG
591  SCIPdebug( SCIPprintRow(scip, row, NULL) );
592 #endif
593  SCIP_CALL( SCIPaddRow(scip, row, FALSE, &infeasible) );
594  SCIP_CALL( SCIPreleaseRow(scip, &row));
595  ++nGen;
596 
597  if ( infeasible )
598  {
599  *result = SCIP_CUTOFF;
600  return SCIP_OKAY;
601  }
602  }
603  }
604  }
605  }
606 
607  if (nGen > 0)
608  {
609  *result = SCIP_SEPARATED;
610  return SCIP_OKAY;
611  }
612 
613  }
614  SCIPdebugMsg(scip, "all linear ordering constraints are feasible.\n");
615  *result = SCIP_FEASIBLE;
616 
617  return SCIP_OKAY;
618 }
619 
620 /** constraint enforcing method of constraint handler for pseudo solutions */
621 static
622 SCIP_DECL_CONSENFOPS(consEnfopsLOP)
623 { /*lint --e{715}*/
624  int c;
625 
626  assert( scip != NULL );
627  assert( conshdlr != NULL );
628  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
629  assert( conss != NULL );
630  assert( result != NULL );
631 
632  /* loop through all constraints */
633  for (c = 0; c < nconss; ++c)
634  {
635  SCIP_CONSDATA* consdata;
636  SCIP_CONS* cons;
637  SCIP_VAR*** vars;
638  int i;
639  int j;
640  int k;
641  int n;
642 
643  cons = conss[c];
644  assert( cons != NULL );
645  SCIPdebugMsg(scip, "enforcing pseudo solution for linear ordering constraint <%s>.\n", SCIPconsGetName(cons));
646 
647  consdata = SCIPconsGetData(cons);
648  assert( consdata != NULL );
649  assert( consdata->vars != NULL );
650  vars = consdata->vars;
651  n = consdata->n;
652 
653  /* check triangle inequalities */
654  for (i = 0; i < n; ++i)
655  {
656  for (j = i + 1; j < n; ++j)
657  {
658  SCIP_Bool oneIJ;
659  SCIP_Bool oneJI;
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 
665  oneIJ = SCIPgetSolVal(scip, NULL, vars[i][j]) > 0.5 ? TRUE : FALSE;
666  oneJI = SCIPgetSolVal(scip, NULL, vars[j][i]) > 0.5 ? TRUE : FALSE;
667 
668  if ( oneIJ == oneJI )
669  {
670  SCIPdebugMsg(scip, "constraint <%s> infeasible (violated equation).\n", SCIPconsGetName(cons));
671  *result = SCIP_INFEASIBLE;
672  return SCIP_OKAY;
673  }
674 
675  for (k = i + 1; k < n; ++k)
676  {
677  SCIP_Bool oneJK;
678  SCIP_Bool oneKI;
679 
680  if ( k == j )
681  continue;
682 
683  assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, NULL, vars[j][k])) );
684  assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, NULL, vars[k][i])) );
685 
686  oneJK = SCIPgetSolVal(scip, NULL, vars[j][k]) > 0.5 ? TRUE : FALSE;
687  oneKI = SCIPgetSolVal(scip, NULL, vars[k][i]) > 0.5 ? TRUE : FALSE;
688 
689  /* if triangle inequality is violated */
690  if ( oneIJ && oneJK && oneKI )
691  {
692  SCIPdebugMsg(scip, "constraint <%s> infeasible (violated triangle ineq.).\n", SCIPconsGetName(cons));
693  *result = SCIP_INFEASIBLE;
694  return SCIP_OKAY;
695  }
696  }
697  }
698  }
699  }
700  SCIPdebugMsg(scip, "all linear ordering constraints are feasible.\n");
701  *result = SCIP_FEASIBLE;
702 
703  return SCIP_OKAY;
704 }
705 
706 /** feasibility check method of constraint handler for integral solutions */
707 static
708 SCIP_DECL_CONSCHECK(consCheckLOP)
709 { /*lint --e{715}*/
710  int c;
711 
712  assert( scip != NULL );
713  assert( conshdlr != NULL );
714  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
715  assert( conss != NULL );
716  assert( result != NULL );
717 
718  /* loop through all constraints */
719  for (c = 0; c < nconss; ++c)
720  {
721  SCIP_CONSDATA* consdata;
722  SCIP_CONS* cons;
723  SCIP_VAR*** vars;
724  int i;
725  int j;
726  int k;
727  int n;
728 
729  cons = conss[c];
730  assert( cons != NULL );
731  SCIPdebugMsg(scip, "checking linear ordering constraint <%s>.\n", SCIPconsGetName(cons));
732 
733  consdata = SCIPconsGetData(cons);
734  assert( consdata != NULL );
735  assert( consdata->vars != NULL );
736  vars = consdata->vars;
737  n = consdata->n;
738 
739  /* check triangle inequalities and symmetry equations */
740  for (i = 0; i < n; ++i)
741  {
742  for (j = i + 1; j < n; ++j)
743  {
744  SCIP_Bool oneIJ;
745  SCIP_Bool oneJI;
746 
747  /* the priorities should ensure that the solution is integral */
748  assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, vars[i][j])) );
749  assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, vars[j][i])) );
750 
751  oneIJ = SCIPgetSolVal(scip, sol, vars[i][j]) > 0.5 ? TRUE : FALSE;
752  oneJI = SCIPgetSolVal(scip, sol, vars[j][i]) > 0.5 ? TRUE : FALSE;
753 
754  /* check symmetry equations */
755  if ( oneIJ == oneJI )
756  {
757  SCIPdebugMsg(scip, "constraint <%s> infeasible (violated equation).\n", SCIPconsGetName(cons));
758  *result = SCIP_INFEASIBLE;
759  if( printreason )
760  {
761  SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
762  SCIPinfoMessage(scip, NULL, "violation: symmetry equation violated <%s> = %.15g and <%s> = %.15g\n",
763  SCIPvarGetName(vars[i][j]), SCIPgetSolVal(scip, sol, vars[i][j]),
764  SCIPvarGetName(vars[j][i]), SCIPgetSolVal(scip, sol, vars[j][i]));
765  }
766  return SCIP_OKAY;
767  }
768 
769  for (k = i + 1; k < n; ++k)
770  {
771  SCIP_Bool oneJK;
772  SCIP_Bool oneKI;
773 
774  if ( k == j )
775  continue;
776 
777  assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, vars[j][k])) );
778  assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, vars[k][i])) );
779 
780  oneJK = SCIPisGT(scip, SCIPgetSolVal(scip, sol, vars[j][k]), 0.5);
781  oneKI = SCIPisGT(scip, SCIPgetSolVal(scip, sol, vars[k][i]), 0.5);
782 
783  /* if triangle inequality is violated */
784  if ( oneIJ && oneJK && oneKI )
785  {
786  SCIPdebugMsg(scip, "constraint <%s> infeasible (violated triangle ineq.).\n", SCIPconsGetName(cons));
787  *result = SCIP_INFEASIBLE;
788  if( printreason )
789  {
790  SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
791  SCIPinfoMessage(scip, NULL,
792  "violation: triangle inequality violated <%s> = %.15g, <%s> = %.15g, <%s> = %.15g\n",
793  SCIPvarGetName(vars[i][j]), SCIPgetSolVal(scip, sol, vars[i][j]),
794  SCIPvarGetName(vars[j][k]), SCIPgetSolVal(scip, sol, vars[j][k]),
795  SCIPvarGetName(vars[k][i]), SCIPgetSolVal(scip, sol, vars[k][i]));
796  }
797  return SCIP_OKAY;
798  }
799  }
800  }
801  }
802  }
803  SCIPdebugMsg(scip, "all linear ordering constraints are feasible.\n");
804  *result = SCIP_FEASIBLE;
805 
806  return SCIP_OKAY;
807 }
808 
809 /** domain propagation method of constraint handler */
810 static
811 SCIP_DECL_CONSPROP(consPropLOP)
812 { /*lint --e{715}*/
813  int c;
814  int nGen = 0;
815 
816  assert( scip != NULL );
817  assert( conshdlr != NULL );
818  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
819  assert( conss != NULL );
820  assert( result != NULL );
821 
822  *result = SCIP_DIDNOTRUN;
823 
824  /* loop through all constraints */
825  for (c = 0; c < nconss; ++c)
826  {
827  SCIP_CONSDATA* consdata;
828  SCIP_CONS* cons;
829  SCIP_VAR*** vars;
830  int i;
831  int j;
832  int k;
833  int n;
834 
835  cons = conss[c];
836  assert( cons != NULL );
837  SCIPdebugMsg(scip, "propagating linear ordering constraint <%s>.\n", SCIPconsGetName(cons));
838 
839  *result = SCIP_DIDNOTFIND;
840 
841  consdata = SCIPconsGetData(cons);
842  assert( consdata != NULL );
843  assert( consdata->vars != NULL );
844 
845  vars = consdata->vars;
846  n = consdata->n;
847 
848  /* check triangle inequalities */
849  for (i = 0; i < n; ++i)
850  {
851  for (j = i + 1; j < n; ++j)
852  {
853  SCIP_Bool infeasible;
854  SCIP_Bool tightened;
855 
856  /* if x[i][j] == 1 then x[j][i] = 0 */
857  if ( SCIPvarGetLbLocal(vars[i][j]) > 0.5 )
858  {
859  SCIP_CALL( SCIPinferBinvarCons(scip, vars[j][i], FALSE, cons, i*n + j, &infeasible, &tightened) );
860  if ( infeasible )
861  {
862  SCIPdebugMsg(scip, " -> node infeasible.\n");
864  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][j]) );
865  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[j][i]) );
866  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
867  *result = SCIP_CUTOFF;
868  return SCIP_OKAY;
869  }
870  if ( tightened )
871  ++nGen;
872  }
873 
874  /* if x[i][j] == 0 then x[j][i] = 1 */
875  if ( SCIPvarGetUbLocal(vars[i][j]) < 0.5 )
876  {
877  SCIP_CALL( SCIPinferBinvarCons(scip, vars[j][i], TRUE, cons, i*n + j, &infeasible, &tightened) );
878  if ( infeasible )
879  {
880  SCIPdebugMsg(scip, " -> node infeasible.\n");
882  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][j]) );
883  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[j][i]) );
884  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
885  *result = SCIP_CUTOFF;
886  return SCIP_OKAY;
887  }
888  if ( tightened )
889  ++nGen;
890  }
891 
892  for (k = i + 1; k < n; ++k)
893  {
894  if ( k == j )
895  continue;
896 
897  /* if x[i][j] == 1 and x[j][k] == 1 then x[k][i] = 0 */
898  if ( SCIPvarGetLbLocal(vars[i][j]) > 0.5 && SCIPvarGetLbLocal(vars[j][k]) > 0.5 )
899  {
900  SCIP_CALL( SCIPinferBinvarCons(scip, vars[k][i], FALSE, cons, n*n + i*n*n + j*n + k, &infeasible, &tightened) );
901  if ( infeasible )
902  {
903  SCIPdebugMsg(scip, " -> node infeasible.\n");
905  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][j]) );
906  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[j][k]) );
907  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[k][i]) );
908  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
909  *result = SCIP_CUTOFF;
910  return SCIP_OKAY;
911  }
912  if ( tightened )
913  ++nGen;
914  }
915 
916  /* all other implications occur with other indices i, j, k */
917  }
918  }
919  }
920  }
921  SCIPdebugMsg(scip, "propagated %d domains.\n", nGen);
922  if (nGen > 0)
923  *result = SCIP_REDUCEDDOM;
924 
925  return SCIP_OKAY;
926 }
927 
928 /** propagation conflict resolving method of constraint handler */
929 static
930 SCIP_DECL_CONSRESPROP(consRespropLOP)
931 { /*lint --e{715}*/
932  SCIP_CONSDATA* consdata;
933  SCIP_VAR*** vars;
934  int n;
935 
936  assert( scip != NULL );
937  assert( conshdlr != NULL );
938  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
939  assert( cons != NULL );
940  assert( infervar != NULL );
941  assert( bdchgidx != NULL );
942  assert( result != NULL );
943 
944  SCIPdebugMsg(scip, "Propagation resolution of constraint <%s>.\n", SCIPconsGetName(cons));
945  *result = SCIP_DIDNOTFIND;
946 
947  consdata = SCIPconsGetData(cons);
948  assert( consdata != NULL);
949  assert( consdata->vars != NULL );
950 
951  n = consdata->n;
952  vars = consdata->vars;
953 
954  assert( 0 <= inferinfo && inferinfo < n*n + n*n*n );
955 
956  /* if the conflict came from an equation */
957  if ( inferinfo < (n*n) )
958  {
959  int index1;
960  int index2;
961 
962  index1 = inferinfo/n;
963  index2 = inferinfo % n;
964  assert( 0 <= index1 && index1 < n );
965  assert( 0 <= index2 && index2 < n );
966  assert( vars[index2][index1] == infervar );
967 
968  /* if the variable was fixed to 0 */
969  if ( SCIPvarGetUbAtIndex(infervar, bdchgidx, FALSE) > 0.5 && SCIPvarGetUbAtIndex(infervar, bdchgidx, TRUE) < 0.5 )
970  {
971  SCIPdebugMsg(scip, " -> reason for x[%d][%d] == 0 was x[%d][%d] = 1.\n", index2, index1, index1, index2);
972  /* the reason was that x[i][j] was fixed to 1 */
973  SCIP_CALL( SCIPaddConflictLb(scip, vars[index1][index2], bdchgidx) );
974  *result = SCIP_SUCCESS;
975  return SCIP_OKAY;
976  }
977 
978  /* if the variable was fixed to 1 */
979  if ( SCIPvarGetLbAtIndex(infervar, bdchgidx, FALSE) < 0.5 && SCIPvarGetLbAtIndex(infervar, bdchgidx, TRUE) > 0.5 )
980  {
981  SCIPdebugMsg(scip, " -> reason for x[%d][%d] == 1 was x[%d][%d] = 0.\n", index2, index1, index1, index2);
982  /* the reason was that x[i][j] was fixed to 0 */
983  SCIP_CALL( SCIPaddConflictUb(scip, vars[index1][index2], bdchgidx) );
984  *result = SCIP_SUCCESS;
985  return SCIP_OKAY;
986  }
987  }
988  else
989  {
990  /* otherwise the conflict came from a triangle inequality */
991  int index1;
992  int index2;
993  int index3;
994 
995  index1 = (inferinfo - n*n)/(n*n);
996  index2 = (inferinfo - n*n - index1 * n*n)/n;
997  index3 = (inferinfo - n*n) % n;
998 
999  assert( 0 <= index1 && index1 < n );
1000  assert( 0 <= index2 && index2 < n );
1001  assert( 0 <= index3 && index3 < n );
1002  assert( index1 != index2 && index2 != index3 && index1 != index3 );
1003  assert( vars[index3][index1] == infervar );
1004 
1005  /* the variable should have been fixed to 0 */
1006  assert( SCIPvarGetUbAtIndex(infervar, bdchgidx, FALSE) > 0.5 && SCIPvarGetUbAtIndex(infervar, bdchgidx, TRUE) < 0.5 );
1007 
1008  /* the reason was that x[index1][index2] and x[index2][index3] were fixed to 1 */
1009  SCIPdebugMsg(scip, " -> reason for x[%d][%d] == 0 was x[%d][%d] = x[%d][%d] = 1.\n", index3, index1, index1, index2, index2, index3);
1010  SCIP_CALL( SCIPaddConflictLb(scip, vars[index1][index2], bdchgidx) );
1011  SCIP_CALL( SCIPaddConflictLb(scip, vars[index2][index3], bdchgidx) );
1012  *result = SCIP_SUCCESS;
1013  }
1014 
1015  return SCIP_OKAY;
1016 }
1017 
1018 /** variable rounding lock method of constraint handler */
1019 static
1020 SCIP_DECL_CONSLOCK(consLockLOP)
1021 { /*lint --e{715}*/
1022  int i;
1023  int j;
1024  SCIP_CONSDATA* consdata;
1025  SCIP_VAR*** vars;
1026  int n;
1027 
1028  assert( scip != NULL );
1029  assert( conshdlr != NULL );
1030  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1031  assert( cons != NULL );
1032 
1033  SCIPdebugMsg(scip, "Locking linear ordering constraint <%s>.\n", SCIPconsGetName(cons));
1034 
1035  /* get data of constraint */
1036  consdata = SCIPconsGetData(cons);
1037  assert( consdata != NULL);
1038  assert( consdata->vars != NULL );
1039  n = consdata->n;
1040  vars = consdata->vars;
1041 
1042  for (i = 0; i < n; ++i)
1043  {
1044  for (j = 0; j < n; ++j)
1045  {
1046  if ( i != j )
1047  {
1048  /* the constraint may be violated in any way */
1049  SCIP_CALL( SCIPaddVarLocksType(scip, vars[i][j], SCIP_LOCKTYPE_MODEL, nlockspos + nlocksneg, nlockspos + nlocksneg) );
1050  }
1051  }
1052  }
1053 
1054  return SCIP_OKAY;
1055 }
1056 
1057 /** constraint display method of constraint handler */
1058 static
1059 SCIP_DECL_CONSPRINT(consPrintLOP)
1060 { /*lint --e{715}*/
1061  SCIP_CONSDATA* consdata;
1062  SCIP_VAR*** vars;
1063  int i;
1064  int j;
1065  int n;
1066 
1067  assert( scip != NULL );
1068  assert( conshdlr != NULL );
1069  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1070  assert( cons != NULL );
1071 
1072  consdata = SCIPconsGetData(cons);
1073  assert( consdata != NULL );
1074  assert( consdata->vars != NULL );
1075  n = consdata->n;
1076  vars = consdata->vars;
1077 
1078  SCIPinfoMessage(scip, file, "LOP[");
1079  for (i = 0; i < n; ++i)
1080  {
1081  if ( i > 0 )
1082  SCIPinfoMessage(scip, file, ", ");
1083  SCIPinfoMessage(scip, file, "(");
1084  for (j = 0; j < n; ++j)
1085  {
1086  if ( j != i )
1087  {
1088  if ( j > 0 && (i > 0 || j > 1) )
1089  SCIPinfoMessage(scip, file, ",");
1090  SCIPinfoMessage(scip, file, "%s", SCIPvarGetName(vars[i][j]));
1091  }
1092  }
1093  SCIPinfoMessage(scip, file, ")");
1094  }
1095  SCIPinfoMessage(scip, file, "]\n");
1096 
1097  return SCIP_OKAY;
1098 }
1099 
1100 /** constraint copying method of constraint handler */
1101 static
1102 SCIP_DECL_CONSCOPY(consCopyLOP)
1103 { /*lint --e{715}*/
1104  SCIP_CONSDATA* sourcedata;
1105  SCIP_VAR*** sourcevars;
1106  SCIP_VAR*** vars;
1107  int i;
1108  int j;
1109  int n;
1110 
1111  assert( scip != NULL );
1112  assert( sourceconshdlr != NULL );
1113  assert( strcmp(SCIPconshdlrGetName(sourceconshdlr), CONSHDLR_NAME) == 0 );
1114  assert( cons != NULL );
1115  assert( sourcescip != NULL );
1116  assert( sourcecons != NULL );
1117  assert( varmap != NULL );
1118  assert( valid != NULL );
1119 
1120  *valid = TRUE;
1121 
1122  SCIPdebugMsg(scip, "Copying method for linear ordering constraint handler.\n");
1123 
1124  sourcedata = SCIPconsGetData(sourcecons);
1125  assert( sourcedata != NULL );
1126 
1127  n = sourcedata->n;
1128  sourcevars = sourcedata->vars;
1129  assert( sourcevars != NULL );
1130 
1131  SCIP_CALL( SCIPallocBufferArray(scip, &vars, n) );
1132  BMSclearMemoryArray(vars, n);
1133 
1134  for (i = 0; i < n; ++i)
1135  {
1136  SCIP_CALL( SCIPallocBufferArray(scip, &(vars[i]), n) ); /*lint !e866*/
1137 
1138  for (j = 0; j < n && *valid; ++j)
1139  {
1140  if ( i != j )
1141  {
1142  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[i][j], &vars[i][j], varmap, consmap, global, valid) );
1143  assert( !(*valid) || vars[i][j] != NULL );
1144  }
1145  }
1146  }
1147 
1148  if ( *valid )
1149  {
1150  /* create copied constraint */
1151  if ( name == 0 )
1152  name = SCIPconsGetName(sourcecons);
1153 
1154  SCIP_CALL( SCIPcreateConsLOP(scip, cons, name, n, vars,
1155  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
1156  }
1157 
1158  /* free memory in reverse order */
1159  for (i = n-1; i >= 0; --i)
1160  SCIPfreeBufferArrayNull(scip, &vars[i]);
1161  SCIPfreeBufferArray(scip, &vars);
1162 
1163  return SCIP_OKAY;
1164 }
1165 
1166 /** creates the handler for linear ordering constraints and includes it in SCIP */
1168  SCIP* scip /**< SCIP data structure */
1169  )
1170 {
1171  SCIP_CONSHDLR* conshdlr = NULL;
1172 
1173  /* include constraint handler */
1176  consEnfolpLOP, consEnfopsLOP, consCheckLOP, consLockLOP, NULL) );
1177  assert( conshdlr != NULL );
1178 
1179  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteLOP) );
1180  SCIP_CALL( SCIPsetConshdlrExit(scip, conshdlr, consExitLOP) );
1181  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyLOP, consCopyLOP) );
1182  SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransLOP) );
1183  SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpLOP) );
1184  SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpLOP, consSepasolLOP,
1186  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropLOP, CONSHDLR_PROPFREQ,
1188  SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropLOP) );
1189  SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintLOP) );
1190 
1191  return SCIP_OKAY;
1192 }
1193 
1194 /** creates and captures a linear ordering constraint */
1196  SCIP* scip, /**< SCIP data structure */
1197  SCIP_CONS** cons, /**< pointer to hold the created constraint */
1198  const char* name, /**< name of constraint */
1199  int n, /**< number of elements */
1200  SCIP_VAR*** vars, /**< n x n matrix of binary variables */
1201  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? */
1202  SCIP_Bool separate, /**< should the constraint be separated during LP processing? */
1203  SCIP_Bool enforce, /**< should the constraint be enforced during node processing? */
1204  SCIP_Bool check, /**< should the constraint be checked for feasibility? */
1205  SCIP_Bool propagate, /**< should the constraint be propagated during node processing? */
1206  SCIP_Bool local, /**< is constraint only valid locally? */
1207  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)? */
1208  SCIP_Bool dynamic, /**< is constraint subject to aging? */
1209  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? */
1210  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
1211  * if it may be moved to a more global node? */
1212  )
1213 {
1214  SCIP_CONSHDLR* conshdlr;
1215  SCIP_CONSDATA* consdata;
1216  int i;
1217  int j;
1218 
1219  /* find the linear ordering constraint handler */
1220  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
1221  if (conshdlr == NULL)
1222  {
1223  SCIPerrorMessage("linear ordering constraint handler not found\n");
1224  return SCIP_PLUGINNOTFOUND;
1225  }
1226 
1227  /* create constraint data */
1228  SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
1229 
1230  consdata->n = n;
1231  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->vars, n) );
1232  for (i = 0; i < n; ++i)
1233  {
1234  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->vars[i]), n) ); /*lint !e866*/
1235  for (j = 0; j < n; ++j)
1236  {
1237  if ( j != i )
1238  {
1239  assert( vars[i][j] != NULL );
1240  consdata->vars[i][j] = vars[i][j];
1241  }
1242  }
1243  }
1244 
1245  /* create constraint */
1246  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
1247  local, modifiable, dynamic, removable, stickingatnode) );
1248 
1249  return SCIP_OKAY;
1250 }
static SCIP_DECL_CONSPRINT(consPrintLOP)
Definition: cons_lop.c:1060
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:101
#define CONSHDLR_DELAYSEPA
Definition: cons_lop.c:47
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:563
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyLOP)
Definition: cons_lop.c:159
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:84
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1626
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:1196
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8344
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip_cons.c:586
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1649
#define SCIP_MAXSTRLEN
Definition: def.h:293
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1686
static SCIP_DECL_CONSENFOPS(consEnfopsLOP)
Definition: cons_lop.c:623
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17966
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1436
#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:931
#define FALSE
Definition: def.h:87
int SCIPgetSubscipDepth(SCIP *scip)
Definition: scip_copy.c:2591
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:166
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
#define TRUE
Definition: def.h:86
#define SCIPdebug(x)
Definition: pub_message.h:84
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8364
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
#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:220
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8354
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
Definition: scip_cons.c:609
#define SCIPdebugMsg
Definition: scip_message.h:69
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
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:934
#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:344
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4256
#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:332
#define SCIPerrorMessage
Definition: pub_message.h:55
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4175
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:128
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip_cut.c:126
constraint handler for linear ordering constraints
SCIP_Real SCIPvarGetUbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: var.c:16661
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8085
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8304
static SCIP_DECL_CONSTRANS(consTransLOP)
Definition: cons_lop.c:287
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17251
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:384
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:8324
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:241
static SCIP_DECL_CONSEXIT(consExitLOP)
Definition: cons_lop.c:205
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip_cons.c:632
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:56
static SCIP_DECL_CONSCOPY(consCopyLOP)
Definition: cons_lop.c:1103
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
#define SCIP_Bool
Definition: def.h:84
static SCIP_DECL_CONSCHECK(consCheckLOP)
Definition: cons_lop.c:709
SCIP_Real SCIPvarGetLbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: var.c:16542
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip_cons.c:2473
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8284
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8254
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:770
static SCIP_DECL_CONSPROP(consPropLOP)
Definition: cons_lop.c:812
SCIP_RETCODE SCIPincludeConshdlrLOP(SCIP *scip)
Definition: cons_lop.c:1168
#define CONSHDLR_ENFOPRIORITY
Definition: cons_lop.c:40
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1553
static SCIP_DECL_CONSDELETE(consDeleteLOP)
Definition: cons_lop.c:176
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2304
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:702
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8115
SCIP_RETCODE SCIPsetConshdlrExit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXIT((*consexit)))
Definition: scip_cons.c:405
#define CONSHDLR_SEPAPRIORITY
Definition: cons_lop.c:39
#define SCIP_Real
Definition: def.h:177
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8334
#define CONSHDLR_NEEDSCONS
Definition: cons_lop.c:49
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8274
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8264
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2197
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
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:123
SCIPallocBlockMemory(scip, subsol))
SCIP_RETCODE SCIPcreateEmptyRowConshdlr(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:1382
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
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:5720
static SCIP_DECL_CONSLOCK(consLockLOP)
Definition: cons_lop.c:1021
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip_cons.c:266