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-2017 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  */
22 
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24 
25 #ifndef __SCIP_CONS_QUADRATIC_H__
26 #define __SCIP_CONS_QUADRATIC_H__
27 
28 #include "scip/scip.h"
29 #include "scip/intervalarith.h"
30 #include "nlpi/type_nlpi.h"
31 
32 #ifdef __cplusplus
33 extern "C" {
34 #endif
35 
36 
37 /** creates the handler for quadratic constraints and includes it in SCIP
38  *
39  * @ingroup ConshdlrIncludes
40  * */
41 extern
43  SCIP* scip /**< SCIP data structure */
44  );
45 
46 /**@addtogroup CONSHDLRS
47  *
48  * @{
49  *
50  * @name Quadratic Constraints
51  *
52  * @{
53  *
54  * This constraint handler handles constraints of the form
55  * \f[
56  * \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}
57  * \f]
58  *
59  * Constraints are enforced by separation, domain propagation, and spatial branching.
60  *
61  * For semidefinite matrices \f$A=(a_{i,j})_{i,j}\f$, cuts based on linearization of \f$\langle x, Ax\rangle\f$ are implemented.
62  * For underestimating a non-convex term, McCormick underestimators and secants for univariate concave quadratic terms are implemented.
63  * If \f$\langle x, Ax\rangle\f$ is factorable (i.e., can be written as product of two linear functions),
64  * specialized separation techniques (e.g., lifted tangent inequalities) that take the constraint sides into account are applied.
65  *
66  * Branching is performed for variables in nonconvex terms, if the relaxation solution cannot be separated.
67  * Further, domain propagation is applied.
68  *
69  * During presolve, variable products which contain binary variables may be reformulated into linear constraints, thereby introducing new variables.
70  *
71  * See also
72  * @par
73  * Timo Berthold and Stefan Heinz and Stefan Vigerske@n
74  * <a href="http://dx.doi.org/10.1007/978-1-4614-1927-3">Extending a CIP framework to solve MIQCPs</a>@n
75  * In: Jon Lee and Sven Leyffer (eds.),
76  * Mixed-integer nonlinear optimization: Algorithmic advances and applications,
77  * IMA volumes in Mathematics and its Applications, volume 154, 427-444, 2012.
78  *
79  * @par
80  * Stefan Vigerske@n
81  * Decomposition of Multistage Stochastic Programs and a Constraint Integer Programming Approach to Mixed-Integer Nonlinear Programming@n
82  * PhD Thesis, Humboldt-University Berlin, 2012, submitted.
83  *
84  * @par
85  * Pietro Belotti and Andrew J. Miller and Mahdi Namazifar@n
86  * Linear inequalities for bounded products of variables@n
87  * SIAG/OPT Views-and-News 22:1, 1-8, 2011.
88  */
89 
90 /** event data for variable bound changes in quadratic constraints */
91 typedef struct SCIP_QuadVarEventData SCIP_QUADVAREVENTDATA;
92 
93 /** data structure to store a single term associated to a quadratic variable
94  */
96 {
97  SCIP_VAR* var; /**< quadratic variable */
98  SCIP_Real lincoef; /**< linear coefficient of variable */
99  SCIP_Real sqrcoef; /**< square coefficient of variable */
100 
101  int nadjbilin; /**< number of bilinear terms this variable is involved in */
102  int adjbilinsize; /**< size of adjacent bilinear terms array */
103  int* adjbilin; /**< indices of associated bilinear terms */
104 
105  SCIP_QUADVAREVENTDATA* eventdata; /**< event data for bound change events */
106 };
108 
109 /** data structure to store a single bilinear term (similar to SCIP_QUADELEM)
110  * except for temporary reasons, we assume that the index of var1 is smaller than the index of var2
111  */
113 {
117 };
119 
120 /** storage for a linear row in preparation
121  *
122  * Uses to assemble data that could eventually make a SCIP_ROW.
123  * @note Only one-sided rows are allowed here.
124  */
126 {
127  SCIP_VAR** vars; /**< variables */
128  SCIP_Real* coefs; /**< coefficients of variables */
129  int nvars; /**< number of variables (= number of coefficients) */
130  int varssize; /**< length of variables array (= lengths of coefficients array) */
131  SCIP_Real side; /**< side */
132  SCIP_SIDETYPE sidetype; /**< type of side */
133  SCIP_Bool local; /**< whether the row is only locally valid (i.e., for the current node) */
134  char name[SCIP_MAXSTRLEN]; /**< row name */
135 };
136 typedef struct SCIP_RowPrep SCIP_ROWPREP;
137 
138 /** upgrading method for quadratic constraints into more specific constraints
139  *
140  * the method might upgrade a quadratic constraint into a set of quadratic constraints
141  * the caller provided an array upgdconss to store upgrade constraints
142  * the length of upgdconss is given by upgdconsssize
143  * if an upgrade is not possible, set *nupgdconss to zero
144  * if more than upgdconsssize many constraints shall replace cons, the function
145  * should return the required number as negated value in *nupgdconss
146  * i.e., if cons should be replaced by 3 constraints, the function should set
147  * *nupgdconss to -3 and return with SCIP_OKAY
148  *
149  * input:
150  * - scip : SCIP main data structure
151  * - cons : the quadratic constraint to upgrade
152  * - nbinlin : number of binary variables in linear part
153  * - nbinquad : number of binary variables in quadratic part
154  * - nintlin : number of integer variables in linear part
155  * - nintquad : number of integer variables in quadratic part
156  * - nimpllin : number of implicit integer variables in linear part
157  * - nimplquad : number of implicit integer variables in quadratic part
158  * - ncontlin : number of continuous variables in linear part
159  * - ncontquad : number of continuous variables in quadratic part
160  * - integral : TRUE iff constraints activity value is always integral
161  * - nupgdconss : pointer to store number of constraints that replace this constraint
162  * - upgdconss : array to store constraints that replace this constraint
163  * - upgdconsssize : length of the provided upgdconss array
164  * - presoltiming : current presolve timing
165  */
166 #define SCIP_DECL_QUADCONSUPGD(x) SCIP_RETCODE x (SCIP* scip, SCIP_CONS* cons, \
167  int nbinlin, int nbinquad, int nintlin, int nintquad, int nimpllin, int nimplquad, int ncontlin, int ncontquad, \
168  SCIP_Bool integral, int* nupgdconss, SCIP_CONS** upgdconss, int upgdconsssize, SCIP_PRESOLTIMING presoltiming)
169 
170 /** includes a quadratic constraint upgrade method into the quadratic constraint handler */
171 extern
173  SCIP* scip, /**< SCIP data structure */
174  SCIP_DECL_QUADCONSUPGD((*quadconsupgd)), /**< method to call for upgrading quadratic constraint */
175  int priority, /**< priority of upgrading method */
176  SCIP_Bool active, /**< should the upgrading method be active by default? */
177  const char* conshdlrname /**< name of the constraint handler */
178  );
179 
180 /** Creates and captures a quadratic constraint.
181  *
182  * The constraint should be given in the form
183  * \f[
184  * \ell \leq \sum_{i=1}^n b_i x_i + \sum_{j=1}^m a_j y_j z_j \leq u,
185  * \f]
186  * where \f$x_i = y_j = z_k\f$ is possible.
187  *
188  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
189  */
190 extern
192  SCIP* scip, /**< SCIP data structure */
193  SCIP_CONS** cons, /**< pointer to hold the created constraint */
194  const char* name, /**< name of constraint */
195  int nlinvars, /**< number of linear terms (n) */
196  SCIP_VAR** linvars, /**< variables in linear part (x_i) or NULL if nlinvars == 0 */
197  SCIP_Real* lincoefs, /**< coefficients of variables in linear part (b_i) or NULL if nlinvars == 0 */
198  int nquadterms, /**< number of quadratic terms (m) */
199  SCIP_VAR** quadvars1, /**< array with first variables in quadratic terms (y_j) or NULL if nquadterms == 0 */
200  SCIP_VAR** quadvars2, /**< array with second variables in quadratic terms (z_j) or NULL if nquadterms == 0 */
201  SCIP_Real* quadcoeffs, /**< array with coefficients of quadratic terms (a_j) or NULL if nquadterms == 0 */
202  SCIP_Real lhs, /**< left hand side of quadratic equation (l) */
203  SCIP_Real rhs, /**< right hand side of quadratic equation (u) */
204  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
205  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
206  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
207  * Usually set to TRUE. */
208  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
209  * TRUE for model constraints, FALSE for additional, redundant constraints. */
210  SCIP_Bool check, /**< should the constraint be checked for feasibility?
211  * TRUE for model constraints, FALSE for additional, redundant constraints. */
212  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
213  * Usually set to TRUE. */
214  SCIP_Bool local, /**< is constraint only valid locally?
215  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
216  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
217  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
218  * adds coefficients to this constraint. */
219  SCIP_Bool dynamic, /**< is constraint subject to aging?
220  * Usually set to FALSE. Set to TRUE for own cuts which
221  * are separated as constraints. */
222  SCIP_Bool removable /**< should the relaxation be removed from the LP due to aging or cleanup?
223  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
224  );
225 
226 /** creates and captures a quadratic constraint
227  * in its most basic variant, i. e., with all constraint flags set to their default values, which can be set
228  * afterwards using SCIPsetConsFLAGNAME() in scip.h
229  *
230  * The constraint should be given in the form
231  * \f[
232  * \ell \leq \sum_{i=1}^n b_i x_i + \sum_{j=1}^m a_j y_jz_j \leq u,
233  * \f]
234  * where \f$x_i = y_j = z_k\f$ is possible.
235  *
236  * @see SCIPcreateConsQuadratic() for the default constraint flag configuration
237  *
238 
239  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
240  */
241 extern
243  SCIP* scip, /**< SCIP data structure */
244  SCIP_CONS** cons, /**< pointer to hold the created constraint */
245  const char* name, /**< name of constraint */
246  int nlinvars, /**< number of linear terms (n) */
247  SCIP_VAR** linvars, /**< array with variables in linear part (x_i) */
248  SCIP_Real* lincoefs, /**< array with coefficients of variables in linear part (b_i) */
249  int nquadterms, /**< number of quadratic terms (m) */
250  SCIP_VAR** quadvars1, /**< array with first variables in quadratic terms (y_j) */
251  SCIP_VAR** quadvars2, /**< array with second variables in quadratic terms (z_j) */
252  SCIP_Real* quadcoefs, /**< array with coefficients of quadratic terms (a_j) */
253  SCIP_Real lhs, /**< left hand side of quadratic equation (ell) */
254  SCIP_Real rhs /**< right hand side of quadratic equation (u) */
255  );
256 
257 /** creates and captures a quadratic constraint.
258  *
259  * The constraint should be given in the form
260  * \f[
261  * \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.
262  * \f]
263  *
264  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
265  */
266 extern
268  SCIP* scip, /**< SCIP data structure */
269  SCIP_CONS** cons, /**< pointer to hold the created constraint */
270  const char* name, /**< name of constraint */
271  int nlinvars, /**< number of linear terms (n) */
272  SCIP_VAR** linvars, /**< array with variables in linear part (x_i) */
273  SCIP_Real* lincoefs, /**< array with coefficients of variables in linear part (b_i) */
274  int nquadvarterms, /**< number of quadratic terms (m) */
275  SCIP_QUADVARTERM* quadvarterms, /**< quadratic variable terms */
276  int nbilinterms, /**< number of bilinear terms (p) */
277  SCIP_BILINTERM* bilinterms, /**< bilinear terms */
278  SCIP_Real lhs, /**< constraint left hand side (ell) */
279  SCIP_Real rhs, /**< constraint right hand side (u) */
280  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? */
281  SCIP_Bool separate, /**< should the constraint be separated during LP processing? */
282  SCIP_Bool enforce, /**< should the constraint be enforced during node processing? */
283  SCIP_Bool check, /**< should the constraint be checked for feasibility? */
284  SCIP_Bool propagate, /**< should the constraint be propagated during node processing? */
285  SCIP_Bool local, /**< is constraint only valid locally? */
286  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)? */
287  SCIP_Bool dynamic, /**< is constraint dynamic? */
288  SCIP_Bool removable /**< should the constraint be removed from the LP due to aging or cleanup? */
289  );
290 
291 /** creates and captures a quadratic constraint
292  * in its most basic variant, i. e., with all constraint flags set to their default values, which can be set
293  * afterwards using SCIPsetConsFLAGNAME() in scip.h
294  *
295  * The constraint should be given in the form
296  * \f[
297  * \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.
298  * \f]
299  *
300  * @see SCIPcreateConsQuadratic2() for the default constraint flag configuration
301  *
302  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
303  */
304 extern
306  SCIP* scip, /**< SCIP data structure */
307  SCIP_CONS** cons, /**< pointer to hold the created constraint */
308  const char* name, /**< name of constraint */
309  int nlinvars, /**< number of linear terms (n) */
310  SCIP_VAR** linvars, /**< array with variables in linear part (x_i) */
311  SCIP_Real* lincoefs, /**< array with coefficients of variables in linear part (b_i) */
312  int nquadvarterms, /**< number of quadratic terms (m) */
313  SCIP_QUADVARTERM* quadvarterms, /**< quadratic variable terms */
314  int nbilinterms, /**< number of bilinear terms (p) */
315  SCIP_BILINTERM* bilinterms, /**< bilinear terms */
316  SCIP_Real lhs, /**< constraint left hand side (ell) */
317  SCIP_Real rhs /**< constraint right hand side (u) */
318  );
319 
320 /** Adds a constant to the constraint function, that is, subtracts a constant from both sides */
321 extern
323  SCIP* scip, /**< SCIP data structure */
324  SCIP_CONS* cons, /**< constraint */
325  SCIP_Real constant /**< constant to subtract from both sides */
326  );
327 
328 /** Adds a linear variable with coefficient to a quadratic constraint.
329  */
330 extern
332  SCIP* scip, /**< SCIP data structure */
333  SCIP_CONS* cons, /**< constraint */
334  SCIP_VAR* var, /**< variable */
335  SCIP_Real coef /**< coefficient of variable */
336  );
337 
338 /** Adds a quadratic variable with linear and square coefficient to a quadratic constraint.
339  */
340 extern
342  SCIP* scip, /**< SCIP data structure */
343  SCIP_CONS* cons, /**< constraint */
344  SCIP_VAR* var, /**< variable */
345  SCIP_Real lincoef, /**< linear coefficient of variable */
346  SCIP_Real sqrcoef /**< square coefficient of variable */
347  );
348 
349 /** Adds a linear coefficient for a quadratic variable.
350  *
351  * Variable will be added with square coefficient 0.0 if not existing yet.
352  */
353 extern
355  SCIP* scip, /**< SCIP data structure */
356  SCIP_CONS* cons, /**< constraint */
357  SCIP_VAR* var, /**< variable */
358  SCIP_Real coef /**< value to add to linear coefficient of variable */
359  );
360 
361 /** Adds a square coefficient for a quadratic variable.
362  *
363  * Variable will be added with linear coefficient 0.0 if not existing yet.
364  */
365 extern
367  SCIP* scip, /**< SCIP data structure */
368  SCIP_CONS* cons, /**< constraint */
369  SCIP_VAR* var, /**< variable */
370  SCIP_Real coef /**< value to add to square coefficient of variable */
371  );
372 
373 /** Adds a bilinear term to a quadratic constraint.
374  *
375  * Variables will be added with linear and square coefficient 0.0 if not existing yet.
376  * If variables are equal, only the square coefficient of the variable is updated.
377  */
378 extern
380  SCIP* scip, /**< SCIP data structure */
381  SCIP_CONS* cons, /**< constraint */
382  SCIP_VAR* var1, /**< first variable */
383  SCIP_VAR* var2, /**< second variable */
384  SCIP_Real coef /**< coefficient of bilinear term */
385  );
386 
387 /** Gets the quadratic constraint as a nonlinear row representation.
388  */
389 extern
391  SCIP* scip, /**< SCIP data structure */
392  SCIP_CONS* cons, /**< constraint */
393  SCIP_NLROW** nlrow /**< pointer to store nonlinear row */
394  );
395 
396 /** Gets the number of variables in the linear part of a quadratic constraint.
397  */
398 extern
400  SCIP* scip, /**< SCIP data structure */
401  SCIP_CONS* cons /**< constraint */
402  );
403 
404 /** Gets the variables in the linear part of a quadratic constraint.
405  * Length is given by SCIPgetNLinearVarsQuadratic.
406  */
407 extern
409  SCIP* scip, /**< SCIP data structure */
410  SCIP_CONS* cons /**< constraint */
411  );
412 
413 /** Gets the coefficients in the linear part of a quadratic constraint.
414  * Length is given by SCIPgetNLinearVarsQuadratic.
415  */
416 extern
418  SCIP* scip, /**< SCIP data structure */
419  SCIP_CONS* cons /**< constraint */
420  );
421 
422 /** Gets the number of quadratic variable terms of a quadratic constraint.
423  */
424 extern
426  SCIP* scip, /**< SCIP data structure */
427  SCIP_CONS* cons /**< constraint */
428  );
429 
430 /** Gets the quadratic variable terms of a quadratic constraint.
431  * Length is given by SCIPgetNQuadVarTermsQuadratic.
432  */
433 extern
435  SCIP* scip, /**< SCIP data structure */
436  SCIP_CONS* cons /**< constraint */
437  );
438 
439 /** Ensures that quadratic variable terms are sorted. */
440 extern
442  SCIP* scip, /**< SCIP data structure */
443  SCIP_CONS* cons /**< constraint */
444  );
445 
446 /** Finds the position of a quadratic variable term for a given variable.
447  *
448  * @note If the quadratic variable terms have not been sorted before, then a search may reorder the current order of the terms.
449  */
450 extern
452  SCIP* scip, /**< SCIP data structure */
453  SCIP_CONS* cons, /**< constraint */
454  SCIP_VAR* var, /**< variable to search for */
455  int* pos /**< buffer to store position of quadvarterm for var, or -1 if not found */
456  );
457 
458 /** Gets the number of bilinear terms of a quadratic constraint.
459  */
460 extern
462  SCIP* scip, /**< SCIP data structure */
463  SCIP_CONS* cons /**< constraint */
464  );
465 
466 /** Gets the bilinear terms of a quadratic constraint.
467  * Length is given by SCIPgetNBilinTermQuadratic.
468  */
469 extern
471  SCIP* scip, /**< SCIP data structure */
472  SCIP_CONS* cons /**< constraint */
473  );
474 
475 /** Gets the left hand side of a quadratic constraint.
476  */
477 extern
479  SCIP* scip, /**< SCIP data structure */
480  SCIP_CONS* cons /**< constraint */
481  );
482 
483 /** Gets the right hand side of a quadratic constraint.
484  */
485 extern
487  SCIP* scip, /**< SCIP data structure */
488  SCIP_CONS* cons /**< constraint */
489  );
490 
491 /** get index of a variable in linvars that may be decreased without making any other constraint infeasible, or -1 if none */
492 extern
494  SCIP* scip, /**< SCIP data structure */
495  SCIP_CONS* cons /**< constraint */
496  );
497 
498 /** get index of a variable in linvars that may be increased without making any other constraint infeasible, or -1 if none */
499 extern
501  SCIP* scip, /**< SCIP data structure */
502  SCIP_CONS* cons /**< constraint */
503  );
504 
505 /** Check the quadratic function of a quadratic constraint for its semi-definiteness, if not done yet.
506  */
507 extern
509  SCIP* scip, /**< SCIP data structure */
510  SCIP_CONS* cons /**< constraint */
511  );
512 
513 /** Indicates whether the quadratic function of a quadratic constraint is (known to be) convex.
514  */
515 extern
517  SCIP* scip, /**< SCIP data structure */
518  SCIP_CONS* cons /**< constraint */
519  );
520 
521 /** Indicates whether the quadratic function of a quadratic constraint is (known to be) concave.
522  */
523 extern
525  SCIP* scip, /**< SCIP data structure */
526  SCIP_CONS* cons /**< constraint */
527  );
528 
529 /** Gets the violation of a constraint by a solution. */
530 extern
532  SCIP* scip, /**< SCIP data structure */
533  SCIP_CONS* cons, /**< constraint */
534  SCIP_SOL* sol, /**< solution which violation to calculate, or NULL for LP solution */
535  SCIP_Real* violation /**< pointer to store violation of constraint */
536  );
537 
538 /** Indicates whether the quadratic constraint is local w.r.t. the current local bounds.
539  *
540  * That is, checks whether each variable with a square term is fixed and for each bilinear term at least one variable is fixed.
541  */
542 extern
544  SCIP* scip, /**< SCIP data structure */
545  SCIP_CONS* cons /**< constraint */
546  );
547 
548 /** Adds the constraint to an NLPI problem. */
549 extern
551  SCIP* scip, /**< SCIP data structure */
552  SCIP_CONS* cons, /**< constraint */
553  SCIP_NLPI* nlpi, /**< interface to NLP solver */
554  SCIP_NLPIPROBLEM* nlpiprob, /**< NLPI problem where to add constraint */
555  SCIP_HASHMAP* scipvar2nlpivar, /**< mapping from SCIP variables to variable indices in NLPI */
556  SCIP_Bool names /**< whether to pass constraint names to NLPI */
557  );
558 
559 /** sets the left hand side of a quadratic constraint
560  *
561  * @note This method may only be called during problem creation stage for an original constraint.
562  */
563 extern
565  SCIP* scip, /**< SCIP data structure */
566  SCIP_CONS* cons, /**< constraint data */
567  SCIP_Real lhs /**< new left hand side */
568  );
569 
570 /** sets the right hand side of a quadratic constraint
571  *
572  * @note This method may only be called during problem creation stage for an original constraint.
573  */
574 extern
576  SCIP* scip, /**< SCIP data structure */
577  SCIP_CONS* cons, /**< constraint data */
578  SCIP_Real rhs /**< new right hand side */
579  );
580 
581 extern
582 /** gets the feasibility of the quadratic constraint in the given solution */
584  SCIP* scip, /**< SCIP data structure */
585  SCIP_CONS* cons, /**< constraint data */
586  SCIP_SOL* sol, /**< solution, or NULL to use current node's solution */
587  SCIP_Real* feasibility /**< pointer to store the feasibility */
588  );
589 
590 /** gets the activity of the quadratic constraint in the given solution */
591 extern
593  SCIP* scip, /**< SCIP data structure */
594  SCIP_CONS* cons, /**< constraint data */
595  SCIP_SOL* sol, /**< solution, or NULL to use current node's solution */
596  SCIP_Real* activity /**< pointer to store the activity */
597  );
598 
599 /** changes the linear coefficient value for a given quadratic variable in a quadratic constraint data; if not
600  * available, it adds it
601  *
602  * @note this is only allowed for original constraints and variables in problem creation stage
603  */
604 extern
606  SCIP* scip, /**< SCIP data structure */
607  SCIP_CONS* cons, /**< constraint data */
608  SCIP_VAR* var, /**< quadratic variable */
609  SCIP_Real coef /**< new coefficient */
610  );
611 
612 /** changes the square coefficient value for a given quadratic variable in a quadratic constraint data; if not
613  * available, it adds it
614  *
615  * @note this is only allowed for original constraints and variables in problem creation stage
616  */
617 extern
619  SCIP* scip, /**< SCIP data structure */
620  SCIP_CONS* cons, /**< constraint data */
621  SCIP_VAR* var, /**< quadratic variable */
622  SCIP_Real coef /**< new coefficient */
623  );
624 
625 /** changes the bilinear coefficient value for a given quadratic variable in a quadratic constraint data; if not
626  * available, it adds it
627  *
628  * @note this is only allowed for original constraints and variables in problem creation stage
629  */
630 extern
632  SCIP* scip, /**< SCIP data structure */
633  SCIP_CONS* cons, /**< constraint */
634  SCIP_VAR* var1, /**< first quadratic variable */
635  SCIP_VAR* var2, /**< second quadratic variable */
636  SCIP_Real coef /**< coefficient of bilinear term */
637  );
638 
639 /** returns the total number of bilinear terms that are contained in all quadratic constraints */
641  SCIP* scip /**< SCIP data structure */
642  );
643 
644 /** returns all bilinear terms that are contained in all quadratic constraints */
645 extern
647  SCIP* scip, /**< SCIP data structure */
648  SCIP_VAR** RESTRICT x, /**< array to store first variable of each bilinear term */
649  SCIP_VAR** RESTRICT y, /**< array to second variable of each bilinear term */
650  int* RESTRICT nbilinterms, /**< buffer to store the total number of bilinear terms */
651  int* RESTRICT nunderests, /**< array to store the total number of constraints that require to underestimate a bilinear term */
652  int* RESTRICT noverests, /**< array to store the total number of constraints that require to overestimate a bilinear term */
653  SCIP_Real* maxnonconvexity /**< estimate of nonconvex eigenvalues of all quadratic constraints containing a bilinear term */
654  );
655 
656 /** adds a globally valid inequality of the form xcoef x <= ycoef y + constant for a bilinear term (x,y)
657  *
658  * @note the indices of bilinear terms match with the entries of bilinear terms returned by SCIPgetAllBilinearTermsQuadratic
659  */
660 extern
662  SCIP* scip, /**< SCIP data structure */
663  SCIP_VAR* x, /**< first variable */
664  SCIP_VAR* y, /**< second variable */
665  int idx, /**< index of the bilinear term */
666  SCIP_Real xcoef, /**< x coefficient */
667  SCIP_Real ycoef, /**< y coefficient */
668  SCIP_Real constant, /**< constant part */
669  SCIP_Bool* success /**< buffer to store whether inequality has been accepted */
670  );
671 
672 /* @} */
673 
674 
675 #ifdef SCIP_PRIVATE_ROWPREP
676 
677 /** creates a SCIP_ROWPREP datastructure
678  *
679  * Initial row represents 0 <= 0.
680  */
681 extern
683  SCIP* scip, /**< SCIP data structure */
684  SCIP_ROWPREP** rowprep, /**< buffer to store pointer to rowprep */
685  SCIP_SIDETYPE sidetype, /**< whether cut will be or lower-equal or larger-equal type */
686  SCIP_Bool local /**< whether cut will be valid only locally */
687 );
688 
689 /** frees a SCIP_ROWPREP datastructure */
690 extern
691 void SCIPfreeRowprep(
692  SCIP* scip, /**< SCIP data structure */
693  SCIP_ROWPREP** rowprep /**< pointer that stores pointer to rowprep */
694 );
695 
696 /** creates a copy of a SCIP_ROWPREP datastructure */
697 extern
699  SCIP* scip, /**< SCIP data structure */
700  SCIP_ROWPREP** target, /**< buffer to store pointer of rowprep copy */
701  SCIP_ROWPREP* source /**< rowprep to copy */
702 );
703 
704 /** ensures that rowprep has space for at least given number of additional terms
705  *
706  * Useful when knowing in advance how many terms will be added.
707  */
708 extern
710  SCIP* scip, /**< SCIP data structure */
711  SCIP_ROWPREP* rowprep, /**< rowprep */
712  int size /**< number of additional terms for which to alloc space in rowprep */
713 );
714 
715 /** prints a rowprep */
716 extern
717 void SCIPprintRowprep(
718  SCIP* scip, /**< SCIP data structure */
719  SCIP_ROWPREP* rowprep, /**< rowprep to be printed */
720  FILE* file /**< file to print to, or NULL for stdout */
721 );
722 
723 /** adds a term coef*var to a rowprep */
724 extern
726  SCIP* scip, /**< SCIP data structure */
727  SCIP_ROWPREP* rowprep, /**< rowprep */
728  SCIP_VAR* var, /**< variable to add */
729  SCIP_Real coef /**< coefficient to add */
730 );
731 
732 /** adds several terms coef*var to a rowprep */
733 extern
735  SCIP* scip, /**< SCIP data structure */
736  SCIP_ROWPREP* rowprep, /**< rowprep */
737  int nvars, /**< number of terms to add */
738  SCIP_VAR** vars, /**< variables to add */
739  SCIP_Real* coefs /**< coefficients to add */
740 );
741 
742 /** adds constant value to side of rowprep */
743 extern
744 void SCIPaddRowprepSide(
745  SCIP_ROWPREP* rowprep, /**< rowprep */
746  SCIP_Real side /**< constant value to be added to side */
747 );
748 
749 /** adds constant term to rowprep
750  *
751  * Substracts constant from side.
752  */
753 extern
755  SCIP_ROWPREP* rowprep, /**< rowprep */
756  SCIP_Real constant /**< constant value to be added */
757 );
758 
759 #ifdef NDEBUG
760 #define SCIPaddRowprepSide(rowprep, sideadd) ((rowprep)->side += (sideadd))
761 #define SCIPaddRowprepConstant(rowprep, constant) SCIPaddRowprepSide(rowprep, -(constant))
762 #endif
763 
764 /** computes violation of cut in a given solution */
765 extern
767  SCIP* scip, /**< SCIP data structure */
768  SCIP_ROWPREP* rowprep, /**< rowprep to be turned into a row */
769  SCIP_SOL* sol /**< solution or NULL for LP solution */
770 );
771 
772 /** Merge terms that use same variable and eliminate zero coefficients.
773  *
774  * Terms are sorted by variable (@see SCIPvarComp) after return.
775  */
776 extern
778  SCIP* scip, /**< SCIP data structure */
779  SCIP_ROWPREP* rowprep /**< rowprep to be cleaned up */
780 );
781 
782 /* Cleans up and attempts to improve rowprep
783  *
784  * Drops small or large coefficients if coefrange is too large, if this can be done by relaxing the cut.
785  * Scales coefficients up to reach minimal violation, if possible.
786  * Scaling is omitted if violation is very small (ROWPREP_SCALEUP_VIOLNONZERO) or
787  * maximal coefficient would become huge (ROWPREP_SCALEUP_MAXMAXCOEF).
788  * Scales coefficients and side down if they are large and if the minimal violation is still reached.
789  * Rounds coefficients close to integral values to integrals, if this can be done by relaxing the cut.
790  * Rounds side within epsilon of 0 to 0.0 or +/-1.1*epsilon, whichever relaxes the cut least.
791  *
792  * After return, the terms in the rowprep will be sorted by absolute value of coefficient, in decreasing order.
793  */
794 extern
796  SCIP* scip, /**< SCIP data structure */
797  SCIP_ROWPREP* rowprep, /**< rowprep to be cleaned */
798  SCIP_SOL* sol, /**< solution that we try to cut off, or NULL for LP solution */
799  SCIP_Real maxcoefrange, /**< maximal allowed coefficients range */
800  SCIP_Real minviol, /**< minimal absolute violation the row should achieve (w.r.t. sol) */
801  SCIP_Real* coefrange, /**< buffer to store coefrange of cleaned up cut, or NULL if not of interest */
802  SCIP_Real* viol /**< buffer to store absolute violation of cleaned up cut in sol, or NULL if not of interest */
803 );
804 
805 /** scales a rowprep
806  *
807  * @return Exponent of actually applied scaling factor, if written as 2^x.
808  */
809 extern
810 int SCIPscaleRowprep(
811  SCIP_ROWPREP* rowprep, /**< rowprep to be scaled */
812  SCIP_Real factor /**< suggested scale factor */
813 );
814 
815 /** generates a SCIP_ROW from a rowprep */
816 extern
818  SCIP* scip, /**< SCIP data structure */
819  SCIP_ROW** row, /**< buffer to store pointer to new row */
820  SCIP_ROWPREP* rowprep, /**< rowprep to be turned into a row */
821  SCIP_CONSHDLR* conshdlr /**< constraint handler */
822 );
823 
824 /** generates a SCIP_ROW from a rowprep */
825 extern
827  SCIP* scip, /**< SCIP data structure */
828  SCIP_ROW** row, /**< buffer to store pointer to new row */
829  SCIP_ROWPREP* rowprep, /**< rowprep to be turned into a row */
830  SCIP_SEPA* sepa /**< separator */
831 );
832 
833 #endif
834 
835 /* @} */
836 
837 #ifdef __cplusplus
838 }
839 #endif
840 
841 #endif
SCIP_VAR ** SCIPgetLinearVarsQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPchgSquareCoefQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef)
SCIP_RETCODE SCIPincludeConshdlrQuadratic(SCIP *scip)
SCIP_RETCODE SCIPchgBilinCoefQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real coef)
SCIP_RETCODE SCIPaddQuadVarQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real lincoef, SCIP_Real sqrcoef)
SCIP_VAR * var2
void SCIPaddConstantQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_Real constant)
int SCIPgetNAllBilinearTermsQuadratic(SCIP *scip)
SCIP_RETCODE SCIPaddSquareCoefQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef)
SCIP_RETCODE SCIPchgRhsQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
SCIP_RETCODE SCIPincludeQuadconsUpgrade(SCIP *scip, SCIP_DECL_QUADCONSUPGD((*quadconsupgd)), int priority, SCIP_Bool active, const char *conshdlrname)
#define SCIP_MAXSTRLEN
Definition: def.h:259
SCIP_VAR * var1
SCIP_RETCODE SCIPaddRowprepTerms(SCIP *scip, SCIP_ROWPREP *rowprep, int nvars, SCIP_VAR **vars, SCIP_Real *coefs)
SCIP_RETCODE SCIPcleanupRowprep(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Real maxcoefrange, SCIP_Real minviol, SCIP_Real *coefrange, SCIP_Real *viol)
SCIP_RETCODE SCIPaddRowprepTerm(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_VAR *var, SCIP_Real coef)
SCIP_Bool local
SCIP_RETCODE SCIPchgLinearCoefQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef)
SCIP_SIDETYPE sidetype
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPcreateConsBasicQuadratic2(SCIP *scip, SCIP_CONS **cons, const char *name, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, int nquadvarterms, SCIP_QUADVARTERM *quadvarterms, int nbilinterms, SCIP_BILINTERM *bilinterms, SCIP_Real lhs, SCIP_Real rhs)
static GRAPHNODE ** active
SCIP_RETCODE SCIPcreateConsBasicQuadratic(SCIP *scip, SCIP_CONS **cons, const char *name, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, int nquadterms, SCIP_VAR **quadvars1, SCIP_VAR **quadvars2, SCIP_Real *quadcoefs, SCIP_Real lhs, SCIP_Real rhs)
SCIP_Real SCIPgetLhsQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPaddLinearVarQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef)
SCIP_RETCODE SCIPcreateConsQuadratic(SCIP *scip, SCIP_CONS **cons, const char *name, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, int nquadterms, SCIP_VAR **quadvars1, SCIP_VAR **quadvars2, SCIP_Real *quadcoeffs, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable)
int SCIPgetNQuadVarTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPaddBilinearIneqQuadratic(SCIP *scip, SCIP_VAR *x, SCIP_VAR *y, int idx, SCIP_Real xcoef, SCIP_Real ycoef, SCIP_Real constant, SCIP_Bool *success)
int SCIPgetNBilinTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPisConcaveQuadratic(SCIP *scip, SCIP_CONS *cons)
void SCIPfreeRowprep(SCIP *scip, SCIP_ROWPREP **rowprep)
SCIP_RETCODE SCIPchgLhsQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
struct SCIP_QuadVarEventData SCIP_QUADVAREVENTDATA
SCIP_RETCODE SCIPfindQuadVarTermQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, int *pos)
SCIP_RETCODE SCIPensureRowprepSize(SCIP *scip, SCIP_ROWPREP *rowprep, int size)
interval arithmetics for provable bounds
SCIP_RETCODE SCIPgetAllBilinearTermsQuadratic(SCIP *scip, SCIP_VAR **RESTRICT x, SCIP_VAR **RESTRICT y, int *RESTRICT nbilinterms, int *RESTRICT nunderests, int *RESTRICT noverests, SCIP_Real *maxnonconvexity)
SCIP_Real SCIPgetRowprepViolation(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol)
SCIP_VAR ** vars
SCIP_Real * SCIPgetCoefsLinearVarsQuadratic(SCIP *scip, SCIP_CONS *cons)
int SCIPgetLinvarMayDecreaseQuadratic(SCIP *scip, SCIP_CONS *cons)
void SCIPaddRowprepSide(SCIP_ROWPREP *rowprep, SCIP_Real side)
SCIP_RETCODE SCIPcreateRowprep(SCIP *scip, SCIP_ROWPREP **rowprep, SCIP_SIDETYPE sidetype, SCIP_Bool local)
SCIP_RETCODE SCIPgetNlRowQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_NLROW **nlrow)
SCIP_BILINTERM * SCIPgetBilinTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetRhsQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPgetViolationQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Real *violation)
SCIP_RETCODE SCIPaddBilinTermQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real coef)
SCIP_Real side
#define SCIP_Bool
Definition: def.h:61
void SCIPmergeRowprepTerms(SCIP *scip, SCIP_ROWPREP *rowprep)
SCIP_RETCODE SCIPgetRowprepRowCons(SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_CONSHDLR *conshdlr)
char name[SCIP_MAXSTRLEN]
SCIP_Bool SCIPisLinearLocalQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcheckCurvatureQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_QUADVAREVENTDATA * eventdata
int SCIPgetLinvarMayIncreaseQuadratic(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNLinearVarsQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcopyRowprep(SCIP *scip, SCIP_ROWPREP **target, SCIP_ROWPREP *source)
SCIP_RETCODE SCIPgetFeasibilityQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Real *feasibility)
SCIP_RETCODE SCIPsortQuadVarTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
int SCIPscaleRowprep(SCIP_ROWPREP *rowprep, SCIP_Real factor)
#define SCIP_Real
Definition: def.h:149
SCIP_RETCODE SCIPaddToNlpiProblemQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *scipvar2nlpivar, SCIP_Bool names)
SCIP_RETCODE SCIPcreateConsQuadratic2(SCIP *scip, SCIP_CONS **cons, const char *name, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, int nquadvarterms, SCIP_QUADVARTERM *quadvarterms, int nbilinterms, SCIP_BILINTERM *bilinterms, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable)
SCIP_RETCODE SCIPaddQuadVarLinearCoefQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef)
#define SCIP_DECL_QUADCONSUPGD(x)
SCIP_Real * coefs
SCIP_QUADVARTERM * SCIPgetQuadVarTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
void SCIPprintRowprep(SCIP *scip, SCIP_ROWPREP *rowprep, FILE *file)
SCIP_RETCODE SCIPgetRowprepRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_SEPA *sepa)
SCIP_Bool SCIPisConvexQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPgetActivityQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Real *activity)
SCIP callable library.
type definitions for specific NLP solver interfaces
void SCIPaddRowprepConstant(SCIP_ROWPREP *rowprep, SCIP_Real constant)
enum SCIP_SideType SCIP_SIDETYPE
Definition: type_lp.h:58