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-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@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_nonlinear.h"
82 #include "scip/cons_knapsack.h"
83 #include "scip/cons_linear.h"
84 #include "scip/cons_logicor.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 0 /**< 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_EXPR* quadexpr, /**< quadratic expression */
1276  SCIP_HASHMAP* varhash, /**< hash map from variable to index of linear constraint */
1277  SCIP_Real scale, /**< scale factor of quadratic constraint */
1278  SCIP_CONS** dualconss, /**< array with dual constraints */
1279  int* ndualconss, /**< pointer to store number of dual constraints */
1280  int* naddconss /**< buffer to increase with number of created additional constraints */
1281  )
1282 {
1283  int nbilinexprs;
1284  int j;
1285 
1286  assert( scip != NULL );
1287  assert( objcons != NULL );
1288  assert( quadexpr != NULL );
1289  assert( varhash != NULL );
1290  assert( dualconss != NULL );
1291  assert( ndualconss != NULL );
1292  assert( naddconss != NULL );
1293 
1294  /* get the number of bilinear expressions */
1295  SCIPexprGetQuadraticData(quadexpr, NULL, NULL, NULL, NULL, NULL, &nbilinexprs, NULL, NULL);
1296 
1297  /* loop through bilinear terms of quadratic constraint */
1298  for( j = 0; j < nbilinexprs; ++j )
1299  {
1300  SCIP_EXPR* expr1;
1301  SCIP_EXPR* expr2;
1302  SCIP_VAR* bilvar1;
1303  SCIP_VAR* bilvar2;
1304  SCIP_Real coef;
1305  int i;
1306 
1307  /* get variables of the bilinear term */
1308  SCIPexprGetQuadraticBilinTerm(quadexpr, j, &expr1, &expr2, &coef, NULL, NULL);
1309  assert(expr1 != NULL && SCIPisExprVar(scip, expr1));
1310  assert(expr2 != NULL && SCIPisExprVar(scip, expr2));
1311 
1312  bilvar1 = SCIPgetVarExprVar(expr1);
1313  bilvar2 = SCIPgetVarExprVar(expr2);
1314  assert(bilvar1 != NULL && bilvar2 != NULL && bilvar1 != bilvar2);
1315 
1316  /* quadratic matrix has to be symmetric; therefore, split bilinear terms into two parts */
1317  for( i = 0; i < 2; ++i )
1318  {
1319  SCIP_CONS* dualcons = NULL; /* dual constraint associated to variable */
1320 
1321  if( i == 1 )
1322  SCIPswapPointers((void**)&bilvar1, (void**)&bilvar2);
1323 
1324  /* create/get dual constraint associated to variable 'bilvar1';
1325  * if variable does not already exist in hashmap then create dual variables for its bounds */
1326  SCIP_CALL( createKKTDualCons(scip, objcons, bilvar1, varhash, dualconss, ndualconss, &dualcons, naddconss) );
1327  assert( dualcons != NULL );
1328 
1329  /* add variable to dual constraint */
1330  assert( ! SCIPisFeasZero(scip, scale) );
1331  SCIP_CALL( SCIPaddCoefLinear(scip, dualcons, bilvar2, coef / scale) );
1332  }
1333  }
1334 
1335  return SCIP_OKAY;
1336 }
1337 
1338 /** handle quadratic terms of quadratic constraint for quadratic constraint update
1339  *
1340  * For each quadratic term variable
1341  * 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
1342  * already
1343  * 2. create the dual variables and the complementarity constraints for the lower and upper bound constraints of this
1344  * variable, if not done already
1345  * 3. add the coefficient \f$Q_{ii}\f$ of this variable to the dual constraint
1346  *
1347  * for steps 1 and 2 see the documentation of createKKTDualCons() for further information.
1348  **/
1349 static
1350 SCIP_RETCODE presolveAddKKTQuadQuadraticTerms(
1351  SCIP* scip, /**< SCIP pointer */
1352  SCIP_CONS* objcons, /**< objective constraint */
1353  SCIP_EXPR* quadexpr, /**< quadratic expression */
1354  SCIP_HASHMAP* varhash, /**< hash map from variable to index of linear constraint */
1355  SCIP_Real scale, /**< scale factor of quadratic constraint */
1356  SCIP_CONS** dualconss, /**< array with dual constraints */
1357  int* ndualconss, /**< pointer to store number of dual constraints */
1358  int* naddconss /**< buffer to increase with number of created additional constraints */
1359  )
1360 {
1361  int nquadexprs;
1362  int j;
1363 
1364  assert( scip != NULL );
1365  assert( objcons != NULL );
1366  assert( varhash != NULL );
1367  assert( dualconss != NULL );
1368  assert( ndualconss != NULL );
1369  assert( naddconss != NULL );
1370 
1371  /* get the number of quadratic expressions */
1372  SCIPexprGetQuadraticData(quadexpr, NULL, NULL, NULL, NULL, &nquadexprs, NULL, NULL, NULL);
1373 
1374  /* loop through quadratic terms */
1375  for( j = 0; j < nquadexprs; ++j )
1376  {
1377  SCIP_EXPR* expr;
1378  SCIP_Real sqrcoef;
1379  SCIP_CONS* dualcons = NULL; /* dual constraint associated to variable */
1380  SCIP_VAR* quadvar;
1381 
1382  /* get variable of the quadratic term */
1383  SCIPexprGetQuadraticQuadTerm(quadexpr, j, &expr, NULL, &sqrcoef, NULL, NULL, NULL);
1384  assert(expr != NULL && SCIPisExprVar(scip, expr));
1385  quadvar = SCIPgetVarExprVar(expr);
1386  assert(quadvar != NULL);
1387 
1388  /* create/get dual constraint associated to variable 'bilvar1';
1389  * if variable does not already exist in hashmap then create dual variables for its bounds */
1390  SCIP_CALL( createKKTDualCons(scip, objcons, quadvar, varhash, dualconss, ndualconss, &dualcons, naddconss) );
1391  assert( dualcons != NULL );
1392 
1393  /* add variable to dual constraint */
1394  assert( ! SCIPisFeasZero(scip, scale) );
1395  SCIP_CALL( SCIPaddCoefLinear(scip, dualcons, quadvar, sqrcoef * 2.0 / scale) );
1396  }
1397 
1398  return SCIP_OKAY;
1399 }
1400 
1401 /** handle linear terms of quadratic constraint for quadratic constraint update
1402  *
1403  * For each linear term variable
1404  * 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
1405  * already
1406  * 2. create the dual variables and the complementarity constraints for the lower and upper bound constraints of this
1407  * variable, if not done already
1408  * 3. add the right hand side \f$-c_i\f$ to the dual constraint
1409  * 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
1410  *
1411  * for steps 1 and 2 see the documentation of createKKTDualCons() for further information.
1412  **/
1413 static
1414 SCIP_RETCODE presolveAddKKTQuadLinearTerms(
1415  SCIP* scip, /**< SCIP pointer */
1416  SCIP_CONS* objcons, /**< objective constraint */
1417  SCIP_EXPR* quadexpr, /**< quadratic expression */
1418  SCIP_HASHMAP* varhash, /**< hash map from variable to index of linear constraint */
1419  SCIP_VAR* objvar, /**< variable of objective function */
1420  SCIP_Real scale, /**< scale factor of quadratic constraint */
1421  SCIP_CONS** dualconss, /**< array with dual constraints */
1422  int* ndualconss, /**< pointer to store number of dual constraints */
1423  int* naddconss /**< buffer to increase with number of created additional constraints */
1424  )
1425 {
1426  SCIP_EXPR** linexprs;
1427  SCIP_Real* lincoefs;
1428  int nquadexprs;
1429  int nlinexprs;
1430  int j;
1431 
1432  assert( scip != NULL );
1433  assert( objcons != NULL );
1434  assert( varhash != NULL );
1435  assert( objvar != NULL );
1436  assert( dualconss != NULL );
1437  assert( ndualconss != NULL );
1438  assert( naddconss != NULL );
1439 
1440  /* get linear and quadratic expression terms */
1441  SCIPexprGetQuadraticData(quadexpr, NULL, &nlinexprs, &linexprs, &lincoefs, &nquadexprs, NULL, NULL, NULL);
1442 
1443  /* loop through linear terms */
1444  for( j = 0; j < nlinexprs; ++j )
1445  {
1446  SCIP_VAR* var;
1447  SCIP_Real coef;
1448 
1449  assert(linexprs[j] != NULL);
1450  assert(SCIPisExprVar(scip, linexprs[j]));
1451 
1452  var = SCIPgetVarExprVar(linexprs[j]);
1453  assert(var != NULL);
1454  coef = lincoefs[j];
1455 
1456  if( var != objvar )
1457  {
1458  SCIP_CONS* dualcons = NULL; /* dual constraint associated to variable */
1459 
1460  /* create/get dual constraint associated to variable;
1461  * if variable does not already exist in hashmap then create dual variables for its bounds
1462  */
1463  SCIP_CALL( createKKTDualCons(scip, objcons, var, varhash, dualconss, ndualconss, &dualcons, naddconss) );
1464  assert( dualcons != NULL );
1465 
1466  /* change lhs and rhs of dual constraint */
1467  assert( ! SCIPisFeasZero(scip, scale) );
1468  SCIP_CALL( SCIPchgLhsLinear(scip, dualcons, SCIPgetLhsLinear(scip, dualcons) - coef / scale) );
1469  SCIP_CALL( SCIPchgRhsLinear(scip, dualcons, SCIPgetRhsLinear(scip, dualcons) - coef / scale) );
1470 
1471  /* add variable to objective constraint */
1472  SCIP_CALL( SCIPaddCoefLinear(scip, objcons, var, coef / (scale * 2)) );
1473  }
1474  }
1475 
1476  /* loop through linear terms that are part of a quadratic term */
1477  for( j = 0; j < nquadexprs; ++j )
1478  {
1479  SCIP_EXPR* expr;
1480  SCIP_CONS* dualcons;
1481  SCIP_Real coef;
1482  SCIP_VAR* var;
1483  int ind;
1484 
1485  SCIPexprGetQuadraticQuadTerm(quadexpr, j, &expr, &coef, NULL, NULL, NULL, NULL);
1486  assert(expr != NULL);
1487  assert(SCIPisExprVar(scip, expr));
1488 
1489  var = SCIPgetVarExprVar(expr);
1490  assert(var != NULL && var != objvar);
1491 
1492  /* get dual constraint associated to variable (has already been created in function
1493  * presolveAddKKTQuadQuadraticTerms()
1494  */
1495  assert( SCIPhashmapExists(varhash, var) );
1496  ind = SCIPhashmapGetImageInt(varhash, var);
1497  dualcons = dualconss[ind];
1498  assert( dualcons != NULL );
1499 
1500  /* change lhs and rhs of dual constraint */
1501  assert( ! SCIPisFeasZero(scip, scale) );
1502  SCIP_CALL( SCIPchgLhsLinear(scip, dualcons, SCIPgetLhsLinear(scip, dualcons) -coef / scale) );
1503  SCIP_CALL( SCIPchgRhsLinear(scip, dualcons, SCIPgetRhsLinear(scip, dualcons) -coef / scale) );
1504 
1505  /* add variable to objective constraint */
1506  SCIP_CALL( SCIPaddCoefLinear(scip, objcons, var, coef / (scale * 2.0)) );
1507  }
1508 
1509  return SCIP_OKAY;
1510 }
1511 
1512 /** checks for a given constraint whether it is the objective function of a (mixed-binary) quadratic program
1513  * \f[
1514  * \begin{array}{ll}
1515  * \min & z \\
1516  * s.t. & x^T Q x + c^T x + d <= z \\
1517  * & A x \leq b, \\
1518  * & x \in \{0, 1\}^{p} \times R^{n-p},
1519  * \end{array}
1520  * \f]
1521  * which is equivalent to
1522  * \f[
1523  * \begin{array}{ll}
1524  * \min & x^T Q x + c^T x + d \\
1525  * s.t. & A x \leq b, \\
1526  * & x \in \{0, 1\}^{p} \times R^{n-p}.
1527  * \end{array}
1528  * \f]
1529  *
1530  *
1531  * We check whether
1532  * 1. there is a single quadratic constraint that can be written as \f$x^T Q x + c^T x + d \leq z\f$
1533  * 2. all other constraints are linear
1534  * 3. all integer variables are binary if allowbinary = TRUE, or all variables are continuous if allowbinary = FALSE
1535  * 4. z is the only variable in the objective and doesn't appear in any other constraint
1536  */
1537 static
1538 SCIP_RETCODE checkConsQuadraticProblem(
1539  SCIP* scip, /**< SCIP data structure */
1540  SCIP_CONS* cons, /**< nonlinear constraint */
1541  SCIP_EXPR* quadexpr, /**< quadratic expression */
1542  SCIP_Bool allowbinary, /**< if TRUE then allow binary variables in the problem, if FALSE then all
1543  * variables have to be continuous */
1544  SCIP_VAR** objvar, /**< pointer to store the objective variable @p z */
1545  SCIP_Real* scale, /**< pointer to store the value by which we have to scale the quadratic
1546  * constraint such that the objective variable @p z has coefficient -1 */
1547  SCIP_Real* objrhs, /**< pointer to store the right hand side @p -d of the objective constraint */
1548  SCIP_Bool* isqp /**< pointer to store whether the problem is a (mixed-binary) QP */
1549  )
1550 {
1551  SCIP_CONSHDLR* conshdlr;
1552  int nconss = 0;
1553  SCIP_Real coef;
1554  SCIP_Real obj;
1555 
1556  SCIP_VAR* origObjVar;
1557  SCIP_Real origObjConstant = 0.0;
1558  SCIP_Real origObjScalar = 1.0;
1559  SCIP_Real origObjUb;
1560  SCIP_Real origObjLb;
1561 
1562  SCIP_Real lhs;
1563  SCIP_Real rhs;
1564 
1565  SCIP_VAR* mayincrease;
1566  SCIP_VAR* maydecrease;
1567  SCIP_Real mayincreasecoef;
1568  SCIP_Real maydecreasecoef;
1569 
1570  SCIP_EXPR** linexprs;
1571  SCIP_Real* lincoefs;
1572  SCIP_Real constant;
1573  int nbilinexprs;
1574  int nquadexprs;
1575  int nlinexprs;
1576 
1577  assert(SCIPconshdlrGetNConss(SCIPfindConshdlr(scip, "nonlinear")) == 1);
1578 
1579  *objrhs = 0.0;
1580  *scale = 0.0;
1581  *isqp = FALSE;
1582  *objvar = NULL;
1583 
1584  lhs = SCIPgetLhsNonlinear(cons);
1585  rhs = SCIPgetRhsNonlinear(cons);
1586 
1587  /* desired structure: there exists only one variable with nonzero objective value; this is the objective variable 'z' */
1588  if( SCIPgetNObjVars(scip) != 1 )
1589  return SCIP_OKAY;
1590 
1591  /* desired structure: all integer variables are binary; if the parameter 'allowbinary' is set to FALSE, then all
1592  * variables have to be continuous
1593  */
1594  if( SCIPgetNIntVars(scip) > 0 || (! allowbinary && SCIPgetNBinVars(scip) > 0) )
1595  return SCIP_OKAY;
1596 
1597  /* desired structure: the constraint has to take one of the three forms
1598  * i) x^T Q x + c^T x <= d
1599  * ii) x^T Q x + c^T x >= d
1600  * iii) x^T Q x + c^T x == d
1601  * the case a <= x^T Q x + c^T x <= d with 'a' and 'd' finite and a != d is not allowed.
1602  */
1603  if( ! SCIPisFeasEQ(scip, lhs, rhs) && ! SCIPisInfinity(scip, -lhs) && ! SCIPisInfinity(scip, rhs) )
1604  return SCIP_OKAY;
1605 
1606  /* get number of linear constraints (including special cases of linear constraints) */
1607  conshdlr = SCIPfindConshdlr(scip, "linear");
1608  if( conshdlr != NULL )
1609  nconss += SCIPconshdlrGetNConss(conshdlr);
1610 
1611  conshdlr = SCIPfindConshdlr(scip, "setppc");
1612  if( conshdlr != NULL )
1613  nconss += SCIPconshdlrGetNConss(conshdlr);
1614 
1615  conshdlr = SCIPfindConshdlr(scip, "knapsack");
1616  if( conshdlr != NULL )
1617  nconss += SCIPconshdlrGetNConss(conshdlr);
1618 
1619  conshdlr = SCIPfindConshdlr(scip, "varbound");
1620  if( conshdlr != NULL )
1621  nconss += SCIPconshdlrGetNConss(conshdlr);
1622 
1623  conshdlr = SCIPfindConshdlr(scip, "logicor");
1624  if( conshdlr != NULL )
1625  nconss += SCIPconshdlrGetNConss(conshdlr);
1626 
1627  /* desired structure: all the non-nonlinear constraints are linear constraints */
1628  if( nconss != SCIPgetNConss(scip) - 1 )
1629  return SCIP_OKAY;
1630 
1631  /* get data of the quadratic expression */
1632  SCIPexprGetQuadraticData(quadexpr, &constant, &nlinexprs, &linexprs, &lincoefs, &nquadexprs, &nbilinexprs, NULL, NULL);
1633 
1634  /* adjust lhs and rhs if constant is nonzero */
1635  if( constant != 0.0 )
1636  {
1637  if( !SCIPisInfinity(scip, -lhs) )
1638  lhs -= constant;
1639  if( !SCIPisInfinity(scip, rhs) )
1640  rhs -= constant;
1641  }
1642 
1643  /* compute the objective shift of the QP. Note that
1644  *
1645  * min z s.t. x^T Q x + c^T x <= d + z
1646  * Ax <= b
1647  *
1648  * is equivalent to
1649  *
1650  * min x^T Q x + c^T x - d s.t. Ax <= b
1651  *
1652  * Here, -d is the objective shift. We define b to be the right hand side of the objective constraint.
1653  */
1654  if( ! SCIPisInfinity(scip, -lhs) )
1655  *objrhs = lhs;
1656  else
1657  *objrhs = rhs;
1658  assert( ! SCIPisInfinity(scip, REALABS(*objrhs)) );
1659 
1660  /* search for the objective variable 'objvar' in the linear term of quadratic constraint (it is already known that
1661  * at most one variable has a nonzero objective value); additionally, check the sign of the objective variable
1662  */
1663 
1664  SCIPgetLinvarMayIncreaseNonlinear(scip, cons, &mayincrease, &mayincreasecoef);
1665  SCIPgetLinvarMayIncreaseNonlinear(scip, cons, &maydecrease, &maydecreasecoef);
1666 
1667  if( maydecrease == NULL && mayincrease == NULL )
1668  return SCIP_OKAY;
1669  else if( maydecrease != NULL )
1670  {
1671  *objvar = maydecrease;
1672  coef = maydecreasecoef;
1673 
1674  /* if both mayincrease and maydecrease are nonnegative, then check objective coefficient */
1675  if( mayincrease != NULL && SCIPisFeasZero(scip, SCIPvarGetObj(maydecrease)) )
1676  {
1677  *objvar = mayincrease;
1678  coef = mayincreasecoef;
1679  }
1680  }
1681  else
1682  {
1683  *objvar = mayincrease;
1684  coef = mayincreasecoef;
1685  }
1686  obj = SCIPvarGetObj(*objvar);
1687 
1688  /* check sign of coefficient */
1689  if( SCIPisFeasPositive(scip, obj)
1690  && ( ( SCIPisFeasNegative(scip, coef) && SCIPisFeasEQ(scip, rhs, *objrhs) )
1691  || ( SCIPisFeasPositive(scip, coef) && SCIPisFeasEQ(scip, lhs, *objrhs) )
1692  )
1693  )
1694  {
1695  *scale = -coef; /* value by which we have to scale the quadratic constraint such that the objective variable
1696  * has coefficient -1 */
1697  }
1698  else if( SCIPisFeasNegative(scip, obj)
1699  && ( ( SCIPisFeasNegative(scip, coef) && SCIPisFeasEQ(scip, lhs, *objrhs) )
1700  || ( SCIPisFeasPositive(scip, coef) && SCIPisFeasEQ(scip, rhs, *objrhs) )
1701  )
1702  )
1703  {
1704  *scale = coef; /* value by which we have to scale the quadratic constraint such that the objective variable
1705  * has coefficient 1 */
1706  }
1707  else
1708  return SCIP_OKAY;
1709  assert( *objvar != NULL && ! SCIPisFeasZero(scip, SCIPvarGetObj(*objvar)) );
1710  assert( ! SCIPisFeasZero(scip, *scale) );
1711 
1712  /* scale the right hand side of the objective constraint */
1713  *objrhs = (*objrhs)/(*scale); /*lint !e414*/
1714 
1715  /* check whether 'objvar' is part of a linear constraint; if this is true then return
1716  * whether 'objvar' is part of a linear constraint can be deduced from the variable locks */
1717  if( SCIPisFeasEQ(scip, lhs, rhs) )
1718  {
1719  if( SCIPvarGetNLocksDownType(*objvar, SCIP_LOCKTYPE_MODEL) != 1
1720  || SCIPvarGetNLocksUpType(*objvar, SCIP_LOCKTYPE_MODEL) != 1 )
1721  return SCIP_OKAY;
1722  }
1723  else
1724  {
1725  assert( SCIPisInfinity(scip, -lhs) || SCIPisInfinity(scip, rhs) );
1726 
1727  if( ( SCIPvarGetNLocksDownType(*objvar, SCIP_LOCKTYPE_MODEL) != 1
1728  || SCIPvarGetNLocksUpType(*objvar, SCIP_LOCKTYPE_MODEL) != 0 )
1729  && ( SCIPvarGetNLocksDownType(*objvar, SCIP_LOCKTYPE_MODEL) != 0
1730  || SCIPvarGetNLocksUpType(*objvar, SCIP_LOCKTYPE_MODEL) != 1 ) )
1731  return SCIP_OKAY;
1732  }
1733 
1734  /* check bounds of original objective variable */
1735  origObjVar = *objvar;
1736  SCIP_CALL( SCIPvarGetOrigvarSum(&origObjVar, &origObjScalar, &origObjConstant) );
1737  if( origObjVar == NULL )
1738  return SCIP_OKAY;
1739 
1740  if( SCIPisFeasPositive(scip, origObjScalar) )
1741  {
1742  origObjUb = SCIPvarGetUbOriginal(origObjVar);
1743  origObjLb = SCIPvarGetLbOriginal(origObjVar);
1744  }
1745  else
1746  {
1747  origObjUb = -SCIPvarGetLbOriginal(origObjVar);
1748  origObjLb = -SCIPvarGetUbOriginal(origObjVar);
1749  origObjScalar *= -1;
1750  origObjConstant *= -1;
1751  }
1752 
1753  /* not every optimal solution of the problem is a KKT point if the objective variable is bounded */
1754  if( SCIPisFeasPositive(scip, obj))
1755  {
1756  if ( !SCIPisInfinity(scip, -origObjLb))
1757  return SCIP_OKAY;
1758  if ( !SCIPisInfinity(scip, origObjUb)
1759  && !SCIPisFeasLE(scip, rhs/coef, (origObjUb-origObjConstant)/origObjScalar) )
1760  return SCIP_OKAY;
1761  }
1762  else
1763  {
1764  if ( !SCIPisInfinity(scip, origObjUb) )
1765  return SCIP_OKAY;
1766  if ( !SCIPisInfinity(scip, -origObjLb)
1767  && !SCIPisFeasGE(scip, lhs/coef, (origObjLb - origObjConstant)/origObjScalar) )
1768  return SCIP_OKAY;
1769  }
1770 
1771  *isqp = TRUE;
1772 
1773  return SCIP_OKAY;
1774 }
1775 
1776 /*
1777  * Callback methods of presolver
1778  */
1779 
1780 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
1781 static
1782 SCIP_DECL_PRESOLCOPY(presolCopyQPKKTref)
1783 { /*lint --e{715}*/
1784  assert(scip != NULL);
1785  assert(presol != NULL);
1786  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
1787 
1788  /* call inclusion method of presolver */
1789  SCIP_CALL( SCIPincludePresolQPKKTref(scip) );
1790 
1791  return SCIP_OKAY;
1792 }
1793 
1794 
1795 /** destructor of presolver to free user data (called when SCIP is exiting) */
1796 static
1797 SCIP_DECL_PRESOLFREE(presolFreeQPKKTref)
1798 { /*lint --e{715}*/
1799  SCIP_PRESOLDATA* presoldata;
1800 
1801  /* free presolver data */
1802  presoldata = SCIPpresolGetData(presol);
1803  assert(presoldata != NULL);
1804 
1805  SCIPfreeBlockMemory(scip, &presoldata);
1806  SCIPpresolSetData(presol, NULL);
1807 
1808  return SCIP_OKAY;
1809 }
1810 
1811 
1812 /** execution method of presolver */
1813 static
1814 SCIP_DECL_PRESOLEXEC(presolExecQPKKTref)
1815 { /*lint --e{715}*/
1816  SCIP_PRESOLDATA* presoldata;
1817  SCIP_CONSHDLR* linconshdlr;
1818  SCIP_CONSHDLR* nlconshdlr;
1819  SCIP_CONS** conss;
1820  SCIP_CONS* cons;
1821  SCIP_Bool isquadratic;
1822  SCIP_EXPR* expr;
1823 
1824  SCIP_CONS** savelinconss = NULL;
1825  SCIP_CONS** linconss = NULL;
1826  int nlinconss = 0;
1827 
1828  SCIP_HASHMAP* varhash; /* hash map from variable to index of dual constraint */
1829  SCIP_CONS** dualconss; /* constraints associated to the Lagrangean function */
1830  int ndualconss = 0;
1831 
1832  SCIP_EXPRCURV curv;
1833 
1834  SCIP_CONS* objcons;
1835  SCIP_VAR* objvar;
1836  SCIP_Real scale;
1837  SCIP_Real objrhs;
1838  SCIP_Bool isqp;
1839  int j;
1840 
1841  assert( scip != NULL );
1842  assert( naddconss != NULL );
1843  assert( ndelconss != NULL );
1844 
1845  /* desired structure: there exists only one nonlinear constraint */
1846  nlconshdlr = SCIPfindConshdlr(scip, "nonlinear");
1847  if( nlconshdlr == NULL || SCIPconshdlrGetNConss(nlconshdlr) != 1 )
1848  return SCIP_OKAY;
1849 
1850  /* get presolver data */
1851  presoldata = SCIPpresolGetData(presol);
1852  assert(presoldata != NULL);
1853 
1854  /* get nonlinear constraint */
1855  conss = SCIPconshdlrGetConss(nlconshdlr);
1856  cons = conss[0];
1857  assert( cons != NULL );
1858 
1859  SCIPdebugMsg(scip, "tries to add the KKT conditions for constraint <%s>\n", SCIPconsGetName(cons));
1860 
1861  /* get quadratic representation of the nonlinear constraint, if possible */
1862  SCIP_CALL( SCIPcheckQuadraticNonlinear(scip, cons, &isquadratic) );
1863 
1864  if( !isquadratic )
1865  {
1866  SCIPdebugMsg(scip, "nonlinear constraint is not quadratic -> skip\n");
1867  return SCIP_OKAY;
1868  }
1869 
1870  /* desired structure: matrix associated to quadratic constraint is indefinite; otherwise, the problem usually can be
1871  * solved faster by standard methods
1872  */
1873  expr = SCIPgetExprNonlinear(cons);
1874  SCIP_CALL( SCIPcomputeExprQuadraticCurvature(scip, expr, &curv, NULL, FALSE) );
1875 
1876  if( !presoldata->updatequadindef && (curv == SCIP_EXPRCURV_CONVEX || curv == SCIP_EXPRCURV_CONCAVE) )
1877  {
1878  SCIPdebugMsg(scip, "quadratic constraint update failed, since matrix associated to quadratic constraint <%s> is \
1879  not indefinite.\n", SCIPconsGetName(cons) );
1880  return SCIP_OKAY;
1881  }
1882 
1883  /* first, check whether the problem is equivalent to
1884  *
1885  * min z
1886  * s.t. x^T Q x + c^T x <= b + z
1887  * x \in \{0, 1\}^{p} \times R^{n-p}.
1888  *
1889  */
1890  SCIP_CALL( checkConsQuadraticProblem(scip, cons, expr, presoldata->addkktbinary, &objvar, &scale,
1891  &objrhs, &isqp) );
1892  if( ! isqp )
1893  return SCIP_OKAY;
1894  assert( objvar != NULL );
1895 
1896  /* get constraint handler data of linear constraints */
1897  linconshdlr = SCIPfindConshdlr(scip, "linear");
1898 
1899  /* get linear constraints and number of linear constraints */
1900  if( linconshdlr != NULL )
1901  {
1902  nlinconss = SCIPconshdlrGetNConss(linconshdlr);
1903  linconss = SCIPconshdlrGetConss(linconshdlr);
1904  }
1905 
1906  /* the update is only valid if a finite optimal solution of the problem exists,
1907  * since only finite optimal solutions satisfy the KKT conditions;
1908  * we check whether all variables have finite bounds, otherwise we return */
1909  if( presoldata->updatequadbounded )
1910  {
1911  SCIP_VAR** vars;
1912  SCIP_Bool success;
1913  int nvars;
1914  int i;
1915 
1916  /* get total number of variables in the nonlinear constraint */
1917  SCIP_CALL( SCIPgetConsNVars(scip, cons, &nvars, &success) );
1918  assert(success);
1919 
1920  /* allocate memory to store variables of the nonlinear constraint */
1921  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
1922 
1923  /* get variables */
1924  SCIP_CALL( SCIPgetConsVars(scip, cons, vars, nvars, &success) );
1925  assert(success);
1926 
1927  /* check whether each variable has finite bounds */
1928  success = TRUE;
1929  for( i = 0; i < nvars && success; ++i )
1930  {
1931  SCIP_Real lb;
1932  SCIP_Real ub;
1933 
1934  assert(vars[i] != NULL);
1935 
1936  lb = SCIPvarGetLbGlobal(vars[i]);
1937  ub = SCIPvarGetUbGlobal(vars[i]);
1938 
1939  if( vars[i] != objvar && (SCIPisInfinity(scip, -lb) || SCIPisInfinity(scip, ub)) )
1940  success = FALSE;
1941  }
1942 
1943  /* free memory */
1944  SCIPfreeBufferArray(scip, &vars);
1945 
1946  if( !success )
1947  {
1948  SCIPdebugMsg(scip, "failed adding the KKT conditions, since not all variables of <%s> have finite bounds.\n",
1949  SCIPconsGetName(cons));
1950  return SCIP_OKAY;
1951  }
1952  }
1953 
1954  /* add KKT constraints */
1955 
1956  /* set up hash map */
1957  SCIP_CALL( SCIPhashmapCreate(&varhash, SCIPblkmem(scip), SCIPgetNVars(scip) + SCIPgetNFixedVars(scip)) );
1958 
1959  /* allocate buffer array */
1960  SCIP_CALL( SCIPallocBufferArray(scip, &dualconss, 2 * SCIPgetNVars(scip) + 2 * SCIPgetNFixedVars(scip)) ); /*lint !e647*/
1961 
1962  /* duplicate linconss for later use, since in the following, we create new linear constraints */
1963  if( linconss != NULL )
1964  {
1965  SCIP_CALL( SCIPduplicateBufferArray(scip, &savelinconss, linconss, nlinconss) );
1966  }
1967 
1968  /* create new objective constraint */
1969  SCIP_CALL( SCIPcreateConsBasicLinear(scip, &objcons, "objcons", 0, NULL, NULL, objrhs, objrhs) );
1970  if( SCIPisFeasNegative(scip, SCIPvarGetObj(objvar)) )
1971  {
1972  SCIP_CALL( SCIPaddCoefLinear(scip, objcons, objvar, 1.0) );
1973  }
1974  else
1975  {
1976  SCIP_CALL( SCIPaddCoefLinear(scip, objcons, objvar, -1.0) );
1977  }
1978 
1979  /* handle linear constraints */
1980  if( savelinconss != NULL )
1981  {
1982  SCIP_CALL( presolveAddKKTLinearConss(scip, objcons, savelinconss, nlinconss, varhash, dualconss, &ndualconss,
1983  naddconss, ndelconss) );
1984  }
1985 
1986  /* handle set packing constraints */
1987  SCIP_CALL( presolveAddKKTSetppcConss(scip, objcons, varhash, dualconss, &ndualconss, naddconss, ndelconss) );
1988 
1989  /* handle knapsack constraints */
1990  SCIP_CALL( presolveAddKKTKnapsackConss(scip, objcons, varhash, dualconss, &ndualconss, naddconss, ndelconss) );
1991 
1992  /* handle varbound constraints */
1993  SCIP_CALL( presolveAddKKTVarboundConss(scip, objcons, varhash, dualconss, &ndualconss, naddconss, ndelconss) );
1994 
1995  /* handle logicor constraints */
1996  SCIP_CALL( presolveAddKKTLogicorConss(scip, objcons, varhash, dualconss, &ndualconss, naddconss, ndelconss) );
1997 
1998  /* handle linear constraints associated to aggregations of variables */
1999  if( SCIPgetNFixedVars(scip) > 0 )
2000  {
2001  SCIP_CALL( presolveAddKKTAggregatedVars(scip, objcons, SCIPgetFixedVars(scip), SCIPgetNFixedVars(scip),
2002  varhash, dualconss, &ndualconss, naddconss) );
2003  }
2004 
2005  /* handle bilinear terms of quadratic constraint */
2006  SCIP_CALL( presolveAddKKTQuadBilinearTerms(scip, objcons, expr, varhash, scale, dualconss, &ndualconss,
2007  naddconss) );
2008 
2009  /* handle quadratic terms of quadratic constraint */
2010  SCIP_CALL( presolveAddKKTQuadQuadraticTerms(scip, objcons, expr, varhash, scale, dualconss, &ndualconss,
2011  naddconss) );
2012 
2013  /* handle linear terms of quadratic constraint */
2014  SCIP_CALL( presolveAddKKTQuadLinearTerms(scip, objcons, expr, varhash, objvar, scale, dualconss, &ndualconss,
2015  naddconss) );
2016 
2017  /* add/release objective constraint */
2018  SCIP_CALL( SCIPaddCons(scip, objcons) );
2019  SCIP_CALL( SCIPreleaseCons(scip, &objcons) );
2020  ++(*naddconss);
2021 
2022  /* add/release dual constraints associated to the KKT conditions */
2023  for( j = 0; j < ndualconss; ++j )
2024  {
2025  SCIP_CALL( SCIPaddCons(scip, dualconss[j]) );
2026  SCIP_CALL( SCIPreleaseCons(scip, &dualconss[j]) );
2027  }
2028  *naddconss = *naddconss + ndualconss;
2029 
2030  /* free buffer array */
2031  SCIPfreeBufferArrayNull(scip, &savelinconss);
2032  SCIPfreeBufferArray(scip, &dualconss);
2033 
2034  /* free hash map */
2035  SCIPhashmapFree(&varhash);
2036 
2037  if( SCIPgetNBinVars(scip) > 0 )
2038  SCIPdebugMsg(scip, "added the KKT conditions to the mixed-binary quadratic program\n");
2039  else
2040  SCIPdebugMsg(scip, "added the KKT conditions to the quadratic program\n");
2041 
2042  /* SCIP_CALL( SCIPwriteTransProblem(scip, "trafoQP.lp", NULL, FALSE ) ); */
2043 
2044  return SCIP_OKAY;
2045 }
2046 
2047 
2048 /*
2049  * presolver specific interface methods
2050  */
2051 
2052 /** creates the QP KKT reformulation presolver and includes it in SCIP */
2053 SCIP_RETCODE SCIPincludePresolQPKKTref(
2054  SCIP* scip /**< SCIP data structure */
2055  )
2056 {
2057  SCIP_PRESOLDATA* presoldata;
2058  SCIP_PRESOL* presol= NULL;
2059 
2060  /* alloc presolve data object */
2061  SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
2062 
2063  /* include presolver */
2064  SCIP_CALL( SCIPincludePresolBasic(scip, &presol, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS,
2065  PRESOL_TIMING, presolExecQPKKTref, presoldata) );
2066  assert(presol != NULL);
2067 
2068  /* set non fundamental callbacks via setter functions */
2069  SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyQPKKTref) );
2070  SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeQPKKTref) );
2071 
2072  /* add qpkktref presolver parameters */
2073  SCIP_CALL( SCIPaddBoolParam(scip, "presolving/" PRESOL_NAME "/addkktbinary",
2074  "if TRUE then allow binary variables for KKT update",
2075  &presoldata->addkktbinary, TRUE, FALSE, NULL, NULL) );
2076 
2077  SCIP_CALL( SCIPaddBoolParam(scip, "presolving/" PRESOL_NAME "/updatequadbounded",
2078  "if TRUE then only apply the update to QPs with bounded variables; if the variables are not bounded then a "
2079  "finite optimal solution might not exist and the KKT conditions would then be invalid",
2080  &presoldata->updatequadbounded, TRUE, TRUE, NULL, NULL) );
2081 
2082  SCIP_CALL( SCIPaddBoolParam(scip, "presolving/" PRESOL_NAME "/updatequadindef",
2083  "if TRUE then apply quadratic constraint update even if the quadratic constraint matrix is known to be indefinite",
2084  &presoldata->updatequadindef, TRUE, FALSE, NULL, NULL) );
2085 
2086  return SCIP_OKAY;
2087 }
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
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:96
SCIPgetNIntVars
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2080
SCIPisFeasZero
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:838
SCIPexprGetQuadraticData
void SCIPexprGetQuadraticData(SCIP_EXPR *expr, SCIP_Real *constant, int *nlinexprs, SCIP_EXPR ***linexprs, SCIP_Real **lincoefs, int *nquadexprs, int *nbilinexprs, SCIP_Real **eigenvalues, SCIP_Real **eigenvectors)
Definition: expr.c:4055
SCIP_Presol
Definition: struct_presol.h:37
SCIP_PRESOLDATA
struct SCIP_PresolData SCIP_PRESOLDATA
Definition: type_presol.h:42
SCIPsetPresolFree
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
Definition: scip_presol.c:147
SCIPisFeasEQ
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:773
scip_param.h
public methods for SCIP parameter handling
SCIPvarGetNLocksDownType
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3289
SCIP_DECL_PRESOLCOPY
static SCIP_DECL_PRESOLCOPY(presolCopyQPKKTref)
Definition: presol_qpkktref.c:1784
SCIPvarGetMultaggrScalars
SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var)
Definition: var.c:17702
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:18010
cons_varbound.h
Constraint handler for variable bound constraints .
SCIPcomputeExprQuadraticCurvature
SCIP_RETCODE SCIPcomputeExprQuadraticCurvature(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPRCURV *curv, SCIP_HASHMAP *assumevarfixed, SCIP_Bool storeeigeninfo)
Definition: scip_expr.c:2549
scip_mem.h
public methods for memory management
SCIPfindConshdlr
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
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
SCIPgetNVarsSetppc
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9394
SCIP_EXPRCURV_CONCAVE
Definition: type_expr.h:52
SCIPgetLhsVarbound
SCIP_Real SCIPgetLhsVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:5352
SCIPvarGetLbGlobal
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17910
SCIPgetNVarsLogicor
int SCIPgetNVarsLogicor(SCIP *scip, SCIP_CONS *cons)
Definition: cons_logicor.c:5415
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:293
SCIPvarGetNLocksUpType
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3347
SCIPdelCons
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2841
SCIPvarGetMultaggrVars
SCIP_VAR ** SCIPvarGetMultaggrVars(SCIP_VAR *var)
Definition: var.c:17690
SCIP_SETPPCTYPE_COVERING
Definition: cons_setppc.h:80
PRESOL_DESC
#define PRESOL_DESC
Definition: presol_qpkktref.c:105
checkConsQuadraticProblem
static SCIP_RETCODE checkConsQuadraticProblem(SCIP *scip, SCIP_CONS *cons, SCIP_EXPR *quadexpr, SCIP_Bool allowbinary, SCIP_VAR **objvar, SCIP_Real *scale, SCIP_Real *objrhs, SCIP_Bool *isqp)
Definition: presol_qpkktref.c:1540
SCIPgetRhsNonlinear
SCIP_Real SCIPgetRhsNonlinear(SCIP_CONS *cons)
Definition: cons_nonlinear.c:12281
SCIP_Var
Definition: struct_var.h:198
SCIPreleaseVar
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1245
SCIPvarIsBinary
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17431
SCIPisFeasNegative
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:862
createKKTComplementarityBounds
static SCIP_RETCODE createKKTComplementarityBounds(SCIP *scip, SCIP_VAR *var, SCIP_VAR *dualvar, SCIP_Bool takelb, int *naddconss)
Definition: presol_qpkktref.c:223
SCIPisFeasGE
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:825
SCIPswapPointers
void SCIPswapPointers(void **pointer1, void **pointer2)
Definition: misc.c:10291
SCIPconshdlrGetConss
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4547
FALSE
#define FALSE
Definition: def.h:87
scip_presol.h
public methods for presolving plugins
SCIPhashmapCreate
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip_numerics.c:503
SCIPsnprintf
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
TRUE
#define TRUE
Definition: def.h:86
PRESOL_NAME
#define PRESOL_NAME
Definition: presol_qpkktref.c:104
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIPincludePresolQPKKTref
SCIP_RETCODE SCIPincludePresolQPKKTref(SCIP *scip)
Definition: presol_qpkktref.c:2055
SCIPvarGetNegationConstant
SCIP_Real SCIPvarGetNegationConstant(SCIP_VAR *var)
Definition: var.c:17747
SCIPhashmapInsertInt
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3132
SCIPpresolGetData
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
Definition: presol.c:503
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
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
SCIPvarGetAggrScalar
SCIP_Real SCIPvarGetAggrScalar(SCIP_VAR *var)
Definition: var.c:17654
pub_var.h
public methods for problem variables
SCIPfreeBlockMemory
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
SCIPgetVarsKnapsack
SCIP_VAR ** SCIPgetVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13745
PRESOL_PRIORITY
#define PRESOL_PRIORITY
Definition: presol_qpkktref.c:106
SCIPduplicateBufferArray
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:123
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
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
SCIPgetVarVarbound
SCIP_VAR * SCIPgetVarVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:5398
cons_setppc.h
Constraint handler for the set partitioning / packing / covering constraints .
scip_var.h
public methods for SCIP variables
SCIPvarGetNegationVar
SCIP_VAR * SCIPvarGetNegationVar(SCIP_VAR *var)
Definition: var.c:17736
SCIPdebugMsg
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIPgetRhsLinear
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18431
SCIPaddCoefLinear
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
Definition: cons_linear.c:18162
scip_numerics.h
public methods for numerical tolerances
SCIPhashmapExists
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3363
SCIPgetNFixedVars
int SCIPgetNFixedVars(SCIP *scip)
Definition: scip_prob.c:2307
SCIPgetFixedVars
SCIP_VAR ** SCIPgetFixedVars(SCIP *scip)
Definition: scip_prob.c:2264
SCIPvarGetUbGlobal
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17920
SCIP_DECL_PRESOLEXEC
static SCIP_DECL_PRESOLEXEC(presolExecQPKKTref)
Definition: presol_qpkktref.c:1816
SCIP_HashMap
Definition: struct_misc.h:128
presolveAddKKTQuadBilinearTerms
static SCIP_RETCODE presolveAddKKTQuadBilinearTerms(SCIP *scip, SCIP_CONS *objcons, SCIP_EXPR *quadexpr, SCIP_HASHMAP *varhash, SCIP_Real scale, SCIP_CONS **dualconss, int *ndualconss, int *naddconss)
Definition: presol_qpkktref.c:1274
pub_cons.h
public methods for managing constraints
cons_knapsack.h
Constraint handler for knapsack constraints of the form , x binary and .
SCIPgetRhsVarbound
SCIP_Real SCIPgetRhsVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:5375
SCIP_Cons
Definition: struct_cons.h:37
SCIPerrorMessage
#define SCIPerrorMessage
Definition: pub_message.h:55
SCIPgetConsNVars
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
Definition: scip_cons.c:2558
SCIPaddCons
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2768
SCIPvarGetLbOriginal
SCIP_Real SCIPvarGetLbOriginal(SCIP_VAR *var)
Definition: var.c:17856
SCIP_EXPRCURV_CONVEX
Definition: type_expr.h:51
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
SCIPaddVarSOS1
SCIP_RETCODE SCIPaddVarSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real weight)
Definition: cons_sos1.c:10513
SCIPgetVarExprVar
SCIP_VAR * SCIPgetVarExprVar(SCIP_EXPR *expr)
Definition: expr_var.c:403
cons_logicor.h
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
SCIPvarGetUbOriginal
SCIP_Real SCIPvarGetUbOriginal(SCIP_VAR *var)
Definition: var.c:17876
SCIPpresolSetData
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
Definition: presol.c:513
SCIPfreeBufferArrayNull
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:128
SCIPblkmem
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
SCIPconsGetName
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8085
SCIPvarGetAggrConstant
SCIP_Real SCIPvarGetAggrConstant(SCIP_VAR *var)
Definition: var.c:17666
SCIPgetVarsLogicor
SCIP_VAR ** SCIPgetVarsLogicor(SCIP *scip, SCIP_CONS *cons)
Definition: cons_logicor.c:5438
SCIPvarGetName
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17251
SCIPhashmapFree
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3048
SCIPgetExprNonlinear
SCIP_EXPR * SCIPgetExprNonlinear(SCIP_CONS *cons)
Definition: cons_nonlinear.c:12249
SCIP_VARSTATUS_AGGREGATED
Definition: type_var.h:44
SCIPexprGetQuadraticQuadTerm
void SCIPexprGetQuadraticQuadTerm(SCIP_EXPR *quadexpr, int termidx, SCIP_EXPR **expr, SCIP_Real *lincoef, SCIP_Real *sqrcoef, int *nadjbilin, int **adjbilin, SCIP_EXPR **sqrexpr)
Definition: expr.c:4102
NULL
#define NULL
Definition: lpi_spx1.cpp:155
REALABS
#define REALABS(x)
Definition: def.h:201
SCIP_OKAY
Definition: type_retcode.h:33
SCIP_SETPPCTYPE_PARTITIONING
Definition: cons_setppc.h:78
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:384
SCIPvarGetMultaggrConstant
SCIP_Real SCIPvarGetMultaggrConstant(SCIP_VAR *var)
Definition: var.c:17714
SCIPisFeasLE
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:799
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
SCIPgetConsVars
SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
Definition: scip_cons.c:2514
SCIPconshdlrGetNConss
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4590
scip_cons.h
public methods for constraint handler plugins and constraints
SCIP_ERROR
Definition: type_retcode.h:34
SCIPgetCapacityKnapsack
SCIP_Longint SCIPgetCapacityKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13665
SCIP_Expr
Definition: struct_expr.h:95
SCIPgetVbdvarVarbound
SCIP_VAR * SCIPgetVbdvarVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:5421
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
pub_misc.h
public data structures and miscellaneous methods
SCIPcheckQuadraticNonlinear
SCIP_RETCODE SCIPcheckQuadraticNonlinear(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *isquadratic)
Definition: cons_nonlinear.c:12347
SCIP_Bool
#define SCIP_Bool
Definition: def.h:84
createKKTComplementarityBinary
static SCIP_RETCODE createKKTComplementarityBinary(SCIP *scip, SCIP_VAR *var, SCIP_VAR *dualbin1, SCIP_VAR *dualbin2, int *naddconss)
Definition: presol_qpkktref.c:317
SCIP_EXPRCURV
SCIP_EXPRCURV
Definition: type_expr.h:48
SCIPgetTypeSetppc
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9440
cons_nonlinear.h
constraint handler for nonlinear constraints specified by algebraic expressions
SCIP_VARSTATUS_NEGATED
Definition: type_var.h:46
SCIP_DECL_PRESOLFREE
static SCIP_DECL_PRESOLFREE(presolFreeQPKKTref)
Definition: presol_qpkktref.c:1799
SCIPpresolGetName
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:590
SCIPvarGetObj
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17758
SCIPvarGetAggrVar
SCIP_VAR * SCIPvarGetAggrVar(SCIP_VAR *var)
Definition: var.c:17642
SCIP_VARSTATUS_MULTAGGR
Definition: type_var.h:45
SCIPgetVbdcoefVarbound
SCIP_Real SCIPgetVbdcoefVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:5444
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, .
SCIPgetNObjVars
int SCIPgetNObjVars(SCIP *scip)
Definition: scip_prob.c:2218
SCIPchgRhsLinear
SCIP_RETCODE SCIPchgRhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
Definition: cons_linear.c:18476
SCIPvarGetMultaggrNVars
int SCIPvarGetMultaggrNVars(SCIP_VAR *var)
Definition: var.c:17678
SCIPisInfinity
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:514
SCIPvarGetOrigvarSum
SCIP_RETCODE SCIPvarGetOrigvarSum(SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: var.c:12773
SCIPgetNBinVars
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2035
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
SCIPgetVarsSetppc
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9417
SCIPgetNVars
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1990
pub_presol.h
public methods for presolvers
presolveAddKKTQuadLinearTerms
static SCIP_RETCODE presolveAddKKTQuadLinearTerms(SCIP *scip, SCIP_CONS *objcons, SCIP_EXPR *quadexpr, SCIP_HASHMAP *varhash, SCIP_VAR *objvar, SCIP_Real scale, SCIP_CONS **dualconss, int *ndualconss, int *naddconss)
Definition: presol_qpkktref.c:1416
SCIP_SETPPCTYPE
enum SCIP_SetppcType SCIP_SETPPCTYPE
Definition: cons_setppc.h:82
scalars
static const SCIP_Real scalars[]
Definition: lp.c:5736
SCIPaddVar
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1666
SCIPgetVarsLinear
SCIP_VAR ** SCIPgetVarsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18518
PRESOL_MAXROUNDS
#define PRESOL_MAXROUNDS
Definition: presol_qpkktref.c:109
SCIPgetNConss
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3040
SCIPreleaseCons
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
SCIPsetPresolCopy
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip_presol.c:131
pub_message.h
public methods for message output
SCIP_LOCKTYPE_MODEL
Definition: type_var.h:84
SCIPisFeasPositive
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:850
SCIPisExprVar
SCIP_Bool SCIPisExprVar(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1421
SCIPexprGetQuadraticBilinTerm
void SCIPexprGetQuadraticBilinTerm(SCIP_EXPR *expr, int termidx, SCIP_EXPR **expr1, SCIP_EXPR **expr2, SCIP_Real *coef, int *pos2, SCIP_EXPR **prodexpr)
Definition: expr.c:4145
SCIPvarGetStatus
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17370
SCIP_Real
#define SCIP_Real
Definition: def.h:177
cons_sos1.h
constraint handler for SOS type 1 constraints
SCIPgetNVarsKnapsack
int SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13722
scip_message.h
public methods for message handling
SCIP_Longint
#define SCIP_Longint
Definition: def.h:162
SCIPgetValsLinear
SCIP_Real * SCIPgetValsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18542
SCIPchgLhsLinear
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
Definition: cons_linear.c:18455
presolveAddKKTQuadQuadraticTerms
static SCIP_RETCODE presolveAddKKTQuadQuadraticTerms(SCIP *scip, SCIP_CONS *objcons, SCIP_EXPR *quadexpr, SCIP_HASHMAP *varhash, SCIP_Real scale, SCIP_CONS **dualconss, int *ndualconss, int *naddconss)
Definition: presol_qpkktref.c:1352
PRESOL_TIMING
#define PRESOL_TIMING
Definition: presol_qpkktref.c:112
SCIPallocBlockMemory
SCIPallocBlockMemory(scip, subsol))
SCIP_INVALIDDATA
Definition: type_retcode.h:43
SCIPhashmapGetImageInt
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3221
SCIPgetWeightsKnapsack
SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13768
scip_prob.h
public methods for global and local (sub)problems
SCIP_VARSTATUS_FIXED
Definition: type_var.h:43
SCIPgetLhsNonlinear
SCIP_Real SCIPgetLhsNonlinear(SCIP_CONS *cons)
Definition: cons_nonlinear.c:12265
SCIPgetNVarsLinear
int SCIPgetNVarsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18494
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
SCIPgetLhsLinear
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18407
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
SCIPgetLinvarMayIncreaseNonlinear
void SCIPgetLinvarMayIncreaseNonlinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **var, SCIP_Real *coef)
Definition: cons_nonlinear.c:12723
presol_qpkktref.h
qpkktref presolver
memory.h
memory allocation routines
SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:58