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-2020 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file 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  * */
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 */
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  */
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  */
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  */
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  */
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 */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
444  SCIP* scip, /**< SCIP data structure */
445  SCIP_CONS* cons /**< constraint */
446  );
447 
448 /** Ensures that quadratic variable terms are sorted. */
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  */
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  */
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  */
480  SCIP* scip, /**< SCIP data structure */
481  SCIP_CONS* cons /**< constraint */
482  );
483 
484 /** Gets the left hand side of a quadratic constraint.
485  */
488  SCIP* scip, /**< SCIP data structure */
489  SCIP_CONS* cons /**< constraint */
490  );
491 
492 /** Gets the right hand side of a quadratic constraint.
493  */
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 */
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 */
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  */
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  */
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  */
534  SCIP* scip, /**< SCIP data structure */
535  SCIP_CONS* cons /**< constraint */
536  );
537 
538 /** Checks and indicates whether the quadratic constraint is convex. */
541  SCIP* scip, /**< SCIP data structure */
542  SCIP_CONS* cons, /**< constraint */
543  SCIP_HASHMAP* assumevarfixed, /**< hashmap containing variables that should be assumed to be fixed, or NULL */
544  SCIP_Bool* result /**< buffer where to store whether constraint is convex (under given variable fixing) */
545  );
546 
547 /** Gets the violation of a constraint by a solution. */
550  SCIP* scip, /**< SCIP data structure */
551  SCIP_CONS* cons, /**< constraint */
552  SCIP_SOL* sol, /**< solution which violation to calculate, or NULL for LP solution */
553  SCIP_Real* violation /**< pointer to store violation of constraint */
554  );
555 
556 /** Indicates whether the quadratic constraint is local w.r.t. the current local bounds.
557  *
558  * That is, checks whether each variable with a square term is fixed and for each bilinear term at least one variable is fixed.
559  */
562  SCIP* scip, /**< SCIP data structure */
563  SCIP_CONS* cons /**< constraint */
564  );
565 
566 /** Adds the constraint to an NLPI problem. */
569  SCIP* scip, /**< SCIP data structure */
570  SCIP_CONS* cons, /**< constraint */
571  SCIP_NLPI* nlpi, /**< interface to NLP solver */
572  SCIP_NLPIPROBLEM* nlpiprob, /**< NLPI problem where to add constraint */
573  SCIP_HASHMAP* scipvar2nlpivar, /**< mapping from SCIP variables to variable indices in NLPI */
574  SCIP_Bool names /**< whether to pass constraint names to NLPI */
575  );
576 
577 /** sets the left hand side of a quadratic constraint
578  *
579  * @note This method may only be called during problem creation stage for an original constraint.
580  */
583  SCIP* scip, /**< SCIP data structure */
584  SCIP_CONS* cons, /**< constraint data */
585  SCIP_Real lhs /**< new left hand side */
586  );
587 
588 /** sets the right hand side of a quadratic constraint
589  *
590  * @note This method may only be called during problem creation stage for an original constraint.
591  */
594  SCIP* scip, /**< SCIP data structure */
595  SCIP_CONS* cons, /**< constraint data */
596  SCIP_Real rhs /**< new right hand side */
597  );
598 
600 /** gets the feasibility of the quadratic constraint in the given solution */
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* feasibility /**< pointer to store the feasibility */
606  );
607 
608 /** gets the activity of the quadratic constraint in the given solution */
611  SCIP* scip, /**< SCIP data structure */
612  SCIP_CONS* cons, /**< constraint data */
613  SCIP_SOL* sol, /**< solution, or NULL to use current node's solution */
614  SCIP_Real* activity /**< pointer to store the activity */
615  );
616 
617 /** changes the linear coefficient value for a given quadratic variable in a quadratic constraint data; if not
618  * available, it adds it
619  *
620  * @note this is only allowed for original constraints and variables in problem creation stage
621  */
624  SCIP* scip, /**< SCIP data structure */
625  SCIP_CONS* cons, /**< constraint data */
626  SCIP_VAR* var, /**< quadratic variable */
627  SCIP_Real coef /**< new coefficient */
628  );
629 
630 /** changes the square coefficient value for a given quadratic variable in a quadratic constraint data; if not
631  * available, it adds it
632  *
633  * @note this is only allowed for original constraints and variables in problem creation stage
634  */
637  SCIP* scip, /**< SCIP data structure */
638  SCIP_CONS* cons, /**< constraint data */
639  SCIP_VAR* var, /**< quadratic variable */
640  SCIP_Real coef /**< new coefficient */
641  );
642 
643 /** changes the bilinear coefficient value for a given quadratic variable in a quadratic constraint data; if not
644  * available, it adds it
645  *
646  * @note this is only allowed for original constraints and variables in problem creation stage
647  */
650  SCIP* scip, /**< SCIP data structure */
651  SCIP_CONS* cons, /**< constraint */
652  SCIP_VAR* var1, /**< first quadratic variable */
653  SCIP_VAR* var2, /**< second quadratic variable */
654  SCIP_Real coef /**< coefficient of bilinear term */
655  );
656 
657 /** returns the total number of bilinear terms that are contained in all quadratic constraints */
660  SCIP* scip /**< SCIP data structure */
661  );
662 
663 /** returns all bilinear terms that are contained in all quadratic constraints */
666  SCIP* scip, /**< SCIP data structure */
667  SCIP_VAR** RESTRICT x, /**< array to store first variable of each bilinear term */
668  SCIP_VAR** RESTRICT y, /**< array to second variable of each bilinear term */
669  int* RESTRICT nbilinterms, /**< buffer to store the total number of bilinear terms */
670  int* RESTRICT nunderests, /**< array to store the total number of constraints that require to underestimate a bilinear term */
671  int* RESTRICT noverests, /**< array to store the total number of constraints that require to overestimate a bilinear term */
672  SCIP_Real* maxnonconvexity /**< estimate of nonconvex eigenvalues of all quadratic constraints containing a bilinear term */
673  );
674 
675 /** adds a globally valid inequality of the form xcoef x <= ycoef y + constant for a bilinear term (x,y)
676  *
677  * @note the indices of bilinear terms match with the entries of bilinear terms returned by SCIPgetAllBilinearTermsQuadratic
678  */
681  SCIP* scip, /**< SCIP data structure */
682  SCIP_VAR* x, /**< first variable */
683  SCIP_VAR* y, /**< second variable */
684  int idx, /**< index of the bilinear term */
685  SCIP_Real xcoef, /**< x coefficient */
686  SCIP_Real ycoef, /**< y coefficient */
687  SCIP_Real constant, /**< constant part */
688  SCIP_Bool* success /**< buffer to store whether inequality has been accepted */
689  );
690 
691 /** @} */
692 
693 
694 #ifdef SCIP_PRIVATE_ROWPREP
695 
696 /** creates a SCIP_ROWPREP datastructure
697  *
698  * Initial row represents 0 <= 0.
699  */
702  SCIP* scip, /**< SCIP data structure */
703  SCIP_ROWPREP** rowprep, /**< buffer to store pointer to rowprep */
704  SCIP_SIDETYPE sidetype, /**< whether cut will be or lower-equal or larger-equal type */
705  SCIP_Bool local /**< whether cut will be valid only locally */
706 );
707 
708 /** frees a SCIP_ROWPREP datastructure */
710 void SCIPfreeRowprep(
711  SCIP* scip, /**< SCIP data structure */
712  SCIP_ROWPREP** rowprep /**< pointer that stores pointer to rowprep */
713 );
714 
715 /** creates a copy of a SCIP_ROWPREP datastructure */
718  SCIP* scip, /**< SCIP data structure */
719  SCIP_ROWPREP** target, /**< buffer to store pointer of rowprep copy */
720  SCIP_ROWPREP* source /**< rowprep to copy */
721 );
722 
723 /** ensures that rowprep has space for at least given number of additional terms
724  *
725  * Useful when knowing in advance how many terms will be added.
726  */
729  SCIP* scip, /**< SCIP data structure */
730  SCIP_ROWPREP* rowprep, /**< rowprep */
731  int size /**< number of additional terms for which to alloc space in rowprep */
732 );
733 
734 /** prints a rowprep */
736 void SCIPprintRowprep(
737  SCIP* scip, /**< SCIP data structure */
738  SCIP_ROWPREP* rowprep, /**< rowprep to be printed */
739  FILE* file /**< file to print to, or NULL for stdout */
740 );
741 
742 /** adds a term coef*var to a rowprep */
745  SCIP* scip, /**< SCIP data structure */
746  SCIP_ROWPREP* rowprep, /**< rowprep */
747  SCIP_VAR* var, /**< variable to add */
748  SCIP_Real coef /**< coefficient to add */
749 );
750 
751 /** adds several terms coef*var to a rowprep */
754  SCIP* scip, /**< SCIP data structure */
755  SCIP_ROWPREP* rowprep, /**< rowprep */
756  int nvars, /**< number of terms to add */
757  SCIP_VAR** vars, /**< variables to add */
758  SCIP_Real* coefs /**< coefficients to add */
759 );
760 
761 /** adds constant value to side of rowprep */
763 void SCIPaddRowprepSide(
764  SCIP_ROWPREP* rowprep, /**< rowprep */
765  SCIP_Real side /**< constant value to be added to side */
766 );
767 
768 /** adds constant term to rowprep
769  *
770  * Substracts constant from side.
771  */
774  SCIP_ROWPREP* rowprep, /**< rowprep */
775  SCIP_Real constant /**< constant value to be added */
776 );
777 
778 #ifdef NDEBUG
779 #define SCIPaddRowprepSide(rowprep, sideadd) ((rowprep)->side += (sideadd))
780 #define SCIPaddRowprepConstant(rowprep, constant) SCIPaddRowprepSide(rowprep, -(constant))
781 #endif
782 
783 /** computes violation of cut in a given solution */
786  SCIP* scip, /**< SCIP data structure */
787  SCIP_ROWPREP* rowprep, /**< rowprep to be turned into a row */
788  SCIP_SOL* sol /**< solution or NULL for LP solution */
789 );
790 
791 /** Merge terms that use same variable and eliminate zero coefficients.
792  *
793  * Terms are sorted by variable (@see SCIPvarComp) after return.
794  */
797  SCIP* scip, /**< SCIP data structure */
798  SCIP_ROWPREP* rowprep /**< rowprep to be cleaned up */
799 );
800 
801 /* Cleans up and attempts to improve rowprep
802  *
803  * Drops small or large coefficients if coefrange is too large, if this can be done by relaxing the cut.
804  * Scales coefficients up to reach minimal violation, if possible.
805  * Scaling is omitted if violation is very small (ROWPREP_SCALEUP_VIOLNONZERO) or
806  * maximal coefficient would become huge (ROWPREP_SCALEUP_MAXMAXCOEF).
807  * Scales coefficients and side down if they are large and if the minimal violation is still reached.
808  * Rounds coefficients close to integral values to integrals, if this can be done by relaxing the cut.
809  * Rounds side within epsilon of 0 to 0.0 or +/-1.1*epsilon, whichever relaxes the cut least.
810  *
811  * After return, the terms in the rowprep will be sorted by absolute value of coefficient, in decreasing order.
812  */
815  SCIP* scip, /**< SCIP data structure */
816  SCIP_ROWPREP* rowprep, /**< rowprep to be cleaned */
817  SCIP_SOL* sol, /**< solution that we try to cut off, or NULL for LP solution */
818  SCIP_Real maxcoefrange, /**< maximal allowed coefficients range */
819  SCIP_Real minviol, /**< minimal absolute violation the row should achieve (w.r.t. sol) */
820  SCIP_Real* coefrange, /**< buffer to store coefrange of cleaned up cut, or NULL if not of interest */
821  SCIP_Real* viol /**< buffer to store absolute violation of cleaned up cut in sol, or NULL if not of interest */
822 );
823 
824 /** scales a rowprep
825  *
826  * @return Exponent of actually applied scaling factor, if written as 2^x.
827  */
829 int SCIPscaleRowprep(
830  SCIP_ROWPREP* rowprep, /**< rowprep to be scaled */
831  SCIP_Real factor /**< suggested scale factor */
832 );
833 
834 /** generates a SCIP_ROW from a rowprep */
837  SCIP* scip, /**< SCIP data structure */
838  SCIP_ROW** row, /**< buffer to store pointer to new row */
839  SCIP_ROWPREP* rowprep, /**< rowprep to be turned into a row */
840  SCIP_CONSHDLR* conshdlr /**< constraint handler */
841 );
842 
843 /** generates a SCIP_ROW from a rowprep */
846  SCIP* scip, /**< SCIP data structure */
847  SCIP_ROW** row, /**< buffer to store pointer to new row */
848  SCIP_ROWPREP* rowprep, /**< rowprep to be turned into a row */
849  SCIP_CONS* cons /**< constraint */
850 );
851 
852 /** generates a SCIP_ROW from a rowprep */
855  SCIP* scip, /**< SCIP data structure */
856  SCIP_ROW** row, /**< buffer to store pointer to new row */
857  SCIP_ROWPREP* rowprep, /**< rowprep to be turned into a row */
858  SCIP_SEPA* sepa /**< separator */
859 );
860 
861 #endif
862 
863 /** @} */
864 
865 #ifdef __cplusplus
866 }
867 #endif
868 
869 #endif
SCIP_EXPORT 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)
SCIP_VAR * var2
SCIP_EXPORT SCIP_RETCODE SCIPgetViolationQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Real *violation)
type definitions for miscellaneous datastructures
timing definitions for SCIP
SCIP_EXPORT 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)
type definitions for NLP management
SCIP_EXPORT SCIP_BILINTERM * SCIPgetBilinTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
#define SCIP_MAXSTRLEN
Definition: def.h:273
SCIP_VAR * var1
SCIP_RETCODE SCIPaddRowprepTerms(SCIP *scip, SCIP_ROWPREP *rowprep, int nvars, SCIP_VAR **vars, SCIP_Real *coefs)
SCIP_EXPORT SCIP_RETCODE SCIPaddSquareCoefQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef)
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_EXPORT SCIP_RETCODE SCIPcheckCurvatureQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool local
#define SCIP_EXPORT
Definition: def.h:100
SCIP_SIDETYPE sidetype
SCIP_EXPORT void SCIPaddConstantQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_Real constant)
SCIP_EXPORT SCIP_RETCODE SCIPchgBilinCoefQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real coef)
SCIP_EXPORT SCIP_Real SCIPgetLhsQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_EXPORT SCIP_QUADVARTERM * SCIPgetQuadVarTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPgetRowprepRowConshdlr(SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_CONSHDLR *conshdlr)
static GRAPHNODE ** active
type definitions for return codes for SCIP methods
SCIP_EXPORT SCIP_RETCODE SCIPaddToNlpiProblemQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *scipvar2nlpivar, SCIP_Bool names)
SCIP_EXPORT SCIP_RETCODE SCIPchgSquareCoefQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef)
SCIP_EXPORT SCIP_RETCODE SCIPfindQuadVarTermQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, int *pos)
SCIP_EXPORT SCIP_RETCODE SCIPchgLinearCoefQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef)
SCIP_EXPORT SCIP_RETCODE SCIPgetActivityQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Real *activity)
SCIP_VAR ** x
Definition: circlepacking.c:54
SCIP_EXPORT int SCIPgetNQuadVarTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPgetRowprepRowCons(SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_CONS *cons)
SCIP_EXPORT SCIP_RETCODE SCIPsortQuadVarTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_EXPORT SCIP_RETCODE SCIPaddQuadVarQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real lincoef, SCIP_Real sqrcoef)
SCIP_EXPORT SCIP_RETCODE SCIPchgLhsQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
type definitions for LP management
SCIP_EXPORT SCIP_RETCODE SCIPaddQuadVarLinearCoefQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef)
void SCIPfreeRowprep(SCIP *scip, SCIP_ROWPREP **rowprep)
SCIP_EXPORT SCIP_RETCODE SCIPincludeConshdlrQuadratic(SCIP *scip)
struct SCIP_QuadVarEventData SCIP_QUADVAREVENTDATA
SCIP_RETCODE SCIPensureRowprepSize(SCIP *scip, SCIP_ROWPREP *rowprep, int size)
SCIP_EXPORT SCIP_Bool SCIPisConvexQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetRowprepViolation(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol)
SCIP_VAR ** vars
type definitions for SCIP&#39;s main datastructure
void SCIPaddRowprepSide(SCIP_ROWPREP *rowprep, SCIP_Real side)
SCIP_RETCODE SCIPcreateRowprep(SCIP *scip, SCIP_ROWPREP **rowprep, SCIP_SIDETYPE sidetype, SCIP_Bool local)
SCIP_EXPORT SCIP_RETCODE SCIPaddBilinTermQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real coef)
type definitions for problem variables
SCIP_EXPORT 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_EXPORT SCIP_RETCODE SCIPchgRhsQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
SCIP_EXPORT SCIP_RETCODE SCIPincludeQuadconsUpgrade(SCIP *scip, SCIP_DECL_QUADCONSUPGD((*quadconsupgd)), int priority, SCIP_Bool active, const char *conshdlrname)
SCIP_EXPORT int SCIPgetLinvarMayIncreaseQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_EXPORT SCIP_VAR ** SCIPgetLinearVarsQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_Real side
#define SCIP_Bool
Definition: def.h:70
SCIP_EXPORT SCIP_RETCODE SCIPgetFeasibilityQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Real *feasibility)
void SCIPmergeRowprepTerms(SCIP *scip, SCIP_ROWPREP *rowprep)
char name[SCIP_MAXSTRLEN]
type definitions for storing primal CIP solutions
SCIP_EXPORT SCIP_Bool SCIPisConcaveQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_EXPORT SCIP_RETCODE SCIPaddLinearVarQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef)
SCIP_QUADVAREVENTDATA * eventdata
SCIP_EXPORT int SCIPgetNAllBilinearTermsQuadratic(SCIP *scip)
SCIP_RETCODE SCIPcopyRowprep(SCIP *scip, SCIP_ROWPREP **target, SCIP_ROWPREP *source)
SCIP_EXPORT SCIP_Bool SCIPisLinearLocalQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_EXPORT int SCIPgetNLinearVarsQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_EXPORT 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)
type definitions for separators
SCIP_EXPORT int SCIPgetNBilinTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_EXPORT SCIP_RETCODE SCIPisConvexConsQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_HASHMAP *assumevarfixed, SCIP_Bool *result)
int SCIPscaleRowprep(SCIP_ROWPREP *rowprep, SCIP_Real factor)
SCIP_EXPORT 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)
#define SCIP_Real
Definition: def.h:163
SCIP_VAR ** y
Definition: circlepacking.c:55
SCIP_EXPORT SCIP_Real SCIPgetRhsQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_EXPORT SCIP_Real * SCIPgetCoefsLinearVarsQuadratic(SCIP *scip, SCIP_CONS *cons)
#define SCIP_DECL_QUADCONSUPGD(x)
SCIP_Real * coefs
SCIP_EXPORT 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)
common defines and data types used in all packages of SCIP
void SCIPprintRowprep(SCIP *scip, SCIP_ROWPREP *rowprep, FILE *file)
SCIP_EXPORT int SCIPgetLinvarMayDecreaseQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPgetRowprepRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_SEPA *sepa)
type definitions for constraints and constraint handlers
type definitions for specific NLP solver interfaces
SCIP_EXPORT SCIP_RETCODE SCIPgetNlRowQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_NLROW **nlrow)
void SCIPaddRowprepConstant(SCIP_ROWPREP *rowprep, SCIP_Real constant)
enum SCIP_SideType SCIP_SIDETYPE
Definition: type_lp.h:58