1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB)                      */
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 	}
2097