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