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