Scippy

SCIP

Solving Constraint Integer Programs

presol_qpkktref.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-2021 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 /**@file presol_qpkktref.c
17  * @ingroup DEFPLUGINS_PRESOL
18  * @brief qpkktref presolver
19  * @author Tobias Fischer
20  *
21  * This presolver tries to add the KKT conditions as additional (redundant) constraints to the (mixed-binary) quadratic
22  * program
23  * \f[
24  * \begin{array}{ll}
25  * \min & x^T Q x + c^T x + d \\
26  * & A x \leq b, \\
27  * & x \in \{0, 1\}^{p} \times R^{n-p}.
28  * \end{array}
29  * \f]
30  *
31  * We first check if the structure of the program is like (QP), see the documentation of the function
32  * checkConsQuadraticProblem().
33  *
34  * If the problem is known to be bounded (all variables have finite lower and upper bounds), then we add the KKT
35  * conditions. For a continuous QPs the KKT conditions have the form
36  * \f[
37  * \begin{array}{ll}
38  * Q x + c + A^T \mu = 0,\\
39  * Ax \leq b,\\
40  * \mu_i \cdot (Ax - b)_i = 0, & i \in \{1, \dots, m\},\\
41  * \mu \geq 0.
42  * \end{array}
43  * \f]
44  * where \f$\mu\f$ are the Lagrangian variables. Each of the complementarity constraints \f$\mu_i \cdot (Ax - b)_i = 0\f$
45  * is enforced via an SOS1 constraint for \f$\mu_i\f$ and an additional slack variable \f$s_i = (Ax - b)_i\f$.
46  *
47  * For mixed-binary QPs, the KKT-like conditions are
48  * \f[
49  * \begin{array}{ll}
50  * Q x + c + A^T \mu + I_J \lambda = 0,\\
51  * Ax \leq b,\\
52  * x_j \in \{0,1\} & j \in J,\\
53  * (1 - x_j) \cdot z_j = 0 & j \in J,\\
54  * x_j \cdot (z_j - \lambda_j) = 0 & j \in J,\\
55  * \mu_i \cdot (Ax - b)_i = 0 & i \in \{1, \dots, m\},\\
56  * \mu \geq 0,
57  * \end{array}
58  * \f]
59  * where \f$J = \{1,\dots, p\}\f$, \f$\mu\f$ and \f$\lambda\f$ are the Lagrangian variables, and \f$I_J\f$ is the
60  * submatrix of the \f$n\times n\f$ identity matrix with columns indexed by \f$J\f$. For the derivation of the KKT-like
61  * conditions, see
62  *
63  * Branch-And-Cut for Complementarity and Cardinality Constrained Linear Programs,@n
64  * Tobias Fischer, PhD Thesis (2016)
65  *
66  * Algorithmically:
67  *
68  * - we handle the quadratic term variables of the quadratic constraint like in the method
69  * presolveAddKKTQuadQuadraticTerms()
70  * - we handle the bilinear term variables of the quadratic constraint like in the method presolveAddKKTQuadBilinearTerms()
71  * - we handle the linear term variables of the quadratic constraint like in the method presolveAddKKTQuadLinearTerms()
72  * - we handle linear constraints in the method presolveAddKKTLinearConss()
73  * - we handle aggregated variables in the method presolveAddKKTAggregatedVars()
74  *
75  * we have a hashmap from each variable to the index of the dual constraint in the KKT conditions.
76  */
77 
78 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
79 
80 #include "blockmemshell/memory.h"
81 #include "scip/cons_knapsack.h"
82 #include "scip/cons_linear.h"
83 #include "scip/cons_logicor.h"
84 #include "scip/cons_quadratic.h"
85 #include "scip/cons_setppc.h"
86 #include "scip/cons_sos1.h"
87 #include "scip/cons_varbound.h"
88 #include "scip/presol_qpkktref.h"
89 #include "scip/pub_cons.h"
90 #include "scip/pub_message.h"
91 #include "scip/pub_misc.h"
92 #include "scip/pub_presol.h"
93 #include "scip/pub_var.h"
94 #include "scip/scip_cons.h"
95 #include "scip/scip_mem.h"
96 #include "scip/scip_message.h"
97 #include "scip/scip_numerics.h"
98 #include "scip/scip_param.h"
99 #include "scip/scip_presol.h"
100 #include "scip/scip_prob.h"
101 #include "scip/scip_var.h"
102 #include <string.h>
103 
104 #define PRESOL_NAME "qpkktref"
105 #define PRESOL_DESC "adds KKT conditions to (mixed-binary) quadratic programs"
106 #define PRESOL_PRIORITY -1 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers);
107  * combined with propagators */
108 #define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no
109  * limit) */
110 #define PRESOL_TIMING SCIP_PRESOLTIMING_MEDIUM /* timing of the presolver (fast, medium, or exhaustive) */
111 
112 
113 /*
114  * Data structures
115  */
116 
117 /** presolver data */
118 struct SCIP_PresolData
119 {
120  SCIP_Bool addkktbinary; /**< if TRUE then allow binary variables for KKT update */
121  SCIP_Bool updatequadbounded; /**< if TRUE then only apply the update to QPs with bounded variables; if
122  * the variables are not bounded then a finite optimal solution might not
123  * exist and the KKT conditions would then be invalid */
124  SCIP_Bool updatequadindef; /**< if TRUE then apply quadratic constraint update even if the quadratic
125  * constraint matrix is known to be indefinite */
126 };
127 
128 
129 /*
130  * Local methods
131  */
132 
133 /** for a linear constraint \f$a^T x \leq b\f$, create the complementarity constraint \f$\mu \cdot s = 0\f$, where
134  * \f$s = b - a^T x\f$ and \f$\mu\f$ is the dual variable associated to the constraint \f$a^T x \leq b\f$
135  */
136 static
137 SCIP_RETCODE createKKTComplementarityLinear(
138  SCIP* scip, /**< SCIP pointer */
139  const char* namepart, /**< name of linear constraint */
140  SCIP_VAR** vars, /**< variables of linear constraint */
141  SCIP_Real* vals, /**< coefficients of variables in linear constraint */
142  SCIP_Real lhs, /**< left hand side of linear constraint */
143  SCIP_Real rhs, /**< right hand side of linear constraint */
144  int nvars, /**< number of variables of linear constraint */
145  SCIP_VAR* dualvar, /**< dual variable associated to linear constraint */
146  SCIP_Bool takelhs, /**< whether to consider the lhs or the rhs of the constraint */
147  int* naddconss /**< buffer to increase with number of created additional constraints */
148  )
149 {
150  char name[SCIP_MAXSTRLEN];
151  SCIP_CONS* KKTlincons;
152  SCIP_CONS* sos1cons;
153  SCIP_VAR* slack;
154  SCIP_Real slackcoef;
155  SCIP_Real eqval;
156 
157  assert( scip != NULL );
158  assert( namepart != NULL );
159  assert( vars != NULL );
160  assert( vals != NULL );
161  assert( dualvar != NULL );
162  assert( ! takelhs || ! SCIPisInfinity(scip, -lhs) );
163  assert( takelhs || ! SCIPisInfinity(scip, rhs) );
164  assert( naddconss != NULL );
165 
166  if( takelhs )
167  {
168  eqval = lhs;
169  slackcoef = -1.0;
170  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "slack_lhs_%s", namepart);
171  }
172  else
173  {
174  eqval = rhs;
175  slackcoef = 1.0;
176  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "slack_rhs_%s", namepart);
177  }
178 
179  /* create slack variable */
180  SCIP_CALL( SCIPcreateVarBasic(scip, &slack, name, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
181 
182  /* add skack variable */
183  SCIP_CALL( SCIPaddVar(scip, slack) );
184 
185  /* create a new linear constraint */
186  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "KKTlin_%s_%d", namepart, takelhs);
187  SCIP_CALL( SCIPcreateConsBasicLinear(scip, &KKTlincons, name, nvars, vars, vals, eqval, eqval) );
188 
189  /* add slack variable to linear constraint */
190  SCIP_CALL( SCIPaddCoefLinear(scip, KKTlincons, slack, slackcoef) );
191 
192  /* create SOS1 (complementarity) constraint involving dual variable of linear constraint and slack variable */
193  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "KKTsos1_lin_%s_%d", namepart, takelhs);
194  SCIP_CALL( SCIPcreateConsBasicSOS1(scip, &sos1cons, name, 0, NULL, NULL) );
195 
196  /* add slack and dual variable to SOS1 constraint */
197  SCIP_CALL( SCIPaddVarSOS1(scip, sos1cons, slack, 1.0) );
198  SCIP_CALL( SCIPaddVarSOS1(scip, sos1cons, dualvar, 2.0) );
199 
200  /* add/release constraints */
201  SCIP_CALL( SCIPaddCons(scip, sos1cons) );
202  SCIP_CALL( SCIPaddCons(scip, KKTlincons) );
203  SCIP_CALL( SCIPreleaseCons(scip, &sos1cons) );
204  SCIP_CALL( SCIPreleaseCons(scip, &KKTlincons) );
205  *naddconss = *naddconss + 2;
206 
207  /* release slack variable */
208  SCIP_CALL( SCIPreleaseVar(scip, &slack) );
209 
210  return SCIP_OKAY;
211 }
212 
213 /** create complementarity constraints of KKT conditions associated to bounds of variables
214  * - for an upper bound constraint \f$x_i \leq u_i\f$, create the complementarity constraint \f$\mu_i \cdot s_i = 0\f$,
215  * where \f$s_i = u_i - x_i\f$ and \f$\mu_i\f$ is the dual variable of the upper bound constraint
216  * - for a lower bound constraint \f$x_i \geq l_i\f$, create the complementarity constraint \f$\lambda_i \cdot w_i = 0\f$,
217  * where \f$w_i = x_i - l_i\f$
218  * and \f$\lambda_i\f$ is the dual variable of the lower bound constraint
219  */
220 static
221 SCIP_RETCODE createKKTComplementarityBounds(
222  SCIP* scip, /**< SCIP pointer */
223  SCIP_VAR* var, /**< variable */
224  SCIP_VAR* dualvar, /**< dual variable associated to bound of variable */
225  SCIP_Bool takelb, /**< whether to consider the lower or upper bound of variable */
226  int* naddconss /**< buffer to increase with number of created additional constraints */
227  )
228 {
229  char name[SCIP_MAXSTRLEN];
230  SCIP_CONS* KKTlincons;
231  SCIP_CONS* sos1cons;
232  SCIP_VAR* slack;
233  SCIP_Real slackcoef;
234  SCIP_Real eqval;
235 
236  assert( scip != NULL );
237  assert( var != NULL );
238  assert( dualvar != NULL );
239  assert( ! takelb || ! SCIPisInfinity(scip, -SCIPvarGetLbGlobal(var)) );
240  assert( takelb || ! SCIPisInfinity(scip, SCIPvarGetUbGlobal(var)) );
241  assert( naddconss != NULL );
242 
243  if( takelb )
244  {
245  eqval = SCIPvarGetLbGlobal(var);
246  slackcoef = -1.0;
247  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "slack_lb_%s", SCIPvarGetName(var));
248  }
249  else
250  {
251  eqval = SCIPvarGetUbGlobal(var);
252  slackcoef = 1.0;
253  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "slack_ub_%s", SCIPvarGetName(var));
254  }
255 
256  /* create complementarity constraint; if bound is nonzero, we additionally need to introduce a slack variable */
257  if( SCIPisFeasZero(scip, eqval) && SCIPvarGetStatus(var) != SCIP_VARSTATUS_MULTAGGR )
258  {
259  /* create SOS1 (complementarity) constraint involving dual variable of linear constraint and slack variable */
260  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "KKTsos1_bound%s_%d", SCIPvarGetName(var), takelb);
261  SCIP_CALL( SCIPcreateConsBasicSOS1(scip, &sos1cons, name, 0, NULL, NULL) );
262 
263  /* add slack and dual variable to SOS1 constraint */
264  SCIP_CALL( SCIPaddVarSOS1(scip, sos1cons, var, 1.0) );
265  SCIP_CALL( SCIPaddVarSOS1(scip, sos1cons, dualvar, 2.0) );
266 
267  /* add/release constraint */
268  SCIP_CALL( SCIPaddCons(scip, sos1cons) );
269  SCIP_CALL( SCIPreleaseCons(scip, &sos1cons) );
270  ++(*naddconss);
271  }
272  else
273  {
274  /* create slack variable */
275  SCIP_CALL( SCIPcreateVarBasic(scip, &slack, name, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
276 
277  /* add skack variable */
278  SCIP_CALL( SCIPaddVar(scip, slack) );
279 
280  /* create a new linear constraint */
281  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "KKT_bound%s_%d", SCIPvarGetName(var), takelb);
282  SCIP_CALL( SCIPcreateConsBasicLinear(scip, &KKTlincons, name, 0, NULL, NULL, eqval, eqval) );
283 
284  /* add slack variable to linear constraint */
285  SCIP_CALL( SCIPaddCoefLinear(scip, KKTlincons, var, 1.0) );
286  SCIP_CALL( SCIPaddCoefLinear(scip, KKTlincons, slack, slackcoef) );
287 
288  /* create SOS1 (complementarity) constraint involving dual variable of linear constraint and slack variable */
289  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "KKTsos1_bound%s_%d", SCIPvarGetName(var), takelb);
290  SCIP_CALL( SCIPcreateConsBasicSOS1(scip, &sos1cons, name, 0, NULL, NULL) );
291 
292  /* add slack and dual variable to SOS1 constraint */
293  SCIP_CALL( SCIPaddVarSOS1(scip, sos1cons, slack, 1.0) );
294  SCIP_CALL( SCIPaddVarSOS1(scip, sos1cons, dualvar, 2.0) );
295 
296  /* add/release constraints */
297  SCIP_CALL( SCIPaddCons(scip, sos1cons) );
298  SCIP_CALL( SCIPaddCons(scip, KKTlincons) );
299  SCIP_CALL( SCIPreleaseCons(scip, &sos1cons) );
300  SCIP_CALL( SCIPreleaseCons(scip, &KKTlincons) );
301  *naddconss = *naddconss + 2;
302 
303  /* release slack variable */
304  SCIP_CALL( SCIPreleaseVar(scip, &slack) );
305  }
306 
307  return SCIP_OKAY;
308 }
309 
310 /** create the complementarity constraints of the KKT-like conditions associated to a binary variable \f$x_i\f$;
311  * these are \f$(1 - x_i) \cdot z_i = 0\f$ and \f$x_i \cdot (z_i - \lambda_i) = 0\f$, where \f$z_i\f$ and
312  * \f$\lambda_i\f$ are dual variables
313  */
314 static
315 SCIP_RETCODE createKKTComplementarityBinary(
316  SCIP* scip, /**< SCIP pointer */
317  SCIP_VAR* var, /**< variable */
318  SCIP_VAR* dualbin1, /**< first dual variable associated to binary variable */
319  SCIP_VAR* dualbin2, /**< second dual variable associated to binary variable */
320  int* naddconss /**< buffer to increase with number of created additional constraints */
321  )
322 {
323  char name[SCIP_MAXSTRLEN];
324  SCIP_CONS* conslinbin1;
325  SCIP_CONS* conslinbin2;
326  SCIP_CONS* sos1cons1;
327  SCIP_CONS* sos1cons2;
328  SCIP_VAR* slackbin1;
329  SCIP_VAR* slackbin2;
330 
331  assert( scip != NULL );
332  assert( var != NULL );
333  assert( dualbin1 != NULL );
334  assert( dualbin2 != NULL );
335  assert( naddconss != NULL );
336 
337  /* create first slack variable associated to binary constraint; domain [-inf, inf] */
338  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "dual_%s_slackbin1", SCIPvarGetName(var));
339  SCIP_CALL( SCIPcreateVarBasic(scip, &slackbin1, name, -SCIPinfinity(scip), SCIPinfinity(scip), 0.0,
340  SCIP_VARTYPE_CONTINUOUS) );
341  SCIP_CALL( SCIPaddVar(scip, slackbin1) );
342  assert( slackbin1 != NULL );
343 
344  /* create a new linear constraint: dualbin1 - dualbin2 = slackbin */
345  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "KKTBinary1_%s", SCIPvarGetName(var));
346  SCIP_CALL( SCIPcreateConsBasicLinear(scip, &conslinbin1, name, 0, NULL, NULL, 0.0, 0.0) );
347  SCIP_CALL( SCIPaddCoefLinear(scip, conslinbin1, dualbin1, 1.0) );
348  SCIP_CALL( SCIPaddCoefLinear(scip, conslinbin1, dualbin2, -1.0) );
349  SCIP_CALL( SCIPaddCoefLinear(scip, conslinbin1, slackbin1, -1.0) );
350  SCIP_CALL( SCIPaddCons(scip, conslinbin1) );
351  SCIP_CALL( SCIPreleaseCons(scip, &conslinbin1) );
352  ++(*naddconss);
353 
354  /* create SOS1 (complementarity) constraint involving binary variable and slack variable */
355  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "KKTsos1_bin1%s", SCIPvarGetName(var));
356  SCIP_CALL( SCIPcreateConsBasicSOS1(scip, &sos1cons1, name, 0, NULL, NULL) );
357 
358  /* add slack and dual variable to SOS1 constraint */
359  SCIP_CALL( SCIPaddVarSOS1(scip, sos1cons1, var, 1.0) );
360  SCIP_CALL( SCIPaddVarSOS1(scip, sos1cons1, slackbin1, 2.0) );
361 
362  /* add/release constraint */
363  SCIP_CALL( SCIPaddCons(scip, sos1cons1) );
364  SCIP_CALL( SCIPreleaseCons(scip, &sos1cons1) );
365  ++(*naddconss);
366 
367  /* release slack variable */
368  SCIP_CALL( SCIPreleaseVar(scip, &slackbin1) );
369 
370  /* create second slack variable associated to binary constraint; domain [0, inf] */
371  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "dual_%s_slackbin2", SCIPvarGetName(var));
372  SCIP_CALL( SCIPcreateVarBasic(scip, &slackbin2, name, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
373  SCIP_CALL( SCIPaddVar(scip, slackbin2) );
374  assert( slackbin2 != NULL );
375 
376  /* create a new linear constraint: 1.0 - var = slackbin2 */
377  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "KKTBinary2_%s", SCIPvarGetName(var));
378  SCIP_CALL( SCIPcreateConsBasicLinear(scip, &conslinbin2, name, 0, NULL, NULL, 1.0, 1.0) );
379  SCIP_CALL( SCIPaddCoefLinear(scip, conslinbin2, var, 1.0) );
380  SCIP_CALL( SCIPaddCoefLinear(scip, conslinbin2, slackbin2, 1.0) );
381  SCIP_CALL( SCIPaddCons(scip, conslinbin2) );
382  SCIP_CALL( SCIPreleaseCons(scip, &conslinbin2) );
383  ++(*naddconss);
384 
385  /* create SOS1 (complementarity) constraint involving first dual variable and slack variable */
386  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "KKTsos1_bin2%s", SCIPvarGetName(var));
387  SCIP_CALL( SCIPcreateConsBasicSOS1(scip, &sos1cons2, name, 0, NULL, NULL) );
388 
389  /* add slack and dual variable to SOS1 constraint */
390  SCIP_CALL( SCIPaddVarSOS1(scip, sos1cons2, dualbin1, 1.0) );
391  SCIP_CALL( SCIPaddVarSOS1(scip, sos1cons2, slackbin2, 2.0) );
392 
393  /* add/release constraint */
394  SCIP_CALL( SCIPaddCons(scip, sos1cons2) );
395  SCIP_CALL( SCIPreleaseCons(scip, &sos1cons2) );
396  ++(*naddconss);
397 
398  /* release slack variable */
399  SCIP_CALL( SCIPreleaseVar(scip, &slackbin2) );
400 
401  return SCIP_OKAY;
402 }
403 
404 /** create/get dual constraint of KKT conditions associated to primal variable @n@n
405  * if variable does not already exist in hashmap then
406  * 1. create dual constraint for variable
407  * 2. create a dual variable \f$\mu_i\f$ for the upper bound constraint \f$x_i \leq u_i\f$
408  * 3. create a dual variable \f$\lambda_i\f$ for the lower bound constraint \f$x_i \geq l_i\f$
409  * 4. create the complementarity constraint \f$\mu_i \cdot s_i = 0\f$, where \f$s_i = u_i - x_i\f$
410  * 5. create the complementarity constraint \f$\lambda_i \cdot w_i = 0\f$, where \f$w_i = x_i - l_i\f$
411  * 6. add objective coefficients of dual variables
412  * 7. the treatment of binary variables needs special care see the documentation of createKKTComplementarityBinary()
413  *
414  * if variable exists in hasmap then the dual constraint associated to the variable has already been created and is returned
415  */
416 static
417 SCIP_RETCODE createKKTDualCons(
418  SCIP* scip, /**< SCIP pointer */
419  SCIP_CONS* objcons, /**< objective constraint */
420  SCIP_VAR* var, /**< variable */
421  SCIP_HASHMAP* varhash, /**< hash map from variable to index of linear constraint */
422  SCIP_CONS** dualconss, /**< array with dual constraints */
423  int* ndualconss, /**< pointer to store number of dual constraints */
424  SCIP_CONS** dualcons, /**< dual constraint associated to variable */
425  int* naddconss /**< buffer to increase with number of created additional constraints */
426  )
427 {
428  SCIP_VAR* dualub = NULL; /* dual variable associated to upper bound constraint */
429  SCIP_VAR* duallb = NULL; /* dual variable associated to lower bound constraint */
430  SCIP_VAR* dualbin1 = NULL; /* first dual variable associated to binary variable */
431  SCIP_VAR* dualbin2 = NULL; /* second dual variable associated to binary variable */
432 
433  assert( scip != NULL );
434  assert( objcons != NULL );
435  assert( var != NULL );
436  assert( varhash != NULL );
437  assert( dualconss != NULL );
438  assert( ndualconss != NULL );
439  assert( naddconss != NULL );
440 
441  /* if variable exists in hashmap */
442  if( SCIPhashmapExists(varhash, var) )
443  {
444  int ind;
445  ind = SCIPhashmapGetImageInt(varhash, var);
446  *dualcons = dualconss[ind];
447  }
448  else
449  {
450  char name[SCIP_MAXSTRLEN];
451  SCIP_Real lb;
452  SCIP_Real ub;
453 
454  lb = SCIPvarGetLbGlobal(var);
455  ub = SCIPvarGetUbGlobal(var);
456 
457  /* create dual variables corresponding to the bounds of the variables; binary variables have to be treated in a
458  * different way */
459  if( SCIPvarIsBinary(var) )
460  {
461  /* create first dual variable associated to binary constraint; the domain of dualbin is [-inf,inf]; the objective
462  * coefficient is -0.5 */
463  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "dual_%s_bin1", SCIPvarGetName(var));
464  SCIP_CALL( SCIPcreateVarBasic(scip, &dualbin1, name, -SCIPinfinity(scip), SCIPinfinity(scip), 0.0,
465  SCIP_VARTYPE_CONTINUOUS) );
466  SCIP_CALL( SCIPaddVar(scip, dualbin1) );
467  assert( dualbin1 != NULL );
468  SCIP_CALL( SCIPaddCoefLinear(scip, objcons, dualbin1, -0.5) );
469 
470  /* create second variable associated to binary constraint; the domain of dualbin2 is [-inf,inf]; the objective
471  * coefficient is zero */
472  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "dual_%s_bin2", SCIPvarGetName(var));
473  SCIP_CALL( SCIPcreateVarBasic(scip, &dualbin2, name, -SCIPinfinity(scip), SCIPinfinity(scip), 0.0,
474  SCIP_VARTYPE_CONTINUOUS) );
475  SCIP_CALL( SCIPaddVar(scip, dualbin2) );
476  assert( dualbin2 != NULL );
477  }
478  else
479  {
480  if( ! SCIPisInfinity(scip, -lb) )
481  {
482  /* create dual variable associated to lower bound; the domain of duallb is [0,inf] */
483  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "dual_%s_lb", SCIPvarGetName(var));
484  SCIP_CALL( SCIPcreateVarBasic(scip, &duallb, name, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
485  SCIP_CALL( SCIPaddVar(scip, duallb) );
486  assert( duallb != NULL );
487  SCIP_CALL( SCIPaddCoefLinear(scip, objcons, duallb, 0.5 * lb) );
488  }
489 
490  if( ! SCIPisInfinity(scip, ub) )
491  {
492  /* create dual variable associated to upper bound; the domain of dualub is [0,inf] */
493  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "dual_%s_ub", SCIPvarGetName(var));
494  SCIP_CALL( SCIPcreateVarBasic(scip, &dualub, name, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
495  SCIP_CALL( SCIPaddVar(scip, dualub) );
496  assert( dualub != NULL );
497  SCIP_CALL( SCIPaddCoefLinear(scip, objcons, dualub, -0.5 * ub) );
498  }
499  }
500 
501  /* add variable in map */
502  SCIP_CALL( SCIPhashmapInsertInt(varhash, var, (*ndualconss)) );
503  assert( *ndualconss == SCIPhashmapGetImageInt(varhash, var) );
504 
505  /* create a new linear constraint */
506  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "KKTref_%s", SCIPvarGetName(var));
507  SCIP_CALL( SCIPcreateConsBasicLinear(scip, dualcons, name, 0, NULL, NULL, 0.0, 0.0) );
508 
509  /* add dual constraint to array for later use */
510  dualconss[(*ndualconss)++] = *dualcons;
511 
512  /* add dual variables to dual constraints and create complementarity constraints; binary variables have to be
513  * treated in a different way */
514  if( SCIPvarIsBinary(var) )
515  {
516  /* add coefficient of second dual variable corresponding to binary variable */
517  SCIP_CALL( SCIPaddCoefLinear(scip, *dualcons, dualbin2, 1.0) );
518 
519  /* create complementarity constraints */
520  SCIP_CALL( createKKTComplementarityBinary(scip, var, dualbin1, dualbin2, naddconss) );
521 
522  SCIP_CALL( SCIPreleaseVar(scip, &dualbin1) );
523  SCIP_CALL( SCIPreleaseVar(scip, &dualbin2) );
524  }
525  else
526  {
527  if( duallb != NULL )
528  {
529  /* add dual variable corresponding to lower bound of variable */
530  SCIP_CALL( SCIPaddCoefLinear(scip, *dualcons, duallb, -1.0) );
531 
532  /* create complementarity constraint between slack variable of lower bound constraint and dual variable of
533  * lower bound */
534  SCIP_CALL( createKKTComplementarityBounds(scip, var, duallb, TRUE, naddconss) );
535 
536  SCIP_CALL( SCIPreleaseVar(scip, &duallb) );
537  }
538 
539  if( dualub != NULL )
540  {
541  /* add dual variable corresponding to upper bound of variable */
542  SCIP_CALL( SCIPaddCoefLinear(scip, *dualcons, dualub, 1.0) );
543 
544  /* create complementarity constraint between slack variable of upper bound constraint and dual variable of
545  * upper bound */
546  SCIP_CALL( createKKTComplementarityBounds(scip, var, dualub, FALSE, naddconss) );
547 
548  SCIP_CALL( SCIPreleaseVar(scip, &dualub) );
549  }
550  }
551  }
552  assert( *dualcons != NULL );
553 
554  return SCIP_OKAY;
555 }
556 
557 /** handle (a single) linear constraint for quadratic constraint update
558  * 1. create the dual constraints (i.e., the two rows of \f$Q x + c + A^T \mu = 0\f$) associated to the variables of the
559  * linear constraint, if not done already
560  * 2. create the dual variables and the complementarity constraints for the lower and upper bound constraints of the
561  * variables of the linear constraint, if not done already
562  * 3. create the dual variable \f$\mu_i\f$ associated to this linear constraint
563  * 4. create the complementarity constraint \f$\mu_i \cdot (Ax - b)_i = 0\f$ associated to this linear constraint
564  * 5. add objective coefficients of dual variables
565  *
566  * for steps 1 and 2 see the documentation of createKKTDualCons() for further information.@n
567  * for step 4 see the documentation of the function createKKTComplementarityLinear() for further information.
568  */
569 static
570 SCIP_RETCODE presolveAddKKTLinearCons(
571  SCIP* scip, /**< SCIP pointer */
572  SCIP_CONS* objcons, /**< objective constraint */
573  const char* namepart, /**< name of linear constraint */
574  SCIP_VAR** vars, /**< variables of linear constraint */
575  SCIP_Real* vals, /**< coefficients of variables in linear constraint */
576  SCIP_Real lhs, /**< left hand side of linear constraint */
577  SCIP_Real rhs, /**< right hand side of linear constraint */
578  int nvars, /**< number of variables of linear constraint */
579  SCIP_HASHMAP* varhash, /**< hash map from variable to index of linear constraint */
580  SCIP_CONS** dualconss, /**< array with dual constraints */
581  int* ndualconss, /**< pointer to store number of dual constraints */
582  int* naddconss /**< buffer to increase with number of created additional constraints */
583  )
584 {
585  int i;
586 
587  assert( scip != NULL );
588  assert( objcons != NULL );
589  assert( namepart != NULL );
590  assert( varhash != NULL );
591  assert( dualconss != NULL );
592  assert( ndualconss != NULL );
593  assert( vars != NULL );
594  assert( vals != NULL );
595  assert( namepart != NULL );
596  assert( naddconss != NULL );
597 
598  /* differ between left hand side and right hand side case (i=0 -> lhs; i=1 -> rhs) */
599  for( i = 0; i < 2; ++i )
600  {
601  char name[SCIP_MAXSTRLEN];
602  SCIP_VAR* duallin = NULL;
603  int j;
604 
605  /* skip one iteration if lhs equals rhs */
606  if( i == 0 && SCIPisFeasEQ(scip, lhs, rhs) )
607  continue;
608 
609  /* create dual variable corresponding to linear constraint */
610  if( i == 0 )
611  {
612  assert( ! SCIPisFeasEQ(scip, lhs, rhs) );
613 
614  if( SCIPisInfinity(scip, -lhs) )
615  continue;
616 
617  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "dual_%s_lhs", namepart);
618  SCIP_CALL( SCIPcreateVarBasic(scip, &duallin, name, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
619  SCIP_CALL( SCIPaddVar(scip, duallin) );
620  SCIP_CALL( SCIPaddCoefLinear(scip, objcons, duallin, 0.5 * lhs) );
621 
622  /* create complementarity constraint between dual variable and slack variable of linear constraint */
623  SCIP_CALL( createKKTComplementarityLinear(scip, namepart, vars, vals, lhs, rhs, nvars, duallin, TRUE,
624  naddconss) );
625  }
626  else
627  {
628  if( SCIPisInfinity(scip, rhs) )
629  continue;
630 
631  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "dual_%s_rhs", namepart);
632  if( SCIPisFeasEQ(scip, lhs, rhs) )
633  {
634  SCIP_CALL( SCIPcreateVarBasic(scip, &duallin, name, -SCIPinfinity(scip), SCIPinfinity(scip), 0.0,
635  SCIP_VARTYPE_CONTINUOUS) );
636  SCIP_CALL( SCIPaddVar(scip, duallin) );
637  SCIP_CALL( SCIPaddCoefLinear(scip, objcons, duallin, -0.5 * rhs) );
638  }
639  else
640  {
641  SCIP_CALL( SCIPcreateVarBasic(scip, &duallin, name, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
642  SCIP_CALL( SCIPaddVar(scip, duallin) );
643  SCIP_CALL( SCIPaddCoefLinear(scip, objcons, duallin, -0.5 * rhs) );
644 
645  /* create complementarity constraint between dual variable and slack variable of linear constraint */
646  SCIP_CALL( createKKTComplementarityLinear(scip, namepart, vars, vals, lhs, rhs, nvars, duallin, FALSE,
647  naddconss) );
648  }
649  }
650  assert( duallin != NULL );
651 
652  /* loop through variables of linear constraint */
653  for( j = 0; j < nvars; ++j )
654  {
655  SCIP_CONS* dualcons = NULL; /* dual constraint associated to variable */
656  SCIP_VAR* var;
657 
658  var = vars[j];
659 
660  /* create/get dual constraint associated to variable;
661  * if variable does not already exist in hashmap then create dual variables for its bounds */
662  SCIP_CALL( createKKTDualCons(scip, objcons, var, varhash, dualconss, ndualconss, &dualcons, naddconss) );
663  assert( dualcons != NULL );
664 
665  /* add dual variable corresponding to linear constraint */
666  if( i == 0 )
667  {
668  SCIP_CALL( SCIPaddCoefLinear(scip, dualcons, duallin, -vals[j]) );
669  }
670  else
671  {
672  SCIP_CALL( SCIPaddCoefLinear(scip, dualcons, duallin, vals[j]) );
673  }
674  }
675 
676  /* release dual variable */
677  SCIP_CALL( SCIPreleaseVar(scip, &duallin) );
678  }
679 
680  return SCIP_OKAY;
681 }
682 
683 /** handle linear constraints for quadratic constraint update, see the documentation of the function
684  * presolveAddKKTLinearCons() for an explanation
685  */
686 static
687 SCIP_RETCODE presolveAddKKTLinearConss(
688  SCIP* scip, /**< SCIP pointer */
689  SCIP_CONS* objcons, /**< objective constraint */
690  SCIP_CONS** savelinconss, /**< copy of array with linear constraints */
691  int nlinconss, /**< number of linear constraints */
692  SCIP_HASHMAP* varhash, /**< hash map from variable to index of linear constraint */
693  SCIP_CONS** dualconss, /**< array with dual constraints */
694  int* ndualconss, /**< pointer to store number of dual constraints */
695  int* naddconss, /**< buffer to increase with number of created additional constraints */
696  int* ndelconss /**< buffer to increase with number of deleted constraints */
697  )
698 {
699  int c;
700 
701  assert( scip != NULL );
702  assert( objcons != NULL );
703  assert( varhash != NULL );
704  assert( dualconss != NULL );
705  assert( ndualconss != NULL );
706  assert( naddconss != NULL );
707  assert( ndelconss != NULL );
708 
709  /* loop through linear constraints */
710  for( c = 0; c < nlinconss; ++c )
711  {
712  SCIP_CONS* lincons;
713  SCIP_VAR** vars;
714  SCIP_Real* vals;
715  SCIP_Real lhs;
716  SCIP_Real rhs;
717  int nvars;
718 
719  /* get data of constraint */
720  lincons = savelinconss[c];
721  assert( lincons != NULL );
722  lhs = SCIPgetLhsLinear(scip, lincons);
723  rhs = SCIPgetRhsLinear(scip, lincons);
724  nvars = SCIPgetNVarsLinear(scip, lincons);
725  vars = SCIPgetVarsLinear(scip, lincons);
726  vals = SCIPgetValsLinear(scip, lincons);
727 
728  /* handle linear constraint for quadratic constraint update */
729  SCIP_CALL( presolveAddKKTLinearCons(scip, objcons, SCIPconsGetName(lincons),
730  vars, vals, lhs, rhs, nvars, varhash, dualconss, ndualconss, naddconss) );
731  }
732 
733  /* remove linear constraints if lhs != rhs, since they are now redundant; their feasibility is already expressed
734  * by s >= 0, where s is the new slack variable that we introduced for these linear constraints */
735  for( c = nlinconss-1; c >= 0; --c )
736  {
737  SCIP_CONS* lincons;
738 
739  lincons = savelinconss[c];
740  assert( savelinconss[c] != NULL );
741 
742  if( ! SCIPisFeasEQ(scip, SCIPgetLhsLinear(scip, lincons), SCIPgetRhsLinear(scip, lincons)) )
743  {
744  SCIP_CALL( SCIPdelCons(scip, savelinconss[c]) );
745  ++(*ndelconss);
746  }
747  }
748 
749  return SCIP_OKAY;
750 }
751 
752 /** handle knapsack constraints for quadratic constraint update, see the documentation of the function
753  * presolveAddKKTLinearCons() for an explanation
754  */
755 static
756 SCIP_RETCODE presolveAddKKTKnapsackConss(
757  SCIP* scip, /**< SCIP pointer */
758  SCIP_CONS* objcons, /**< objective constraint */
759  SCIP_HASHMAP* varhash, /**< hash map from variable to index of linear constraint */
760  SCIP_CONS** dualconss, /**< array with dual constraints */
761  int* ndualconss, /**< pointer to store number of dual constraints */
762  int* naddconss, /**< buffer to increase with number of created additional constraints */
763  int* ndelconss /**< buffer to increase with number of deleted constraints */
764  )
765 {
766  SCIP_CONSHDLR* conshdlr;
767  SCIP_CONS** conss;
768  int nconss;
769  int c;
770 
771  assert( scip != NULL );
772  assert( objcons != NULL );
773  assert( varhash != NULL );
774  assert( dualconss != NULL );
775  assert( ndualconss != NULL );
776  assert( naddconss != NULL );
777  assert( ndelconss != NULL );
778 
779  conshdlr = SCIPfindConshdlr(scip, "knapsack");
780  if( conshdlr == NULL )
781  return SCIP_OKAY;
782 
783  nconss = SCIPconshdlrGetNConss(conshdlr);
784  conss = SCIPconshdlrGetConss(conshdlr);
785 
786  /* loop through knapsack constraints */
787  for( c = 0; c < nconss; ++c )
788  {
789  SCIP_CONS* cons;
790  SCIP_VAR** vars;
791  SCIP_Longint* weights;
792  SCIP_Real* vals;
793  SCIP_Real lhs;
794  SCIP_Real rhs;
795  int nvars;
796  int v;
797 
798  /* get data of constraint */
799  cons = conss[c];
800  assert( cons != NULL );
801  lhs = -SCIPinfinity(scip);
802  rhs = (SCIP_Real) SCIPgetCapacityKnapsack(scip, cons);
803  nvars = SCIPgetNVarsKnapsack(scip, cons);
804  vars = SCIPgetVarsKnapsack(scip, cons);
805  weights = SCIPgetWeightsKnapsack(scip, cons);
806 
807  /* set coefficients of variables */
808  SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) );
809  for( v = 0; v < nvars; ++v )
810  vals[v] = (SCIP_Real) weights[v];
811 
812  /* handle linear constraint for quadratic constraint update */
813  SCIP_CALL( presolveAddKKTLinearCons(scip, objcons, SCIPconsGetName(cons),
814  vars, vals, lhs, rhs, nvars, varhash, dualconss, ndualconss, naddconss) );
815 
816  /* free buffer array */
817  SCIPfreeBufferArray(scip, &vals);
818  }
819 
820  /* remove knapsack constraints, since they are now redundant; their feasibility is already expressed
821  * by s >= 0, where s is the new slack variable that we introduced for these linear constraints */
822  for( c = nconss-1; c >= 0; --c )
823  {
824  assert( conss[c] != NULL );
825  SCIP_CALL( SCIPdelCons(scip, conss[c]) );
826  ++(*ndelconss);
827  }
828 
829  return SCIP_OKAY;
830 }
831 
832 /** handle set packing constraints for quadratic constraint update, see the documentation of the function
833  * presolveAddKKTLinearCons() for an explanation
834  */
835 static
836 SCIP_RETCODE presolveAddKKTSetppcConss(
837  SCIP* scip, /**< SCIP pointer */
838  SCIP_CONS* objcons, /**< objective constraint */
839  SCIP_HASHMAP* varhash, /**< hash map from variable to index of linear constraint */
840  SCIP_CONS** dualconss, /**< array with dual constraints */
841  int* ndualconss, /**< pointer to store number of dual constraints */
842  int* naddconss, /**< buffer to increase with number of created additional constraints */
843  int* ndelconss /**< buffer to increase with number of deleted constraints */
844  )
845 {
846  SCIP_CONSHDLR* conshdlr;
847  SCIP_CONS** conss;
848  int nconss;
849  int c;
850 
851  assert( scip != NULL );
852  assert( objcons != NULL );
853  assert( varhash != NULL );
854  assert( dualconss != NULL );
855  assert( ndualconss != NULL );
856  assert( naddconss != NULL );
857  assert( ndelconss != NULL );
858 
859  conshdlr = SCIPfindConshdlr(scip, "setppc");
860  if( conshdlr == NULL )
861  return SCIP_OKAY;
862 
863  nconss = SCIPconshdlrGetNConss(conshdlr);
864  conss = SCIPconshdlrGetConss(conshdlr);
865 
866  /* loop through linear constraints */
867  for( c = 0; c < nconss; ++c )
868  {
869  SCIP_SETPPCTYPE type;
870  SCIP_CONS* cons;
871  SCIP_VAR** vars;
872  SCIP_Real* vals;
873  SCIP_Real lhs;
874  SCIP_Real rhs;
875  int nvars;
876  int v;
877 
878  /* get data of constraint */
879  cons = conss[c];
880  assert( cons != NULL );
881 
882  /* get setppc type */
883  type = SCIPgetTypeSetppc(scip, cons);
884  lhs = -SCIPinfinity(scip);
885  rhs = SCIPinfinity(scip);
886  switch( type )
887  {
888  case SCIP_SETPPCTYPE_PARTITIONING:
889  lhs = 1.0;
890  rhs = 1.0;
891  break;
892  case SCIP_SETPPCTYPE_PACKING:
893  rhs = 1.0;
894  break;
895  case SCIP_SETPPCTYPE_COVERING:
896  lhs = 1.0;
897  break;
898  default:
899  SCIPerrorMessage("unknown setppc type\n");
900  return SCIP_INVALIDDATA;
901  }
902 
903  nvars = SCIPgetNVarsSetppc(scip, cons);
904  vars = SCIPgetVarsSetppc(scip, cons);
905 
906  /* set coefficients of variables */
907  SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) );
908  for( v = 0; v < nvars; ++v )
909  vals[v] = 1.0;
910 
911  /* handle linear constraint for quadratic constraint update */
912  SCIP_CALL( presolveAddKKTLinearCons(scip, objcons, SCIPconsGetName(cons),
913  vars, vals, lhs, rhs, nvars, varhash, dualconss, ndualconss, naddconss) );
914 
915  /* free buffer array */
916  SCIPfreeBufferArray(scip, &vals);
917  }
918 
919  /* remove set packing constraints if lhs != rhs, since they are now redundant; their feasibility is already expressed
920  * by s >= 0, where s is the new slack variable that we introduced for these linear constraints */
921  for( c = nconss-1; c >= 0; --c )
922  {
923  assert( conss[c] != NULL );
924 
925  if( SCIPgetTypeSetppc(scip, conss[c]) != SCIP_SETPPCTYPE_PARTITIONING )
926  {
927  assert( SCIPgetTypeSetppc(scip, conss[c]) == SCIP_SETPPCTYPE_PACKING
928  || SCIPgetTypeSetppc(scip, conss[c]) == SCIP_SETPPCTYPE_COVERING );
929 
930  SCIP_CALL( SCIPdelCons(scip, conss[c]) );
931  ++(*ndelconss);
932  }
933  }
934 
935  return SCIP_OKAY;
936 }
937 
938 /** handle varbound constraints for quadratic constraint update, see the documentation of the function
939  * presolveAddKKTLinearCons() for an explanation
940  */
941 static
942 SCIP_RETCODE presolveAddKKTVarboundConss(
943  SCIP* scip, /**< SCIP pointer */
944  SCIP_CONS* objcons, /**< objective constraint */
945  SCIP_HASHMAP* varhash, /**< hash map from variable to index of linear constraint */
946  SCIP_CONS** dualconss, /**< array with dual constraints */
947  int* ndualconss, /**< pointer to store number of dual constraints */
948  int* naddconss, /**< buffer to increase with number of created additional constraints */
949  int* ndelconss /**< buffer to increase with number of deleted constraints */
950  )
951 {
952  SCIP_CONSHDLR* conshdlr;
953  SCIP_CONS** conss;
954  int nconss;
955  int c;
956 
957  assert( scip != NULL );
958  assert( objcons != NULL );
959  assert( varhash != NULL );
960  assert( dualconss != NULL );
961  assert( ndualconss != NULL );
962  assert( naddconss != NULL );
963  assert( ndelconss != NULL );
964 
965  conshdlr = SCIPfindConshdlr(scip, "varbound");
966  if( conshdlr == NULL )
967  return SCIP_OKAY;
968 
969  nconss = SCIPconshdlrGetNConss(conshdlr);
970  conss = SCIPconshdlrGetConss(conshdlr);
971 
972  /* loop through linear constraints */
973  for( c = 0; c < nconss; ++c )
974  {
975  SCIP_CONS* cons;
976  SCIP_VAR** vars;
977  SCIP_Real* vals;
978  SCIP_Real lhs;
979  SCIP_Real rhs;
980  int nvars;
981 
982  /* allocate buffer arrays */
983  SCIP_CALL( SCIPallocBufferArray(scip, &vars, 2) );
984  SCIP_CALL( SCIPallocBufferArray(scip, &vals, 2) );
985 
986  /* get data of constraint */
987  cons = conss[c];
988  assert( cons != NULL );
989 
990  lhs = SCIPgetLhsVarbound(scip, cons);
991  rhs = SCIPgetRhsVarbound(scip, cons);
992  vars[0] = SCIPgetVarVarbound(scip, cons);
993  vars[1] = SCIPgetVbdvarVarbound(scip, cons);
994  vals[0] = 1.0;
995  vals[1] = SCIPgetVbdcoefVarbound(scip, cons);
996  nvars = 2;
997 
998  /* handle linear constraint for quadratic constraint update */
999  SCIP_CALL( presolveAddKKTLinearCons(scip, objcons, SCIPconsGetName(cons),
1000  vars, vals, lhs, rhs, nvars, varhash, dualconss, ndualconss, naddconss) );
1001 
1002  /* free buffer array */
1003  SCIPfreeBufferArray(scip, &vals);
1004  SCIPfreeBufferArray(scip, &vars);
1005  }
1006 
1007  /* remove varbound constraints if lhs != rhs, since they are now redundant; their feasibility is already expressed
1008  * by s >= 0, where s is the new slack variable that we introduced for these linear constraints */
1009  for( c = nconss-1; c >= 0; --c )
1010  {
1011  SCIP_CONS* cons;
1012 
1013  cons = conss[c];
1014  assert( cons != NULL );
1015 
1016  if( ! SCIPisFeasEQ(scip, SCIPgetLhsVarbound(scip, cons), SCIPgetRhsVarbound(scip, cons)) )
1017  {
1018  SCIP_CALL( SCIPdelCons(scip, cons) );
1019  ++(*ndelconss);
1020  }
1021  }
1022 
1023  return SCIP_OKAY;
1024 }
1025 
1026 /** handle logicor constraints for quadratic constraint update, see the documentation of the function
1027  * presolveAddKKTLinearCons() for an explanation
1028  */
1029 static
1030 SCIP_RETCODE presolveAddKKTLogicorConss(
1031  SCIP* scip, /**< SCIP pointer */
1032  SCIP_CONS* objcons, /**< objective constraint */
1033  SCIP_HASHMAP* varhash, /**< hash map from variable to index of linear constraint */
1034  SCIP_CONS** dualconss, /**< array with dual constraints */
1035  int* ndualconss, /**< pointer to store number of dual constraints */
1036  int* naddconss, /**< buffer to increase with number of created additional constraints */
1037  int* ndelconss /**< buffer to increase with number of deleted constraints */
1038  )
1039 {
1040  SCIP_CONSHDLR* conshdlr;
1041  SCIP_CONS** conss;
1042  int nconss;
1043  int c;
1044 
1045  assert( scip != NULL );
1046  assert( objcons != NULL );
1047  assert( varhash != NULL );
1048  assert( dualconss != NULL );
1049  assert( ndualconss != NULL );
1050  assert( naddconss != NULL );
1051  assert( ndelconss != NULL );
1052 
1053  conshdlr = SCIPfindConshdlr(scip, "logicor");
1054  if( conshdlr == NULL )
1055  return SCIP_OKAY;
1056 
1057  nconss = SCIPconshdlrGetNConss(conshdlr);
1058  conss = SCIPconshdlrGetConss(conshdlr);
1059 
1060  /* loop through linear constraints */
1061  for( c = 0; c < nconss; ++c )
1062  {
1063  SCIP_CONS* cons;
1064  SCIP_VAR** vars;
1065  SCIP_Real* vals;
1066  SCIP_Real lhs;
1067  SCIP_Real rhs;
1068  int nvars;
1069  int v;
1070 
1071  /* get data of constraint */
1072  cons = conss[c];
1073  assert( cons != NULL );
1074 
1075  /* get setppc type */
1076  lhs = 1.0;
1077  rhs = SCIPinfinity(scip);
1078 
1079  nvars = SCIPgetNVarsLogicor(scip, cons);
1080  vars = SCIPgetVarsLogicor(scip, cons);
1081 
1082  /* set coefficients of variables */
1083  SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) );
1084  for( v = 0; v < nvars; ++v )
1085  vals[v] = 1.0;
1086 
1087  /* handle linear constraint for quadratic constraint update */
1088  SCIP_CALL( presolveAddKKTLinearCons(scip, objcons, SCIPconsGetName(cons),
1089  vars, vals, lhs, rhs, nvars, varhash, dualconss, ndualconss, naddconss) );
1090 
1091  /* free buffer array */
1092  SCIPfreeBufferArray(scip, &vals);
1093  }
1094 
1095  /* remove logicor constraints, since they are now redundant; their feasibility is already expressed
1096  * by s >= 0, where s is the new slack variable that we introduced for these linear constraints */
1097  for( c = nconss-1; c >= 0; --c )
1098  {
1099  assert( conss[c] != NULL );
1100 
1101  SCIP_CALL( SCIPdelCons(scip, conss[c]) );
1102  ++(*ndelconss);
1103  }
1104 
1105  return SCIP_OKAY;
1106 }
1107 
1108 /** handle aggregated variables for quadratic constraint update @n
1109  * we apply the function presolveAddKKTLinearCons() to the aggregation constraint, see the documentation of this
1110  * function for further information
1111  */
1112 static
1113 SCIP_RETCODE presolveAddKKTAggregatedVars(
1114  SCIP* scip, /**< SCIP pointer */
1115  SCIP_CONS* objcons, /**< objective constraint */
1116  SCIP_VAR** agrvars, /**< aggregated variables */
1117  int nagrvars, /**< number of aggregated variables */
1118  SCIP_HASHMAP* varhash, /**< hash map from variable to index of linear constraint */
1119  SCIP_CONS** dualconss, /**< array with dual constraints */
1120  int* ndualconss, /**< pointer to store number of dual constraints */
1121  int* naddconss /**< buffer to increase with number of created additional constraints */
1122  )
1123 {
1124  int v;
1125 
1126  assert( scip != NULL );
1127  assert( objcons != NULL );
1128  assert( agrvars != NULL );
1129  assert( varhash != NULL );
1130  assert( dualconss != NULL );
1131  assert( ndualconss != NULL );
1132  assert( naddconss != NULL );
1133 
1134  /* loop through variables */
1135  for( v = 0; v < nagrvars; ++v )
1136  {
1137  SCIP_VAR* var;
1138  SCIP_VAR** vars = NULL;
1139  SCIP_Real* vals = NULL;
1140  SCIP_Real lhs;
1141  SCIP_Real rhs;
1142  int nvars;
1143 
1144  var = agrvars[v];
1145 
1146  if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_AGGREGATED )
1147  {
1148  SCIP_Real constant;
1149 
1150  SCIP_CALL( SCIPallocBufferArray(scip, &vars, 2) );
1151  SCIP_CALL( SCIPallocBufferArray(scip, &vals, 2) );
1152 
1153  /* get aggregation variable */
1154  constant = SCIPvarGetAggrConstant(var);
1155  vars[0] = SCIPvarGetAggrVar(var);
1156  vals[0] = SCIPvarGetAggrScalar(var);
1157  vars[1] = var;
1158  vals[1] = -1.0;
1159  lhs = -constant;
1160  rhs = -constant;
1161  nvars = 2;
1162  }
1163  else if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR )
1164  {
1165  SCIP_Real* scalars;
1166  SCIP_VAR** multvars;
1167  SCIP_Real constant;
1168  int nmultvars;
1169  int nbuffer;
1170  int j;
1171 
1172  nmultvars = SCIPvarGetMultaggrNVars(var);
1173  nbuffer = nmultvars+1;
1174 
1175  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nbuffer) );
1176  SCIP_CALL( SCIPallocBufferArray(scip, &vals, nbuffer) );
1177 
1178  /* get aggregation variables */
1179  multvars = SCIPvarGetMultaggrVars(var);
1180  scalars = SCIPvarGetMultaggrScalars(var);
1181  constant = SCIPvarGetMultaggrConstant(var);
1182 
1183  /* add multi-aggregated variables to array */
1184  for( j = 0; j < nmultvars; ++j )
1185  {
1186  vars[j] = multvars[j];
1187  vals[j] = scalars[j];
1188  }
1189 
1190  /* add new variable to array */
1191  vars[nmultvars] = var;
1192  vals[nmultvars] = -1.0;
1193  lhs = -constant;
1194  rhs = -constant;
1195  nvars = nmultvars + 1;
1196  }
1197  else if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_NEGATED )
1198  {
1199  SCIP_VAR* negvar;
1200  SCIP_Real negconst;
1201 
1202  /* get negation variable and negation offset */
1203  negvar = SCIPvarGetNegationVar(var);
1204  negconst = SCIPvarGetNegationConstant(var);
1205 
1206  SCIP_CALL( SCIPallocBufferArray(scip, &vars, 2) );
1207  SCIP_CALL( SCIPallocBufferArray(scip, &vals, 2) );
1208 
1209  vars[0] = negvar;
1210  vars[1] = var;
1211  vals[0] = 1.0;
1212  vals[1] = 1.0;
1213  lhs = negconst;
1214  rhs = negconst;
1215  nvars = 2;
1216  }
1217  else if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED )
1218  {
1219  SCIP_Real lb;
1220  SCIP_Real ub;
1221 
1222  lb = SCIPvarGetLbGlobal(var);
1223  ub = SCIPvarGetUbGlobal(var);
1224  assert( SCIPisFeasEQ(scip, lb, ub) );
1225 
1226  if( SCIPisFeasZero(scip, lb) && SCIPisFeasZero(scip, ub) )
1227  continue;
1228  else
1229  {
1230  SCIP_CALL( SCIPallocBufferArray(scip, &vars, 1) );
1231  SCIP_CALL( SCIPallocBufferArray(scip, &vals, 1) );
1232 
1233  vars[0] = var;
1234  vals[0] = 1.0;
1235  lhs = lb;
1236  rhs = lb;
1237  nvars = 1;
1238  }
1239  }
1240  else
1241  {
1242  SCIPerrorMessage("unexpected variable status\n");
1243  return SCIP_ERROR;
1244  }
1245 
1246  if( nvars > 0 )
1247  {
1248  /* handle aggregation constraint for quadratic constraint update */
1249  SCIP_CALL( presolveAddKKTLinearCons(scip, objcons, SCIPvarGetName(var),
1250  vars, vals, lhs, rhs, nvars, varhash, dualconss, ndualconss, naddconss) );
1251  }
1252 
1253  SCIPfreeBufferArrayNull(scip, &vals);
1254  SCIPfreeBufferArrayNull(scip, &vars);
1255  }
1256 
1257  return SCIP_OKAY;
1258 }
1259 
1260 /** handle bilinear terms of quadratic constraint for quadratic constraint update
1261  *
1262  * For the two variables of each bilinear term
1263  * 1. create the dual constraints (i.e., the two rows of \f$Q x + c + A^T \mu = 0\f$) associated to these variables, if not
1264  * done already
1265  * 2. create the dual variables and the complementarity constraints for the lower and upper bound constraints of the two
1266  * variables of the bilinear term, if not done already
1267  * 3. add the coefficient \f$Q_{ij}\f$ of the bilinear term to the dual constraint
1268  *
1269  * for steps 1 and 2 see the documentation of createKKTDualCons() for further information.
1270  **/
1271 static
1272 SCIP_RETCODE presolveAddKKTQuadBilinearTerms(
1273  SCIP* scip, /**< SCIP pointer */
1274  SCIP_CONS* objcons, /**< objective constraint */
1275  SCIP_BILINTERM* bilinterms, /**< bilinear terms of quadratic constraint */
1276  int nbilinterms, /**< number of bilinear terms of quadratic constraint */
1277  SCIP_HASHMAP* varhash, /**< hash map from variable to index of linear constraint */
1278  SCIP_Real scale, /**< scale factor of quadratic constraint */
1279  SCIP_CONS** dualconss, /**< array with dual constraints */
1280  int* ndualconss, /**< pointer to store number of dual constraints */
1281  int* naddconss /**< buffer to increase with number of created additional constraints */
1282  )
1283 {
1284  int j;
1285 
1286  assert( scip != NULL );
1287  assert( objcons != NULL );
1288  assert( varhash != NULL );
1289  assert( dualconss != NULL );
1290  assert( ndualconss != NULL );
1291  assert( naddconss != NULL );
1292 
1293  /* return if there are no bilinear terms */
1294  if( bilinterms == NULL )
1295  return SCIP_OKAY;
1296 
1297  /* loop through bilinear terms of quadratic constraint */
1298  for( j = 0; j < nbilinterms; ++j )
1299  {
1300  int i;
1301 
1302  /* quadratic matrix has to be symmetric; therefore, split bilinear terms into two parts */
1303  for( i = 0; i < 2; ++i )
1304  {
1305  SCIP_CONS* dualcons = NULL; /* dual constraint associated to variable */
1306  SCIP_VAR* bilvar1;
1307  SCIP_VAR* bilvar2;
1308 
1309  if( i == 0 )
1310  {
1311  bilvar1 = bilinterms[j].var1;
1312  bilvar2 = bilinterms[j].var2;
1313  }
1314  else
1315  {
1316  bilvar1 = bilinterms[j].var2;
1317  bilvar2 = bilinterms[j].var1;
1318  }
1319 
1320  /* create/get dual constraint associated to variable 'bilvar1';
1321  * if variable does not already exist in hashmap then create dual variables for its bounds */
1322  SCIP_CALL( createKKTDualCons(scip, objcons, bilvar1, varhash, dualconss, ndualconss, &dualcons, naddconss) );
1323  assert( dualcons != NULL );
1324 
1325  /* add variable to dual constraint */
1326  assert( ! SCIPisFeasZero(scip, scale) );
1327  SCIP_CALL( SCIPaddCoefLinear(scip, dualcons, bilvar2, bilinterms[j].coef / scale) );
1328  }
1329  }
1330 
1331  return SCIP_OKAY;
1332 }
1333 
1334 /** handle quadratic terms of quadratic constraint for quadratic constraint update
1335  *
1336  * For each quadratic term variable
1337  * 1. create the dual constraint (i.e., a row of \f$Q x + c + A^T \mu = 0\f$) associated to this variable, if not done
1338  * already
1339  * 2. create the dual variables and the complementarity constraints for the lower and upper bound constraints of this
1340  * variable, if not done already
1341  * 3. add the coefficient \f$Q_{ii}\f$ of this variable to the dual constraint
1342  *
1343  * for steps 1 and 2 see the documentation of createKKTDualCons() for further information.
1344  **/
1345 static
1346 SCIP_RETCODE presolveAddKKTQuadQuadraticTerms(
1347  SCIP* scip, /**< SCIP pointer */
1348  SCIP_CONS* objcons, /**< objective constraint */
1349  SCIP_QUADVARTERM* quadterms, /**< quadratic terms of quadratic constraint */
1350  int nquadterms, /**< number of quadratic terms of quadratic constraint */
1351  SCIP_HASHMAP* varhash, /**< hash map from variable to index of linear constraint */
1352  SCIP_Real scale, /**< scale factor of quadratic constraint */
1353  SCIP_CONS** dualconss, /**< array with dual constraints */
1354  int* ndualconss, /**< pointer to store number of dual constraints */
1355  int* naddconss /**< buffer to increase with number of created additional constraints */
1356  )
1357 {
1358  int j;
1359 
1360  assert( scip != NULL );
1361  assert( objcons != NULL );
1362  assert( varhash != NULL );
1363  assert( dualconss != NULL );
1364  assert( ndualconss != NULL );
1365  assert( naddconss != NULL );
1366 
1367  /* return if there are no quadratic terms */
1368  if( quadterms == NULL )
1369  return SCIP_OKAY;
1370 
1371  /* loop through quadratic terms */
1372  for( j = 0; j < nquadterms; ++j )
1373  {
1374  SCIP_CONS* dualcons = NULL; /* dual constraint associated to variable */
1375  SCIP_VAR* quadvar;
1376 
1377  quadvar = quadterms[j].var;
1378 
1379  /* create/get dual constraint associated to variable 'bilvar1';
1380  * if variable does not already exist in hashmap then create dual variables for its bounds */
1381  SCIP_CALL( createKKTDualCons(scip, objcons, quadvar, varhash, dualconss, ndualconss, &dualcons, naddconss) );
1382  assert( dualcons != NULL );
1383 
1384  /* add variable to dual constraint */
1385  assert( ! SCIPisFeasZero(scip, scale) );
1386  SCIP_CALL( SCIPaddCoefLinear(scip, dualcons, quadvar, (SCIP_Real) quadterms[j].sqrcoef * 2 / scale) );
1387  }
1388 
1389  return SCIP_OKAY;
1390 }
1391 
1392 /** handle linear terms of quadratic constraint for quadratic constraint update
1393  *
1394  * For each linear term variable
1395  * 1. create the dual constraint (i.e., a row of \f$Q x + c + A^T \mu = 0\f$) associated to this variable, if not done
1396  * already
1397  * 2. create the dual variables and the complementarity constraints for the lower and upper bound constraints of this
1398  * variable, if not done already
1399  * 3. add the right hand side \f$-c_i\f$ to the dual constraint
1400  * 4. add \f$c_i\f$ to the objective constraint \f$1/2 ( c^T x + b^T \mu) = t\f$, where t is the objective variable
1401  *
1402  * for steps 1 and 2 see the documentation of createKKTDualCons() for further information.
1403  **/
1404 static
1405 SCIP_RETCODE presolveAddKKTQuadLinearTerms(
1406  SCIP* scip, /**< SCIP pointer */
1407  SCIP_CONS* objcons, /**< objective constraint */
1408  SCIP_VAR** lintermvars, /**< linear terms of quadratic constraint */
1409  SCIP_Real* lintermcoefs, /**< coefficients of linear terms of quadratic constraint */
1410  int nlintermvars, /**< number of linear terms of quadratic constraints */
1411  SCIP_QUADVARTERM* quadterms, /**< quadratic terms of quadratic constraint */
1412  int nquadterms, /**< number of quadratic terms of quadratic constraint */
1413  SCIP_HASHMAP* varhash, /**< hash map from variable to index of linear constraint */
1414  SCIP_VAR* objvar, /**< variable of objective function */
1415  SCIP_Real scale, /**< scale factor of quadratic constraint */
1416  SCIP_CONS** dualconss, /**< array with dual constraints */
1417  int* ndualconss, /**< pointer to store number of dual constraints */
1418  int* naddconss /**< buffer to increase with number of created additional constraints */
1419  )
1420 {
1421  int j;
1422 
1423  assert( scip != NULL );
1424  assert( objcons != NULL );
1425  assert( lintermcoefs != NULL );
1426  assert( varhash != NULL );
1427  assert( objvar != NULL );
1428  assert( dualconss != NULL );
1429  assert( ndualconss != NULL );
1430  assert( naddconss != NULL );
1431 
1432  /* loop through linear terms of quadratic constraint */
1433  if( lintermvars != NULL )
1434  {
1435  assert( lintermcoefs != NULL );
1436  for( j = 0; j < nlintermvars; ++j )
1437  {
1438  SCIP_VAR* var;
1439 
1440  var = lintermvars[j];
1441 
1442  if( var != objvar )
1443  {
1444  SCIP_CONS* dualcons = NULL; /* dual constraint associated to variable */
1445  SCIP_Real coef;
1446 
1447  /* create/get dual constraint associated to variable;
1448  * if variable does not already exist in hashmap then create dual variables for its bounds */
1449  SCIP_CALL( createKKTDualCons(scip, objcons, var, varhash, dualconss, ndualconss, &dualcons, naddconss) );
1450  assert( dualcons != NULL );
1451 
1452  /* get coefficient of variable in quadratic constraint */
1453  coef = lintermcoefs[j];
1454 
1455  /* change lhs and rhs of dual constraint */
1456  assert( ! SCIPisFeasZero(scip, scale) );
1457  SCIP_CALL( SCIPchgLhsLinear(scip, dualcons, SCIPgetLhsLinear(scip, dualcons) - coef / scale) );
1458  SCIP_CALL( SCIPchgRhsLinear(scip, dualcons, SCIPgetRhsLinear(scip, dualcons) - coef / scale) );
1459 
1460  /* add variable to objective constraint */
1461  SCIP_CALL( SCIPaddCoefLinear(scip, objcons, var, coef / (scale * 2)) );
1462  }
1463  }
1464  }
1465 
1466  /* loop through linear terms that are part of a quadratic term of quadratic constraint */
1467  if( quadterms != NULL )
1468  {
1469  for( j = 0; j < nquadterms; ++j )
1470  {
1471  SCIP_CONS* dualcons;
1472  SCIP_Real coef;
1473  SCIP_VAR* var;
1474  int ind;
1475 
1476  var = quadterms[j].var;
1477  coef = quadterms[j].lincoef;
1478  assert( var != objvar );
1479 
1480  /* get dual constraint associated to variable (has already been created in function
1481  * presolveAddKKTQuadQuadraticTerms() */
1482  assert( SCIPhashmapExists(varhash, var) );
1483  ind = SCIPhashmapGetImageInt(varhash, var);
1484  dualcons = dualconss[ind];
1485  assert( dualcons != NULL );
1486 
1487  /* change lhs and rhs of dual constraint */
1488  assert( ! SCIPisFeasZero(scip, scale) );
1489  SCIP_CALL( SCIPchgLhsLinear(scip, dualcons, SCIPgetLhsLinear(scip, dualcons) -coef / scale) );
1490  SCIP_CALL( SCIPchgRhsLinear(scip, dualcons, SCIPgetRhsLinear(scip, dualcons) -coef / scale) );
1491 
1492  /* add variable to objective constraint */
1493  SCIP_CALL( SCIPaddCoefLinear(scip, objcons, var, coef / (scale * 2)) );
1494  }
1495  }
1496 
1497  return SCIP_OKAY;
1498 }
1499 
1500 /** checks for a given constraint whether it is the objective function of a (mixed-binary) quadratic program
1501  * \f[
1502  * \begin{array}{ll}
1503  * \min & z \\
1504  * s.t. & x^T Q x + c^T x + d <= z \\
1505  * & A x \leq b, \\
1506  * & x \in \{0, 1\}^{p} \times R^{n-p},
1507  * \end{array}
1508  * \f]
1509  * which is equivalent to
1510  * \f[
1511  * \begin{array}{ll}
1512  * \min & x^T Q x + c^T x + d \\
1513  * s.t. & A x \leq b, \\
1514  * & x \in \{0, 1\}^{p} \times R^{n-p}.
1515  * \end{array}
1516  * \f]
1517  *
1518  *
1519  * We check whether
1520  * 1. there is a single quadratic constraint that can be written as \f$x^T Q x + c^T x + d \leq t\f$
1521  * 2. all other constraints are linear
1522  * 3. all integer variables are binary if allowbinary = TRUE, or all variables are continuous if allowbinary = FALSE
1523  * 4. t is the only variable in the objective and doesn't appear in any other constraint
1524  */
1525 static
1526 SCIP_RETCODE checkConsQuadraticProblem(
1527  SCIP* scip, /**< SCIP data structure */
1528  SCIP_CONSHDLR* quadconshdlr, /**< constraint handler data structure */
1529  SCIP_CONS* cons, /**< quadratic constraint */
1530  SCIP_Bool allowbinary, /**< if TRUE then allow binary variables in the problem, if FALSE then all
1531  * variables have to be continuous */
1532  SCIP_VAR** objvar, /**< pointer to store the objective variable @p z */
1533  SCIP_Real* scale, /**< pointer to store the value by which we have to scale the quadratic
1534  * constraint such that the objective variable @p z has coefficient -1 */
1535  SCIP_Real* objrhs, /**< pointer to store the right hand side @p -d of the objective constraint */
1536  SCIP_Bool* isqp /**< pointer to store whether the problem is a (mixed-binary) QP */
1537  )
1538 {
1539  SCIP_CONSHDLR* conshdlr;
1540  SCIP_VAR** lintermvars;
1541  SCIP_Real* lintermcoefs;
1542  int nconss = 0;
1543  SCIP_Real quadlhs;
1544  SCIP_Real quadrhs;
1545  SCIP_Real coef;
1546  SCIP_Real obj;
1547  int mayincrease;
1548  int maydecrease;
1549  int objind = -1;
1550 
1551  SCIP_VAR* origObjVar;
1552  SCIP_Real origObjConstant = 0.0;
1553  SCIP_Real origObjScalar = 1.0;
1554  SCIP_Real origObjUb;
1555  SCIP_Real origObjLb;
1556 
1557  *objrhs = 0.0;
1558  *scale = 0.0;
1559  *isqp = FALSE;
1560  *objvar = NULL;
1561 
1562  /* desired structure: there exists only one variable with nonzero objective value; this is the objective variable 'z' */
1563  if( SCIPgetNObjVars(scip) != 1 )
1564  return SCIP_OKAY;
1565 
1566  /* desired structure: all integer variables are binary; if the parameter 'allowbinary' is set to FALSE, then all
1567  * variables have to be continuous */
1568  if( SCIPgetNIntVars(scip) > 0 || ( ! allowbinary && SCIPgetNBinVars(scip) > 0 ) )
1569  return SCIP_OKAY;
1570 
1571  /* desired structure: there exists only one quadratic constraint */
1572  if( SCIPconshdlrGetNConss(quadconshdlr) != 1 )
1573  return SCIP_OKAY;
1574 
1575  /* desired structure: the constraint has to take one of the three forms
1576  * i) x^T Q x + c^T x <= d
1577  * ii) x^T Q x + c^T x >= d
1578  * iii) x^T Q x + c^T x == d
1579  * the case a <= x^T Q x + c^T x <= d with 'a' and 'd' finite and a != d is not allowed.
1580  */
1581  quadlhs = SCIPgetLhsQuadratic(scip, cons);
1582  quadrhs = SCIPgetRhsQuadratic(scip, cons);
1583  if( ! SCIPisFeasEQ(scip, quadlhs, quadrhs) && ! SCIPisInfinity(scip, -quadlhs) && ! SCIPisInfinity(scip, quadrhs) )
1584  return SCIP_OKAY;
1585 
1586  /* get number of linear constraints (including special cases of linear constraints) */
1587  conshdlr = SCIPfindConshdlr(scip, "linear");
1588  if( conshdlr != NULL )
1589  nconss += SCIPconshdlrGetNConss(conshdlr);
1590 
1591  conshdlr = SCIPfindConshdlr(scip, "setppc");
1592  if( conshdlr != NULL )
1593  nconss += SCIPconshdlrGetNConss(conshdlr);
1594 
1595  conshdlr = SCIPfindConshdlr(scip, "knapsack");
1596  if( conshdlr != NULL )
1597  nconss += SCIPconshdlrGetNConss(conshdlr);
1598 
1599  conshdlr = SCIPfindConshdlr(scip, "varbound");
1600  if( conshdlr != NULL )
1601  nconss += SCIPconshdlrGetNConss(conshdlr);
1602 
1603  conshdlr = SCIPfindConshdlr(scip, "logicor");
1604  if( conshdlr != NULL )
1605  nconss += SCIPconshdlrGetNConss(conshdlr);
1606 
1607  /* desired structure: all the nonquadratic constraints are linear constraints */
1608  if( nconss != SCIPgetNConss(scip) - 1 )
1609  return SCIP_OKAY;
1610 
1611  /* get variables that are in the linear term of the quadratic constraint */
1612  lintermvars = SCIPgetLinearVarsQuadratic(scip, cons);
1613  lintermcoefs = SCIPgetCoefsLinearVarsQuadratic(scip, cons);
1614 
1615  /* compute the objective shift of the QP. Note that
1616  *
1617  * min z s.t. x^T Q x + c^T x <= d + z
1618  * Ax <= b
1619  *
1620  * is equivalent to
1621  *
1622  * min x^T Q x + c^T x - d s.t. Ax <= b
1623  *
1624  * Here, -d is the objective shift. We define b to be the right hand side of the objective constraint.
1625  */
1626  if( ! SCIPisInfinity(scip, -quadlhs) )
1627  *objrhs = quadlhs;
1628  else
1629  *objrhs = quadrhs;
1630  assert( ! SCIPisInfinity(scip, REALABS(*objrhs)) );
1631 
1632  /* search for the objective variable 'objvar' in the linear term of quadratic constraint (it is already known that
1633  * at most one variable has a nonzero objective value); additionally, check the sign of the objective variable */
1634  maydecrease = SCIPgetLinvarMayDecreaseQuadratic(scip, cons);
1635  mayincrease = SCIPgetLinvarMayIncreaseQuadratic(scip, cons);
1636  if( maydecrease < 0 && mayincrease < 0 )
1637  return SCIP_OKAY;
1638  else if( maydecrease >= 0 )
1639  {
1640  objind = maydecrease;
1641 
1642  /* if both mayincrease and maydecrese are nonnegative, then check objective coefficient */
1643  if( mayincrease >= 0 && SCIPisFeasZero(scip, SCIPvarGetObj(lintermvars[maydecrease])) )
1644  objind = mayincrease;
1645  }
1646  else
1647  objind = mayincrease;
1648  assert( objind < SCIPgetNLinearVarsQuadratic(scip, cons) );
1649 
1650  *objvar = lintermvars[objind];
1651  coef = lintermcoefs[objind];
1652  obj = SCIPvarGetObj(*objvar);
1653 
1654  /* check sign of coefficient */
1655  if( SCIPisFeasPositive(scip, obj)
1656  && ( ( SCIPisFeasNegative(scip, coef) && SCIPisFeasEQ(scip, quadrhs, *objrhs) )
1657  || ( SCIPisFeasPositive(scip, coef) && SCIPisFeasEQ(scip, quadlhs, *objrhs) )
1658  )
1659  )
1660  {
1661  *scale = -coef; /* value by which we have to scale the quadratic constraint such that the objective variable
1662  * has coefficient -1 */
1663  }
1664  else if( SCIPisFeasNegative(scip, obj)
1665  && ( ( SCIPisFeasNegative(scip, coef) && SCIPisFeasEQ(scip, quadlhs, *objrhs) )
1666  || ( SCIPisFeasPositive(scip, coef) && SCIPisFeasEQ(scip, quadrhs, *objrhs) )
1667  )
1668  )
1669  {
1670  *scale = coef; /* value by which we have to scale the quadratic constraint such that the objective variable
1671  * has coefficient 1 */
1672  }
1673  else
1674  return SCIP_OKAY;
1675  assert( *objvar != NULL && ! SCIPisFeasZero(scip, SCIPvarGetObj(*objvar)) );
1676  assert( ! SCIPisFeasZero(scip, *scale) );
1677 
1678  /* scale the right hand side of the objective constraint */
1679  *objrhs = (*objrhs)/(*scale); /*lint !e414*/
1680 
1681  /* check whether 'objvar' is part of a linear constraint; if this is true then return
1682  * whether 'objvar' is part of a linear constraint can be deduced from the variable locks */
1683  if( SCIPisFeasEQ(scip, quadlhs, quadrhs) )
1684  {
1685  if( SCIPvarGetNLocksDownType(*objvar, SCIP_LOCKTYPE_MODEL) != 1
1686  || SCIPvarGetNLocksUpType(*objvar, SCIP_LOCKTYPE_MODEL) != 1 )
1687  return SCIP_OKAY;
1688  }
1689  else
1690  {
1691  assert( SCIPisInfinity(scip, -quadlhs) || SCIPisInfinity(scip, quadrhs) );
1692 
1693  if( ( SCIPvarGetNLocksDownType(*objvar, SCIP_LOCKTYPE_MODEL) != 1
1694  || SCIPvarGetNLocksUpType(*objvar, SCIP_LOCKTYPE_MODEL) != 0 )
1695  && ( SCIPvarGetNLocksDownType(*objvar, SCIP_LOCKTYPE_MODEL) != 0
1696  || SCIPvarGetNLocksUpType(*objvar, SCIP_LOCKTYPE_MODEL) != 1 ) )
1697  return SCIP_OKAY;
1698  }
1699 
1700  /* check bounds of original objective variable */
1701  origObjVar = lintermvars[objind];
1702  SCIP_CALL( SCIPvarGetOrigvarSum(&origObjVar, &origObjScalar, &origObjConstant) );
1703  if (origObjVar == NULL)
1704  return SCIP_OKAY;
1705 
1706  if (SCIPisFeasPositive(scip, origObjScalar))
1707  {
1708  origObjUb = SCIPvarGetUbOriginal(origObjVar);
1709  origObjLb = SCIPvarGetLbOriginal(origObjVar);
1710  }
1711  else
1712  {
1713  origObjUb = -SCIPvarGetLbOriginal(origObjVar);
1714  origObjLb = -SCIPvarGetUbOriginal(origObjVar);
1715  origObjScalar *= -1;
1716  origObjConstant *= -1;
1717  }
1718 
1719  /* not every optimal solution of the problem is a KKT point if the objective variable is bounded */
1720  if( SCIPisFeasPositive(scip, obj))
1721  {
1722  if ( !SCIPisInfinity(scip, -origObjLb))
1723  return SCIP_OKAY;
1724  if ( !SCIPisInfinity(scip, origObjUb)
1725  && !SCIPisFeasLE(scip, quadrhs/coef, (origObjUb-origObjConstant)/origObjScalar) )
1726  return SCIP_OKAY;
1727  }
1728  else
1729  {
1730  if ( !SCIPisInfinity(scip, origObjUb) )
1731  return SCIP_OKAY;
1732  if ( !SCIPisInfinity(scip, -origObjLb)
1733  && !SCIPisFeasGE(scip, quadlhs/coef, (origObjLb-origObjConstant)/origObjScalar) )
1734  return SCIP_OKAY;
1735  }
1736 
1737  *isqp = TRUE;
1738 
1739  return SCIP_OKAY;
1740 }
1741 
1742 /*
1743  * Callback methods of presolver
1744  */
1745 
1746 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
1747 static
1748 SCIP_DECL_PRESOLCOPY(presolCopyQPKKTref)
1749 { /*lint --e{715}*/
1750  assert(scip != NULL);
1751  assert(presol != NULL);
1752  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
1753 
1754  /* call inclusion method of presolver */
1755  SCIP_CALL( SCIPincludePresolQPKKTref(scip) );
1756 
1757  return SCIP_OKAY;
1758 }
1759 
1760 
1761 /** destructor of presolver to free user data (called when SCIP is exiting) */
1762 static
1763 SCIP_DECL_PRESOLFREE(presolFreeQPKKTref)
1764 { /*lint --e{715}*/
1765  SCIP_PRESOLDATA* presoldata;
1766 
1767  /* free presolver data */
1768  presoldata = SCIPpresolGetData(presol);
1769  assert(presoldata != NULL);
1770 
1771  SCIPfreeBlockMemory(scip, &presoldata);
1772  SCIPpresolSetData(presol, NULL);
1773 
1774  return SCIP_OKAY;
1775 }
1776 
1777 
1778 /** execution method of presolver */
1779 static
1780 SCIP_DECL_PRESOLEXEC(presolExecQPKKTref)
1781 { /*lint --e{715}*/
1782  SCIP_PRESOLDATA* presoldata;
1783  SCIP_CONSHDLR* linconshdlr;
1784  SCIP_CONSHDLR* quadconshdlr;
1785  SCIP_CONS** conss;
1786  SCIP_CONS* cons;
1787 
1788  SCIP_QUADVARTERM* quadterms;
1789  SCIP_BILINTERM* bilinterms;
1790  int nquadterms;
1791  int nbilinterms;
1792 
1793  SCIP_VAR** lintermvars;
1794  SCIP_Real* lintermcoefs;
1795  int nlintermvars;
1796 
1797  SCIP_CONS** savelinconss = NULL;
1798  SCIP_CONS** linconss = NULL;
1799  int nlinconss = 0;
1800 
1801  SCIP_HASHMAP* varhash; /* hash map from variable to index of dual constraint */
1802  SCIP_CONS** dualconss; /* constraints associated to the Lagrangean function */
1803  int ndualconss = 0;
1804 
1805  SCIP_CONS* objcons;
1806  SCIP_VAR* objvar;
1807  SCIP_Real scale;
1808  SCIP_Real objrhs;
1809  SCIP_Bool isqp;
1810  int j;
1811 
1812  assert( scip != NULL );
1813  assert( naddconss != NULL );
1814  assert( ndelconss != NULL );
1815 
1816  /* desired structure: there exists only one quadratic constraint */
1817  quadconshdlr = SCIPfindConshdlr(scip,"quadratic");
1818  if( quadconshdlr == NULL || SCIPconshdlrGetNConss(quadconshdlr) != 1 )
1819  return SCIP_OKAY;
1820 
1821  /* get quadratic constraint */
1822  conss = SCIPconshdlrGetConss(quadconshdlr);
1823  cons = conss[0];
1824  assert( cons != NULL );
1825 
1826  SCIPdebugMsg(scip, "tries to add the KKT conditions for constraint <%s>\n", SCIPconsGetName(cons));
1827 
1828  /* get presolver data */
1829  presoldata = SCIPpresolGetData(presol);
1830  assert(presoldata != NULL);
1831 
1832  /* desired structure: matrix associated to quadratic constraint is indefinite;
1833  * otherwise, the problem usually can be solved faster by standard methods. */
1834  SCIP_CALL( SCIPcheckCurvatureQuadratic(scip, cons) );
1835  if( ! presoldata->updatequadindef && ( SCIPisConvexQuadratic(scip, cons) || SCIPisConcaveQuadratic(scip, cons) ) )
1836  {
1837  SCIPdebugMsg(scip, "quadratic constraint update failed, since matrix associated to quadratic constraint <%s> is not \
1838  indefinite.\n", SCIPconsGetName(cons) );
1839  return SCIP_OKAY;
1840  }
1841 
1842  /* first, check whether the problem is equivalent to
1843  *
1844  * min z
1845  * s.t. x^T Q x + c^T x <= b + z
1846  * x \in \{0, 1\}^{p} \times R^{n-p}.
1847  *
1848  */
1849  SCIP_CALL( checkConsQuadraticProblem(scip, quadconshdlr, cons, presoldata->addkktbinary, &objvar, &scale, &objrhs, &isqp) );
1850  if( ! isqp )
1851  return SCIP_OKAY;
1852  assert( objvar != NULL );
1853 
1854  /* get constraint handler data of linear constraints */
1855  linconshdlr = SCIPfindConshdlr(scip, "linear");
1856 
1857  /* get linear constraints and number of linear constraints */
1858  if( linconshdlr != NULL )
1859  {
1860  nlinconss = SCIPconshdlrGetNConss(linconshdlr);
1861  linconss = SCIPconshdlrGetConss(linconshdlr);
1862  }
1863 
1864  /* get variables that are in the linear term of the quadratic constraint */
1865  nlintermvars = SCIPgetNLinearVarsQuadratic(scip, cons);
1866  lintermvars = SCIPgetLinearVarsQuadratic(scip, cons);
1867  lintermcoefs = SCIPgetCoefsLinearVarsQuadratic(scip, cons);
1868 
1869  /* get bilinear terms */
1870  bilinterms = SCIPgetBilinTermsQuadratic(scip, cons);
1871  nbilinterms = SCIPgetNBilinTermsQuadratic(scip, cons);
1872 
1873  /* get quadratic terms */
1874  quadterms = SCIPgetQuadVarTermsQuadratic(scip, cons);
1875  nquadterms = SCIPgetNQuadVarTermsQuadratic(scip, cons);
1876 
1877  /* the update is only valid if a finite optimal solution of the problem exists,
1878  * since only finite optimal solutions satisfy the KKT conditions;
1879  * we check whether all variables have finite bounds, otherwise we return */
1880  if( presoldata->updatequadbounded )
1881  {
1882  /* check linear term variables */
1883  for( j = 0; j < nlintermvars; ++j )
1884  {
1885  SCIP_VAR* var;
1886 
1887  var = lintermvars[j];
1888  if( var != objvar &&
1889  ( SCIPisInfinity(scip, -SCIPvarGetLbGlobal(var)) || SCIPisInfinity(scip, SCIPvarGetUbGlobal(var)) )
1890  )
1891  {
1892  SCIPdebugMsg(scip, "failed adding the KKT conditions, since not all variables to quadratic constraint <%s> are \
1893  bounded.\n", SCIPconsGetName(cons) );
1894  return SCIP_OKAY;
1895  }
1896  }
1897 
1898  /* check linear term variables */
1899  for( j = 0; j < nbilinterms; ++j )
1900  {
1901  SCIP_VAR* bilvar1;
1902  SCIP_VAR* bilvar2;
1903 
1904  bilvar1 = bilinterms[j].var1;
1905  bilvar2 = bilinterms[j].var2;
1906  if( ( bilvar1 != objvar && ( SCIPisInfinity(scip, -SCIPvarGetLbGlobal(bilvar1)) || SCIPisInfinity(scip, SCIPvarGetUbGlobal(bilvar1)) ) )
1907  || ( bilvar2 != objvar && ( SCIPisInfinity(scip, -SCIPvarGetLbGlobal(bilvar2)) || SCIPisInfinity(scip, SCIPvarGetUbGlobal(bilvar2)) ) ) )
1908  {
1909  SCIPdebugMsg(scip, "failed adding the KKT conditions, since not all variables to quadratic constraint <%s> \
1910  are bounded.\n", SCIPconsGetName(cons) );
1911  return SCIP_OKAY;
1912  }
1913  }
1914 
1915  /* check quadratic term variables */
1916  for( j = 0; j < nquadterms; ++j )
1917  {
1918  SCIP_VAR* var;
1919 
1920  var = quadterms[j].var;
1921  if( var != objvar
1922  && ( SCIPisInfinity(scip, -SCIPvarGetLbGlobal(var)) || SCIPisInfinity(scip, SCIPvarGetUbGlobal(var)) )
1923  )
1924  {
1925  SCIPdebugMsg(scip, "failed adding the KKT conditions, since not all variables to quadratic constraint <%s> \
1926  are bounded.\n", SCIPconsGetName(cons) );
1927  return SCIP_OKAY;
1928  }
1929  }
1930  }
1931 
1932  /* add KKT constraints */
1933 
1934  /* set up hash map */
1935  SCIP_CALL( SCIPhashmapCreate(&varhash, SCIPblkmem(scip), SCIPgetNVars(scip) + SCIPgetNFixedVars(scip)) );
1936 
1937  /* allocate buffer array */
1938  SCIP_CALL( SCIPallocBufferArray(scip, &dualconss, 2 * SCIPgetNVars(scip) + 2 * SCIPgetNFixedVars(scip)) ); /*lint !e647*/
1939 
1940  /* duplicate linconss for later use, since in the following, we create new linear constraints */
1941  if( linconss != NULL )
1942  {
1943  SCIP_CALL( SCIPduplicateBufferArray(scip, &savelinconss, linconss, nlinconss) );
1944  }
1945 
1946  /* create new objective constraint */
1947  SCIP_CALL( SCIPcreateConsBasicLinear(scip, &objcons, "objcons", 0, NULL, NULL, objrhs, objrhs) );
1948  if( SCIPisFeasNegative(scip, SCIPvarGetObj(objvar)) )
1949  {
1950  SCIP_CALL( SCIPaddCoefLinear(scip, objcons, objvar, 1.0) );
1951  }
1952  else
1953  {
1954  SCIP_CALL( SCIPaddCoefLinear(scip, objcons, objvar, -1.0) );
1955  }
1956 
1957  /* handle linear constraints */
1958  if( savelinconss != NULL )
1959  {
1960  SCIP_CALL( presolveAddKKTLinearConss(scip, objcons, savelinconss, nlinconss, varhash, dualconss, &ndualconss,
1961  naddconss, ndelconss) );
1962  }
1963 
1964  /* handle set packing constraints */
1965  SCIP_CALL( presolveAddKKTSetppcConss(scip, objcons, varhash, dualconss, &ndualconss, naddconss, ndelconss) );
1966 
1967  /* handle knapsack constraints */
1968  SCIP_CALL( presolveAddKKTKnapsackConss(scip, objcons, varhash, dualconss, &ndualconss, naddconss, ndelconss) );
1969 
1970  /* handle varbound constraints */
1971  SCIP_CALL( presolveAddKKTVarboundConss(scip, objcons, varhash, dualconss, &ndualconss, naddconss, ndelconss) );
1972 
1973  /* handle logicor constraints */
1974  SCIP_CALL( presolveAddKKTLogicorConss(scip, objcons, varhash, dualconss, &ndualconss, naddconss, ndelconss) );
1975 
1976  /* handle linear constraints associated to aggregations of variables */
1977  if( SCIPgetNFixedVars(scip) > 0 )
1978  {
1979  SCIP_CALL( presolveAddKKTAggregatedVars(scip, objcons, SCIPgetFixedVars(scip), SCIPgetNFixedVars(scip),
1980  varhash, dualconss, &ndualconss, naddconss) );
1981  }
1982 
1983  /* handle bilinear terms of quadratic constraint */
1984  SCIP_CALL( presolveAddKKTQuadBilinearTerms(scip, objcons, bilinterms, nbilinterms, varhash, scale, dualconss,
1985  &ndualconss, naddconss) );
1986 
1987  /* handle quadratic terms of quadratic constraint */
1988  SCIP_CALL( presolveAddKKTQuadQuadraticTerms(scip, objcons, quadterms, nquadterms, varhash, scale, dualconss,
1989  &ndualconss, naddconss) );
1990 
1991  /* handle linear terms of quadratic constraint */
1992  SCIP_CALL( presolveAddKKTQuadLinearTerms(scip, objcons, lintermvars, lintermcoefs, nlintermvars, quadterms, nquadterms,
1993  varhash, objvar, scale, dualconss, &ndualconss, naddconss) );
1994 
1995  /* add/release objective constraint */
1996  SCIP_CALL( SCIPaddCons(scip, objcons) );
1997  SCIP_CALL( SCIPreleaseCons(scip, &objcons) );
1998  ++(*naddconss);
1999 
2000  /* add/release dual constraints associated to the KKT conditions */
2001  for( j = 0; j < ndualconss; ++j )
2002  {
2003  SCIP_CALL( SCIPaddCons(scip, dualconss[j]) );
2004  SCIP_CALL( SCIPreleaseCons(scip, &dualconss[j]) );
2005  }
2006  *naddconss = *naddconss + ndualconss;
2007 
2008  /* free buffer array */
2009  SCIPfreeBufferArrayNull(scip, &savelinconss);
2010  SCIPfreeBufferArray(scip, &dualconss);
2011 
2012  /* free hash map */
2013  SCIPhashmapFree(&varhash);
2014 
2015  if( SCIPgetNBinVars(scip) > 0 )
2016  SCIPdebugMsg(scip, "added the KKT conditions to the mixed-binary quadratic program\n");
2017  else
2018  SCIPdebugMsg(scip, "added the KKT conditions to the quadratic program\n");
2019 
2020  /* SCIP_CALL( SCIPwriteTransProblem(scip, "trafoQP.lp", NULL, FALSE ) ); */
2021 
2022  return SCIP_OKAY;
2023 }
2024 
2025 
2026 /*
2027  * presolver specific interface methods
2028  */
2029 
2030 /** creates the QP KKT reformulation presolver and includes it in SCIP */
2031 SCIP_RETCODE SCIPincludePresolQPKKTref(
2032  SCIP* scip /**< SCIP data structure */
2033  )
2034 {
2035  SCIP_PRESOLDATA* presoldata;
2036  SCIP_PRESOL* presol= NULL;
2037 
2038  /* alloc presolve data object */
2039  SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
2040 
2041  /* include presolver */
2042  SCIP_CALL( SCIPincludePresolBasic(scip, &presol, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS,
2043  PRESOL_TIMING, presolExecQPKKTref, presoldata) );
2044  assert(presol != NULL);
2045 
2046  /* set non fundamental callbacks via setter functions */
2047  SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyQPKKTref) );
2048  SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeQPKKTref) );
2049 
2050  /* add qpkktref presolver parameters */
2051  SCIP_CALL( SCIPaddBoolParam(scip, "presolving/" PRESOL_NAME "/addkktbinary",
2052  "if TRUE then allow binary variables for KKT update",
2053  &presoldata->addkktbinary, TRUE, FALSE, NULL, NULL) );
2054 
2055  SCIP_CALL( SCIPaddBoolParam(scip, "presolving/" PRESOL_NAME "/updatequadbounded",
2056  "if TRUE then only apply the update to QPs with bounded variables; if the variables are not bounded then a "
2057  "finite optimal solution might not exist and the KKT conditions would then be invalid",
2058  &presoldata->updatequadbounded, TRUE, TRUE, NULL, NULL) );
2059 
2060  SCIP_CALL( SCIPaddBoolParam(scip, "presolving/" PRESOL_NAME "/updatequadindef",
2061  "if TRUE then apply quadratic constraint update even if the quadratic constraint matrix is known to be indefinite",
2062  &presoldata->updatequadindef, TRUE, FALSE, NULL, NULL) );
2063 
2064  return SCIP_OKAY;
2065 }
createKKTComplementarityLinear
static SCIP_RETCODE createKKTComplementarityLinear(SCIP *scip, const char *namepart, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, int nvars, SCIP_VAR *dualvar, SCIP_Bool takelhs, int *naddconss)
Definition: presol_qpkktref.c:139
SCIP_Presol
Definition: struct_presol.h:37
SCIP_PRESOLDATA
struct SCIP_PresolData SCIP_PRESOLDATA
Definition: type_presol.h:42
SCIPcreateConsBasicSOS1
SCIP_RETCODE SCIPcreateConsBasicSOS1(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *weights)
Definition: cons_sos1.c:10497
presolveAddKKTQuadBilinearTerms
static SCIP_RETCODE presolveAddKKTQuadBilinearTerms(SCIP *scip, SCIP_CONS *objcons, SCIP_BILINTERM *bilinterms, int nbilinterms, SCIP_HASHMAP *varhash, SCIP_Real scale, SCIP_CONS **dualconss, int *ndualconss, int *naddconss)
Definition: presol_qpkktref.c:1274
SCIPfindConshdlr
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
SCIP_BilinTerm::var2
SCIP_VAR * var2
Definition: cons_quadratic.h:124
scip_param.h
public methods for SCIP parameter handling
SCIPgetLhsLinear
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18334
SCIP_DECL_PRESOLCOPY
static SCIP_DECL_PRESOLCOPY(presolCopyQPKKTref)
Definition: presol_qpkktref.c:1750
SCIPvarGetAggrScalar
SCIP_EXPORT SCIP_Real SCIPvarGetAggrScalar(SCIP_VAR *var)
Definition: var.c:17413
cons_varbound.h
Constraint handler for variable bound constraints .
SCIPgetBilinTermsQuadratic
SCIP_BILINTERM * SCIPgetBilinTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15112
SCIPvarGetNLocksUpType
SCIP_EXPORT int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3250
scip_mem.h
public methods for memory management
presolveAddKKTLogicorConss
static SCIP_RETCODE presolveAddKKTLogicorConss(SCIP *scip, SCIP_CONS *objcons, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss, int *ndelconss)
Definition: presol_qpkktref.c:1032
presolveAddKKTKnapsackConss
static SCIP_RETCODE presolveAddKKTKnapsackConss(SCIP *scip, SCIP_CONS *objcons, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss, int *ndelconss)
Definition: presol_qpkktref.c:758
SCIP_MAXSTRLEN
#define SCIP_MAXSTRLEN
Definition: def.h:279
SCIP_BilinTerm::var1
SCIP_VAR * var1
Definition: cons_quadratic.h:123
SCIP_SETPPCTYPE_COVERING
Definition: cons_setppc.h:80
SCIPcheckCurvatureQuadratic
SCIP_RETCODE SCIPcheckCurvatureQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15191
PRESOL_DESC
#define PRESOL_DESC
Definition: presol_qpkktref.c:105
SCIPaddCoefLinear
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
Definition: cons_linear.c:18089
SCIP_Var
Definition: struct_var.h:198
SCIPconshdlrGetNConss
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4582
SCIPgetNVarsKnapsack
int SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13613
SCIPcreateVarBasic
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition: scip_var.c:185
SCIPhashmapInsertInt
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3132
createKKTComplementarityBounds
static SCIP_RETCODE createKKTComplementarityBounds(SCIP *scip, SCIP_VAR *var, SCIP_VAR *dualvar, SCIP_Bool takelb, int *naddconss)
Definition: presol_qpkktref.c:223
SCIPvarIsBinary
SCIP_EXPORT SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17197
SCIP_QuadVarTerm
Definition: cons_quadratic.h:104
SCIPgetNVars
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1986
SCIPgetNConss
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3036
FALSE
#define FALSE
Definition: def.h:73
scip_presol.h
public methods for presolving plugins
SCIPgetLhsQuadratic
SCIP_Real SCIPgetLhsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15125
SCIPvarGetObj
SCIP_EXPORT SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17515
SCIPgetQuadVarTermsQuadratic
SCIP_QUADVARTERM * SCIPgetQuadVarTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15047
SCIPcreateConsBasicLinear
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
Definition: cons_linear.c:17937
SCIPisFeasNegative
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:862
TRUE
#define TRUE
Definition: def.h:72
PRESOL_NAME
#define PRESOL_NAME
Definition: presol_qpkktref.c:104
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIPchgLhsLinear
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
Definition: cons_linear.c:18382
presolveAddKKTLinearCons
static SCIP_RETCODE presolveAddKKTLinearCons(SCIP *scip, SCIP_CONS *objcons, const char *namepart, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, int nvars, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss)
Definition: presol_qpkktref.c:572
SCIP_SETPPCTYPE_PACKING
Definition: cons_setppc.h:79
SCIPisFeasLE
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:799
SCIPgetVarsSetppc
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9273
pub_var.h
public methods for problem variables
SCIPaddBoolParam
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
SCIPfreeBlockMemory
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
PRESOL_PRIORITY
#define PRESOL_PRIORITY
Definition: presol_qpkktref.c:106
SCIPvarGetStatus
SCIP_EXPORT SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17136
SCIPduplicateBufferArray
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:119
createKKTDualCons
static SCIP_RETCODE createKKTDualCons(SCIP *scip, SCIP_CONS *objcons, SCIP_VAR *var, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, SCIP_CONS **dualcons, int *naddconss)
Definition: presol_qpkktref.c:419
SCIPgetWeightsKnapsack
SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13659
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
cons_setppc.h
Constraint handler for the set partitioning / packing / covering constraints .
SCIPallocBlockMemory
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
SCIPgetValsLinear
SCIP_Real * SCIPgetValsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18469
scip_var.h
public methods for SCIP variables
SCIPdebugMsg
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIPgetNQuadVarTermsQuadratic
int SCIPgetNQuadVarTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15032
SCIPisInfinity
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:514
SCIPgetNIntVars
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2076
scip_numerics.h
public methods for numerical tolerances
SCIPvarGetMultaggrScalars
SCIP_EXPORT SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var)
Definition: var.c:17459
SCIPdelCons
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2837
SCIPhashmapGetImageInt
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3221
SCIPhashmapExists
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3363
SCIP_DECL_PRESOLEXEC
static SCIP_DECL_PRESOLEXEC(presolExecQPKKTref)
Definition: presol_qpkktref.c:1782
SCIP_HashMap
Definition: struct_misc.h:128
pub_cons.h
public methods for managing constraints
cons_knapsack.h
Constraint handler for knapsack constraints of the form , x binary and .
presolveAddKKTQuadLinearTerms
static SCIP_RETCODE presolveAddKKTQuadLinearTerms(SCIP *scip, SCIP_CONS *objcons, SCIP_VAR **lintermvars, SCIP_Real *lintermcoefs, int nlintermvars, SCIP_QUADVARTERM *quadterms, int nquadterms, SCIP_HASHMAP *varhash, SCIP_VAR *objvar, SCIP_Real scale, SCIP_CONS **dualconss, int *ndualconss, int *naddconss)
Definition: presol_qpkktref.c:1407
SCIPgetVarVarbound
SCIP_VAR * SCIPgetVarVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:5181
SCIPvarGetName
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17017
SCIPgetFixedVars
SCIP_VAR ** SCIPgetFixedVars(SCIP *scip)
Definition: scip_prob.c:2260
SCIP_Cons
Definition: struct_cons.h:37
SCIPerrorMessage
#define SCIPerrorMessage
Definition: pub_message.h:55
SCIPisConvexQuadratic
SCIP_Bool SCIPisConvexQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15205
SCIP_Conshdlr
Definition: struct_cons.h:117
presolveAddKKTAggregatedVars
static SCIP_RETCODE presolveAddKKTAggregatedVars(SCIP *scip, SCIP_CONS *objcons, SCIP_VAR **agrvars, int nagrvars, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss)
Definition: presol_qpkktref.c:1115
SCIPgetRhsVarbound
SCIP_Real SCIPgetRhsVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:5158
SCIPpresolGetData
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
Definition: presol.c:503
SCIPisFeasEQ
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:773
SCIPgetNObjVars
int SCIPgetNObjVars(SCIP *scip)
Definition: scip_prob.c:2214
cons_logicor.h
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
presolveAddKKTQuadQuadraticTerms
static SCIP_RETCODE presolveAddKKTQuadQuadraticTerms(SCIP *scip, SCIP_CONS *objcons, SCIP_QUADVARTERM *quadterms, int nquadterms, SCIP_HASHMAP *varhash, SCIP_Real scale, SCIP_CONS **dualconss, int *ndualconss, int *naddconss)
Definition: presol_qpkktref.c:1348
SCIPgetVbdcoefVarbound
SCIP_Real SCIPgetVbdcoefVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:5227
SCIPfreeBufferArrayNull
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:124
SCIPblkmem
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
SCIPgetRhsLinear
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18358
cons_quadratic.h
constraint handler for quadratic constraints
SCIP_VARSTATUS_AGGREGATED
Definition: type_var.h:44
SCIPgetNFixedVars
int SCIPgetNFixedVars(SCIP *scip)
Definition: scip_prob.c:2303
NULL
#define NULL
Definition: lpi_spx1.cpp:155
REALABS
#define REALABS(x)
Definition: def.h:187
SCIPgetVbdvarVarbound
SCIP_VAR * SCIPgetVbdvarVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:5204
SCIP_OKAY
Definition: type_retcode.h:33
SCIP_SETPPCTYPE_PARTITIONING
Definition: cons_setppc.h:78
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:370
SCIPincludePresolQPKKTref
SCIP_RETCODE SCIPincludePresolQPKKTref(SCIP *scip)
Definition: presol_qpkktref.c:2033
presolveAddKKTLinearConss
static SCIP_RETCODE presolveAddKKTLinearConss(SCIP *scip, SCIP_CONS *objcons, SCIP_CONS **savelinconss, int nlinconss, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss, int *ndelconss)
Definition: presol_qpkktref.c:689
SCIPgetLinvarMayIncreaseQuadratic
int SCIPgetLinvarMayIncreaseQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15171
SCIPgetLinearVarsQuadratic
SCIP_VAR ** SCIPgetLinearVarsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15003
SCIPvarGetAggrConstant
SCIP_EXPORT SCIP_Real SCIPvarGetAggrConstant(SCIP_VAR *var)
Definition: var.c:17424
SCIPsetPresolCopy
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip_presol.c:130
SCIPvarGetNegationConstant
SCIP_EXPORT SCIP_Real SCIPvarGetNegationConstant(SCIP_VAR *var)
Definition: var.c:17504
SCIPpresolSetData
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
Definition: presol.c:513
SCIPaddVarSOS1
SCIP_RETCODE SCIPaddVarSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real weight)
Definition: cons_sos1.c:10513
scip_cons.h
public methods for constraint handler plugins and constraints
SCIP_ERROR
Definition: type_retcode.h:34
SCIPisFeasZero
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:838
SCIPgetVarsLogicor
SCIP_VAR ** SCIPgetVarsLogicor(SCIP *scip, SCIP_CONS *cons)
Definition: cons_logicor.c:5347
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip_numerics.c:503
pub_misc.h
public data structures and miscellaneous methods
SCIPvarGetNegationVar
SCIP_EXPORT SCIP_VAR * SCIPvarGetNegationVar(SCIP_VAR *var)
Definition: var.c:17493
SCIP_Bool
#define SCIP_Bool
Definition: def.h:70
SCIPvarGetMultaggrConstant
SCIP_EXPORT SCIP_Real SCIPvarGetMultaggrConstant(SCIP_VAR *var)
Definition: var.c:17471
checkConsQuadraticProblem
static SCIP_RETCODE checkConsQuadraticProblem(SCIP *scip, SCIP_CONSHDLR *quadconshdlr, SCIP_CONS *cons, SCIP_Bool allowbinary, SCIP_VAR **objvar, SCIP_Real *scale, SCIP_Real *objrhs, SCIP_Bool *isqp)
Definition: presol_qpkktref.c:1528
SCIPhashmapCreate
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
createKKTComplementarityBinary
static SCIP_RETCODE createKKTComplementarityBinary(SCIP *scip, SCIP_VAR *var, SCIP_VAR *dualbin1, SCIP_VAR *dualbin2, int *naddconss)
Definition: presol_qpkktref.c:317
SCIPvarGetUbGlobal
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17677
SCIP_VARSTATUS_NEGATED
Definition: type_var.h:46
SCIPpresolGetName
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:590
SCIP_DECL_PRESOLFREE
static SCIP_DECL_PRESOLFREE(presolFreeQPKKTref)
Definition: presol_qpkktref.c:1765
SCIPgetNVarsLinear
int SCIPgetNVarsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18421
SCIP_BilinTerm
Definition: cons_quadratic.h:121
SCIPgetVarsKnapsack
SCIP_VAR ** SCIPgetVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13636
SCIP_VARSTATUS_MULTAGGR
Definition: type_var.h:45
presolveAddKKTSetppcConss
static SCIP_RETCODE presolveAddKKTSetppcConss(SCIP *scip, SCIP_CONS *objcons, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss, int *ndelconss)
Definition: presol_qpkktref.c:838
cons_linear.h
Constraint handler for linear constraints in their most general form, .
SCIPvarGetLbOriginal
SCIP_EXPORT SCIP_Real SCIPvarGetLbOriginal(SCIP_VAR *var)
Definition: var.c:17613
SCIPaddVar
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1666
SCIPisFeasGE
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:825
SCIPsetPresolFree
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
Definition: scip_presol.c:146
SCIPisConcaveQuadratic
SCIP_Bool SCIPisConcaveQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15238
SCIPvarGetNLocksDownType
SCIP_EXPORT int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3193
pub_presol.h
public methods for presolvers
SCIP_SETPPCTYPE
enum SCIP_SetppcType SCIP_SETPPCTYPE
Definition: cons_setppc.h:82
scalars
static const SCIP_Real scalars[]
Definition: lp.c:5731
PRESOL_MAXROUNDS
#define PRESOL_MAXROUNDS
Definition: presol_qpkktref.c:109
SCIPgetNVarsLogicor
int SCIPgetNVarsLogicor(SCIP *scip, SCIP_CONS *cons)
Definition: cons_logicor.c:5324
SCIPgetNLinearVarsQuadratic
int SCIPgetNLinearVarsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:14988
SCIPvarGetLbGlobal
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17667
SCIPvarGetMultaggrNVars
SCIP_EXPORT int SCIPvarGetMultaggrNVars(SCIP_VAR *var)
Definition: var.c:17435
SCIPconshdlrGetConss
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4539
SCIPgetNBilinTermsQuadratic
int SCIPgetNBilinTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15097
pub_message.h
public methods for message output
SCIP_LOCKTYPE_MODEL
Definition: type_var.h:84
SCIPsnprintf
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10604
SCIPgetNVarsSetppc
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9250
SCIPhashmapFree
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3048
SCIPconsGetName
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8077
SCIPreleaseVar
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1245
SCIP_Real
#define SCIP_Real
Definition: def.h:163
SCIPincludePresolBasic
SCIP_RETCODE SCIPincludePresolBasic(SCIP *scip, SCIP_PRESOL **presolptr, const char *name, const char *desc, int priority, int maxrounds, SCIP_PRESOLTIMING timing, SCIP_DECL_PRESOLEXEC((*presolexec)), SCIP_PRESOLDATA *presoldata)
Definition: scip_presol.c:95
cons_sos1.h
constraint handler for SOS type 1 constraints
SCIPgetRhsQuadratic
SCIP_Real SCIPgetRhsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15138
scip_message.h
public methods for message handling
SCIPvarGetOrigvarSum
SCIP_EXPORT SCIP_RETCODE SCIPvarGetOrigvarSum(SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: var.c:12545
SCIP_Longint
#define SCIP_Longint
Definition: def.h:148
SCIPgetNBinVars
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2031
SCIPgetTypeSetppc
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9296
SCIP_QuadVarTerm::lincoef
SCIP_Real lincoef
Definition: cons_quadratic.h:107
SCIPaddCons
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2764
SCIPgetCoefsLinearVarsQuadratic
SCIP_Real * SCIPgetCoefsLinearVarsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15018
SCIPvarGetAggrVar
SCIP_EXPORT SCIP_VAR * SCIPvarGetAggrVar(SCIP_VAR *var)
Definition: var.c:17402
SCIPvarGetUbOriginal
SCIP_EXPORT SCIP_Real SCIPvarGetUbOriginal(SCIP_VAR *var)
Definition: var.c:17633
PRESOL_TIMING
#define PRESOL_TIMING
Definition: presol_qpkktref.c:112
SCIPchgRhsLinear
SCIP_RETCODE SCIPchgRhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
Definition: cons_linear.c:18403
SCIP_INVALIDDATA
Definition: type_retcode.h:43
SCIPreleaseCons
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
SCIPgetLhsVarbound
SCIP_Real SCIPgetLhsVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:5135
SCIP_QuadVarTerm::var
SCIP_VAR * var
Definition: cons_quadratic.h:106
scip_prob.h
public methods for global and local (sub)problems
SCIP_VARSTATUS_FIXED
Definition: type_var.h:43
SCIPgetLinvarMayDecreaseQuadratic
int SCIPgetLinvarMayDecreaseQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15151
SCIPgetVarsLinear
SCIP_VAR ** SCIPgetVarsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18445
presolveAddKKTVarboundConss
static SCIP_RETCODE presolveAddKKTVarboundConss(SCIP *scip, SCIP_CONS *objcons, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss, int *ndelconss)
Definition: presol_qpkktref.c:944
SCIPvarGetMultaggrVars
SCIP_EXPORT SCIP_VAR ** SCIPvarGetMultaggrVars(SCIP_VAR *var)
Definition: var.c:17447
SCIPgetCapacityKnapsack
SCIP_Longint SCIPgetCapacityKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13556
SCIPisFeasPositive
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:850
presol_qpkktref.h
qpkktref presolver
memory.h
memory allocation routines
SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:58