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