Scippy

SCIP

Solving Constraint Integer Programs

cons_quadratic.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2014 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_quadratic.h
17  * @ingroup CONSHDLRS
18  * @brief constraint handler for quadratic constraints \f$\textrm{lhs} \leq \sum_{i,j=1}^n a_{i,j} x_ix_j + \sum_{i=1}^n b_i x_i \leq \textrm{rhs}\f$
19  * @author Stefan Vigerske
20  *
21  * This constraint handler handles constraints of the form
22  * \f[
23  * \textrm{lhs} \leq \sum_{i,j=1}^n a_{i,j} x_ix_j + \sum_{i=1}^n b_i x_i \leq \textrm{rhs}
24  * \f]
25  *
26  * Constraints are enforced by separation, domain propagation, and spatial branching.
27  *
28  * For semidefinite matrices \f$A=(a_{i,j})_{i,j}\f$, cuts based on linearization of \f$\langle x, Ax\rangle\f$ are implemented.
29  * For underestimating a non-convex term, McCormick underestimators and secants for univariate concave quadratic terms are implemented.
30  * If \f$\langle x, Ax\rangle\f$ is factorable (i.e., can be written as product of two linear functions),
31  * specialized separation techniques (e.g., lifted tangent inequalities) that take the constraint sides into account are applied.
32  *
33  * Branching is performed for variables in nonconvex terms, if the relaxation solution cannot be separated.
34  * Further, domain propagation is applied.
35  *
36  * During presolve, variable products which contain binary variables may be reformulated into linear constraints, thereby introducing new variables.
37  *
38  * See also
39  * @par
40  * Timo Berthold and Stefan Heinz and Stefan Vigerske@n
41  * <a href="http://dx.doi.org/10.1007/978-1-4614-1927-3">Extending a CIP framework to solve MIQCPs</a>@n
42  * In: Jon Lee and Sven Leyffer (eds.),
43  * Mixed-integer nonlinear optimization: Algorithmic advances and applications,
44  * IMA volumes in Mathematics and its Applications, volume 154, 427-444, 2012.
45  *
46  * @par
47  * Stefan Vigerske@n
48  * Decomposition of Multistage Stochastic Programs and a Constraint Integer Programming Approach to Mixed-Integer Nonlinear Programming@n
49  * PhD Thesis, Humboldt-University Berlin, 2012, submitted.
50  *
51  * @par
52  * Pietro Belotti and Andrew J. Miller and Mahdi Namazifar@n
53  * Linear inequalities for bounded products of variables@n
54  * SIAG/OPT Views-and-News 22:1, 1-8, 2011.
55  */
56 
57 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
58 
59 #ifndef __SCIP_CONS_QUADRATIC_H__
60 #define __SCIP_CONS_QUADRATIC_H__
61 
62 #include "scip/scip.h"
63 #include "scip/intervalarith.h"
64 #include "nlpi/type_nlpi.h"
65 
66 #ifdef __cplusplus
67 extern "C" {
68 #endif
69 
70 /** event data for variable bound changes in quadratic constraints */
71 typedef struct SCIP_QuadVarEventData SCIP_QUADVAREVENTDATA;
72 
73 /** data structure to store a single term associated to a quadratic variable
74  */
75 struct SCIP_QuadVarTerm
76 {
77  SCIP_VAR* var; /**< quadratic variable */
78  SCIP_Real lincoef; /**< linear coefficient of variable */
79  SCIP_Real sqrcoef; /**< square coefficient of variable */
80 
81  int nadjbilin; /**< number of bilinear terms this variable is involved in */
82  int adjbilinsize; /**< size of adjacent bilinear terms array */
83  int* adjbilin; /**< indices of associated bilinear terms */
84 
85  SCIP_QUADVAREVENTDATA* eventdata; /**< event data for bound change events */
86 };
87 typedef struct SCIP_QuadVarTerm SCIP_QUADVARTERM;
88 
89 /** data structure to store a single bilinear term (similar to SCIP_QUADELEM)
90  * except for temporary reasons, we assume that the index of var1 is smaller than the index of var2
91  */
92 struct SCIP_BilinTerm
93 {
94  SCIP_VAR* var1;
95  SCIP_VAR* var2;
96  SCIP_Real coef;
97 };
98 typedef struct SCIP_BilinTerm SCIP_BILINTERM;
99 
100 
101 /** upgrading method for quadratic constraints into more specific constraints
102  *
103  * the method might upgrade a quadratic constraint into a set of quadratic constraints
104  * the caller provided an array upgdconss to store upgrade constraints
105  * the length of upgdconss is given by upgdconsssize
106  * if an upgrade is not possible, set *nupgdconss to zero
107  * if more than upgdconsssize many constraints shall replace cons, the function
108  * should return the required number as negated value in *nupgdconss
109  * i.e., if cons should be replaced by 3 constraints, the function should set
110  * *nupgdconss to -3 and return with SCIP_OKAY
111  *
112  * input:
113  * - scip : SCIP main data structure
114  * - cons : the quadratic constraint to upgrade
115  * - nbinlin : number of binary variables in linear part
116  * - nbinquad : number of binary variables in quadratic part
117  * - nintlin : number of integer variables in linear part
118  * - nintquad : number of integer variables in quadratic part
119  * - nimpllin : number of implicit integer variables in linear part
120  * - nimplquad : number of implicit integer variables in quadratic part
121  * - ncontlin : number of continuous variables in linear part
122  * - ncontquad : number of continuous variables in quadratic part
123  * - integral : TRUE iff constraints activity value is always integral
124  * - nupgdconss : pointer to store number of constraints that replace this constraint
125  * - upgdconss : array to store constraints that replace this constraint
126  * - upgdconsssize : length of the provided upgdconss array
127  */
128 #define SCIP_DECL_QUADCONSUPGD(x) SCIP_RETCODE x (SCIP* scip, SCIP_CONS* cons, \
129  int nbinlin, int nbinquad, int nintlin, int nintquad, int nimpllin, int nimplquad, int ncontlin, int ncontquad, \
130  SCIP_Bool integral, int* nupgdconss, SCIP_CONS** upgdconss, int upgdconsssize)
131 
132 /** creates the handler for quadratic constraints and includes it in SCIP */
133 extern
135  SCIP* scip /**< SCIP data structure */
136  );
137 
138 /** includes a quadratic constraint upgrade method into the quadratic constraint handler */
139 extern
141  SCIP* scip, /**< SCIP data structure */
142  SCIP_DECL_QUADCONSUPGD((*quadconsupgd)), /**< method to call for upgrading quadratic constraint */
143  int priority, /**< priority of upgrading method */
144  SCIP_Bool active, /**< should the upgrading method be active by default? */
145  const char* conshdlrname /**< name of the constraint handler */
146  );
147 
148 /** Creates and captures a quadratic constraint.
149  *
150  * The constraint should be given in the form
151  * \f[
152  * \ell \leq \sum_{i=1}^n b_i x_i + \sum_{j=1}^m a_j y_j z_j \leq u,
153  * \f]
154  * where \f$x_i = y_j = z_k\f$ is possible.
155  *
156  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
157  */
158 extern
160  SCIP* scip, /**< SCIP data structure */
161  SCIP_CONS** cons, /**< pointer to hold the created constraint */
162  const char* name, /**< name of constraint */
163  int nlinvars, /**< number of linear terms (n) */
164  SCIP_VAR** linvars, /**< variables in linear part (x_i) or NULL if nlinvars == 0 */
165  SCIP_Real* lincoefs, /**< coefficients of variables in linear part (b_i) or NULL if nlinvars == 0 */
166  int nquadterms, /**< number of quadratic terms (m) */
167  SCIP_VAR** quadvars1, /**< array with first variables in quadratic terms (y_j) or NULL if nquadterms == 0 */
168  SCIP_VAR** quadvars2, /**< array with second variables in quadratic terms (z_j) or NULL if nquadterms == 0 */
169  SCIP_Real* quadcoeffs, /**< array with coefficients of quadratic terms (a_j) or NULL if nquadterms == 0 */
170  SCIP_Real lhs, /**< left hand side of quadratic equation (l) */
171  SCIP_Real rhs, /**< right hand side of quadratic equation (u) */
172  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
173  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
174  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
175  * Usually set to TRUE. */
176  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
177  * TRUE for model constraints, FALSE for additional, redundant constraints. */
178  SCIP_Bool check, /**< should the constraint be checked for feasibility?
179  * TRUE for model constraints, FALSE for additional, redundant constraints. */
180  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
181  * Usually set to TRUE. */
182  SCIP_Bool local, /**< is constraint only valid locally?
183  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
184  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
185  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
186  * adds coefficients to this constraint. */
187  SCIP_Bool dynamic, /**< is constraint subject to aging?
188  * Usually set to FALSE. Set to TRUE for own cuts which
189  * are separated as constraints. */
190  SCIP_Bool removable /**< should the relaxation be removed from the LP due to aging or cleanup?
191  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
192  );
193 
194 /** creates and captures a quadratic constraint
195  * in its most basic variant, i. e., with all constraint flags set to their default values, which can be set
196  * afterwards using SCIPsetConsFLAGNAME() in scip.h
197  *
198  * The constraint should be given in the form
199  * \f[
200  * \ell \leq \sum_{i=1}^n b_i x_i + \sum_{j=1}^m a_j y_jz_j \leq u,
201  * \f]
202  * where \f$x_i = y_j = z_k\f$ is possible.
203  *
204  * @see SCIPcreateConsQuadratic() for the default constraint flag configuration
205  *
206 
207  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
208  */
209 extern
211  SCIP* scip, /**< SCIP data structure */
212  SCIP_CONS** cons, /**< pointer to hold the created constraint */
213  const char* name, /**< name of constraint */
214  int nlinvars, /**< number of linear terms (n) */
215  SCIP_VAR** linvars, /**< array with variables in linear part (x_i) */
216  SCIP_Real* lincoefs, /**< array with coefficients of variables in linear part (b_i) */
217  int nquadterms, /**< number of quadratic terms (m) */
218  SCIP_VAR** quadvars1, /**< array with first variables in quadratic terms (y_j) */
219  SCIP_VAR** quadvars2, /**< array with second variables in quadratic terms (z_j) */
220  SCIP_Real* quadcoefs, /**< array with coefficients of quadratic terms (a_j) */
221  SCIP_Real lhs, /**< left hand side of quadratic equation (ell) */
222  SCIP_Real rhs /**< right hand side of quadratic equation (u) */
223  );
224 
225 /** creates and captures a quadratic constraint.
226  *
227  * The constraint should be given in the form
228  * \f[
229  * \ell \leq \sum_{i=1}^n b_i x_i + \sum_{j=1}^m (a_j y_j^2 + b_j y_j) + \sum_{k=1}^p c_k v_k w_k \leq u.
230  * \f]
231  *
232  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
233  */
234 extern
236  SCIP* scip, /**< SCIP data structure */
237  SCIP_CONS** cons, /**< pointer to hold the created constraint */
238  const char* name, /**< name of constraint */
239  int nlinvars, /**< number of linear terms (n) */
240  SCIP_VAR** linvars, /**< array with variables in linear part (x_i) */
241  SCIP_Real* lincoefs, /**< array with coefficients of variables in linear part (b_i) */
242  int nquadvarterms, /**< number of quadratic terms (m) */
243  SCIP_QUADVARTERM* quadvarterms, /**< quadratic variable terms */
244  int nbilinterms, /**< number of bilinear terms (p) */
245  SCIP_BILINTERM* bilinterms, /**< bilinear terms */
246  SCIP_Real lhs, /**< constraint left hand side (ell) */
247  SCIP_Real rhs, /**< constraint right hand side (u) */
248  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? */
249  SCIP_Bool separate, /**< should the constraint be separated during LP processing? */
250  SCIP_Bool enforce, /**< should the constraint be enforced during node processing? */
251  SCIP_Bool check, /**< should the constraint be checked for feasibility? */
252  SCIP_Bool propagate, /**< should the constraint be propagated during node processing? */
253  SCIP_Bool local, /**< is constraint only valid locally? */
254  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)? */
255  SCIP_Bool dynamic, /**< is constraint dynamic? */
256  SCIP_Bool removable /**< should the constraint be removed from the LP due to aging or cleanup? */
257  );
258 
259 /** creates and captures a quadratic constraint
260  * in its most basic variant, i. e., with all constraint flags set to their default values, which can be set
261  * afterwards using SCIPsetConsFLAGNAME() in scip.h
262  *
263  * The constraint should be given in the form
264  * \f[
265  * \ell \leq \sum_{i=1}^n b_i x_i + \sum_{j=1}^m (a_j y_j^2 + b_j y_j) + \sum_{k=1}^p c_kv_kw_k \leq u.
266  * \f]
267  *
268  * @see SCIPcreateConsQuadratic2() for the default constraint flag configuration
269  *
270  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
271  */
272 extern
274  SCIP* scip, /**< SCIP data structure */
275  SCIP_CONS** cons, /**< pointer to hold the created constraint */
276  const char* name, /**< name of constraint */
277  int nlinvars, /**< number of linear terms (n) */
278  SCIP_VAR** linvars, /**< array with variables in linear part (x_i) */
279  SCIP_Real* lincoefs, /**< array with coefficients of variables in linear part (b_i) */
280  int nquadvarterms, /**< number of quadratic terms (m) */
281  SCIP_QUADVARTERM* quadvarterms, /**< quadratic variable terms */
282  int nbilinterms, /**< number of bilinear terms (p) */
283  SCIP_BILINTERM* bilinterms, /**< bilinear terms */
284  SCIP_Real lhs, /**< constraint left hand side (ell) */
285  SCIP_Real rhs /**< constraint right hand side (u) */
286  );
287 
288 /** Adds a constant to the constraint function, that is, subtracts a constant from both sides */
289 extern
291  SCIP* scip, /**< SCIP data structure */
292  SCIP_CONS* cons, /**< constraint */
293  SCIP_Real constant /**< constant to subtract from both sides */
294  );
295 
296 /** Adds a linear variable with coefficient to a quadratic constraint.
297  */
298 extern
300  SCIP* scip, /**< SCIP data structure */
301  SCIP_CONS* cons, /**< constraint */
302  SCIP_VAR* var, /**< variable */
303  SCIP_Real coef /**< coefficient of variable */
304  );
305 
306 /** Adds a quadratic variable with linear and square coefficient to a quadratic constraint.
307  */
308 extern
310  SCIP* scip, /**< SCIP data structure */
311  SCIP_CONS* cons, /**< constraint */
312  SCIP_VAR* var, /**< variable */
313  SCIP_Real lincoef, /**< linear coefficient of variable */
314  SCIP_Real sqrcoef /**< square coefficient of variable */
315  );
316 
317 /** Adds a linear coefficient for a quadratic variable.
318  *
319  * Variable will be added with square coefficient 0.0 if not existing yet.
320  */
321 extern
323  SCIP* scip, /**< SCIP data structure */
324  SCIP_CONS* cons, /**< constraint */
325  SCIP_VAR* var, /**< variable */
326  SCIP_Real coef /**< value to add to linear coefficient of variable */
327  );
328 
329 /** Adds a square coefficient for a quadratic variable.
330  *
331  * Variable will be added with linear coefficient 0.0 if not existing yet.
332  */
333 extern
335  SCIP* scip, /**< SCIP data structure */
336  SCIP_CONS* cons, /**< constraint */
337  SCIP_VAR* var, /**< variable */
338  SCIP_Real coef /**< value to add to square coefficient of variable */
339  );
340 
341 /** Adds a bilinear term to a quadratic constraint.
342  *
343  * Variables will be added with linear and square coefficient 0.0 if not existing yet.
344  * If variables are equal, only the square coefficient of the variable is updated.
345  */
346 extern
348  SCIP* scip, /**< SCIP data structure */
349  SCIP_CONS* cons, /**< constraint */
350  SCIP_VAR* var1, /**< first variable */
351  SCIP_VAR* var2, /**< second variable */
352  SCIP_Real coef /**< coefficient of bilinear term */
353  );
354 
355 /** Gets the quadratic constraint as a nonlinear row representation.
356  */
357 extern
359  SCIP* scip, /**< SCIP data structure */
360  SCIP_CONS* cons, /**< constraint */
361  SCIP_NLROW** nlrow /**< pointer to store nonlinear row */
362  );
363 
364 /** Gets the number of variables in the linear part of a quadratic constraint.
365  */
366 extern
368  SCIP* scip, /**< SCIP data structure */
369  SCIP_CONS* cons /**< constraint */
370  );
371 
372 /** Gets the variables in the linear part of a quadratic constraint.
373  * Length is given by SCIPgetNLinearVarsQuadratic.
374  */
375 extern
377  SCIP* scip, /**< SCIP data structure */
378  SCIP_CONS* cons /**< constraint */
379  );
380 
381 /** Gets the coefficients in the linear part of a quadratic constraint.
382  * Length is given by SCIPgetNQuadVarsQuadratic.
383  */
384 extern
386  SCIP* scip, /**< SCIP data structure */
387  SCIP_CONS* cons /**< constraint */
388  );
389 
390 /** Gets the number of quadratic variable terms of a quadratic constraint.
391  */
392 extern
394  SCIP* scip, /**< SCIP data structure */
395  SCIP_CONS* cons /**< constraint */
396  );
397 
398 /** Gets the quadratic variable terms of a quadratic constraint.
399  * Length is given by SCIPgetNQuadVarTermsQuadratic.
400  */
401 extern
403  SCIP* scip, /**< SCIP data structure */
404  SCIP_CONS* cons /**< constraint */
405  );
406 
407 /** Ensures that quadratic variable terms are sorted. */
408 extern
410  SCIP* scip, /**< SCIP data structure */
411  SCIP_CONS* cons /**< constraint */
412  );
413 
414 /** Finds the position of a quadratic variable term for a given variable.
415  *
416  * @note If the quadratic variable terms have not been sorted before, then a search may reorder the current order of the terms.
417  */
418 extern
420  SCIP* scip, /**< SCIP data structure */
421  SCIP_CONS* cons, /**< constraint */
422  SCIP_VAR* var, /**< variable to search for */
423  int* pos /**< buffer to store position of quadvarterm for var, or -1 if not found */
424  );
425 
426 /** Gets the number of bilinear terms of a quadratic constraint.
427  */
428 extern
430  SCIP* scip, /**< SCIP data structure */
431  SCIP_CONS* cons /**< constraint */
432  );
433 
434 /** Gets the bilinear terms of a quadratic constraint.
435  * Length is given by SCIPgetNBilinTermQuadratic.
436  */
437 extern
439  SCIP* scip, /**< SCIP data structure */
440  SCIP_CONS* cons /**< constraint */
441  );
442 
443 /** Gets the left hand side of a quadratic constraint.
444  */
445 extern
447  SCIP* scip, /**< SCIP data structure */
448  SCIP_CONS* cons /**< constraint */
449  );
450 
451 /** Gets the right hand side of a quadratic constraint.
452  */
453 extern
455  SCIP* scip, /**< SCIP data structure */
456  SCIP_CONS* cons /**< constraint */
457  );
458 
459 /** Check the quadratic function of a quadratic constraint for its semi-definiteness, if not done yet.
460  */
461 extern
463  SCIP* scip, /**< SCIP data structure */
464  SCIP_CONS* cons /**< constraint */
465  );
466 
467 /** Indicates whether the quadratic function of a quadratic constraint is (known to be) convex.
468  */
469 extern
471  SCIP* scip, /**< SCIP data structure */
472  SCIP_CONS* cons /**< constraint */
473  );
474 
475 /** Indicates whether the quadratic function of a quadratic constraint is (known to be) concave.
476  */
477 extern
479  SCIP* scip, /**< SCIP data structure */
480  SCIP_CONS* cons /**< constraint */
481  );
482 
483 /** Gets the violation of a constraint by a solution. */
484 extern
486  SCIP* scip, /**< SCIP data structure */
487  SCIP_CONS* cons, /**< constraint */
488  SCIP_SOL* sol, /**< solution which violation to calculate, or NULL for LP solution */
489  SCIP_Real* violation /**< pointer to store violation of constraint */
490  );
491 
492 /** Indicates whether the quadratic constraint is local w.r.t. the current local bounds.
493  *
494  * That is, checks whether each variable with a square term is fixed and for each bilinear term at least one variable is fixed.
495  */
496 extern
498  SCIP* scip, /**< SCIP data structure */
499  SCIP_CONS* cons /**< constraint */
500 );
501 
502 /** Adds the constraint to an NLPI problem. */
503 extern
505  SCIP* scip, /**< SCIP data structure */
506  SCIP_CONS* cons, /**< constraint */
507  SCIP_NLPI* nlpi, /**< interface to NLP solver */
508  SCIP_NLPIPROBLEM* nlpiprob, /**< NLPI problem where to add constraint */
509  SCIP_HASHMAP* scipvar2nlpivar, /**< mapping from SCIP variables to variable indices in NLPI */
510  SCIP_Bool names /**< whether to pass constraint names to NLPI */
511  );
512 
513 #ifdef __cplusplus
514 }
515 #endif
516 
517 #endif
518