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