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