Scippy

SCIP

Solving Constraint Integer Programs

cons_quadratic.c
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-2024 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file cons_quadratic.c
26  * @ingroup DEFPLUGINS_CONS
27  * @brief some API functions of removed constraint handler for quadratic constraints \f$\textrm{lhs} \leq \sum_{i,j} a_{i,j} x_i x_j + \sum_i b_i x_i \leq \textrm{rhs}\f$
28  * @author Stefan Vigerske
29  */
30 
31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32 
33 #include "scip/cons_nonlinear.h"
34 #include "scip/cons_quadratic.h"
35 #include "scip/expr_var.h"
36 #include "scip/expr_pow.h"
37 #include "scip/expr_product.h"
38 
39 /** Creates and captures a quadratic nonlinear constraint.
40  *
41  * The constraint should be given in the form
42  * \f[
43  * \ell \leq \sum_{i=1}^n b_i x_i + \sum_{j=1}^m a_j y_j z_j \leq u,
44  * \f]
45  * where \f$x_i = y_j = z_k\f$ is possible.
46  *
47  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
48  *
49  * @deprecated Use SCIPcreateConsQuadraticNonlinear() instead.
50  */
52  SCIP* scip, /**< SCIP data structure */
53  SCIP_CONS** cons, /**< pointer to hold the created constraint */
54  const char* name, /**< name of constraint */
55  int nlinvars, /**< number of linear terms (n) */
56  SCIP_VAR** linvars, /**< variables in linear part (x_i) or NULL if nlinvars == 0 */
57  SCIP_Real* lincoefs, /**< coefficients of variables in linear part (b_i) or NULL if nlinvars == 0 */
58  int nquadterms, /**< number of quadratic terms (m) */
59  SCIP_VAR** quadvars1, /**< array with first variables in quadratic terms (y_j) or NULL if nquadterms == 0 */
60  SCIP_VAR** quadvars2, /**< array with second variables in quadratic terms (z_j) or NULL if nquadterms == 0 */
61  SCIP_Real* quadcoeffs, /**< array with coefficients of quadratic terms (a_j) or NULL if nquadterms == 0 */
62  SCIP_Real lhs, /**< left hand side of quadratic equation (l) */
63  SCIP_Real rhs, /**< right hand side of quadratic equation (u) */
64  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
65  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
66  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
67  * Usually set to TRUE. */
68  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
69  * TRUE for model constraints, FALSE for additional, redundant constraints. */
70  SCIP_Bool check, /**< should the constraint be checked for feasibility?
71  * TRUE for model constraints, FALSE for additional, redundant constraints. */
72  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
73  * Usually set to TRUE. */
74  SCIP_Bool local, /**< is constraint only valid locally?
75  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
76  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
77  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
78  * adds coefficients to this constraint. */
79  SCIP_Bool dynamic, /**< is constraint subject to aging?
80  * Usually set to FALSE. Set to TRUE for own cuts which
81  * are separated as constraints. */
82  SCIP_Bool removable /**< should the relaxation be removed from the LP due to aging or cleanup?
83  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
84  )
85 {
86  SCIP_CALL( SCIPcreateConsQuadraticNonlinear(scip, cons, name, nlinvars, linvars, lincoefs, nquadterms, quadvars1, quadvars2, quadcoeffs, lhs, rhs,
87  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable) );
88 
89  return SCIP_OKAY;
90 }
91 
92 /** creates and captures a quadratic nonlinear constraint
93  * in its most basic variant, i.e., with all constraint flags set to their default values, which can be set
94  * afterwards using SCIPsetConsFLAGNAME()
95  *
96  * The constraint should be given in the form
97  * \f[
98  * \ell \leq \sum_{i=1}^n b_i x_i + \sum_{j=1}^m a_j y_jz_j \leq u,
99  * \f]
100  * where \f$x_i = y_j = z_k\f$ is possible.
101  *
102  * @see SCIPcreateConsQuadratic() for the default constraint flag configuration
103  *
104  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
105  *
106  * @deprecated Use SCIPcreateConsBasicQuadraticNonlinear instead.
107  */
109  SCIP* scip, /**< SCIP data structure */
110  SCIP_CONS** cons, /**< pointer to hold the created constraint */
111  const char* name, /**< name of constraint */
112  int nlinvars, /**< number of linear terms (n) */
113  SCIP_VAR** linvars, /**< array with variables in linear part (x_i) */
114  SCIP_Real* lincoefs, /**< array with coefficients of variables in linear part (b_i) */
115  int nquadterms, /**< number of quadratic terms (m) */
116  SCIP_VAR** quadvars1, /**< array with first variables in quadratic terms (y_j) */
117  SCIP_VAR** quadvars2, /**< array with second variables in quadratic terms (z_j) */
118  SCIP_Real* quadcoefs, /**< array with coefficients of quadratic terms (a_j) */
119  SCIP_Real lhs, /**< left hand side of quadratic equation (ell) */
120  SCIP_Real rhs /**< right hand side of quadratic equation (u) */
121  )
122 {
123  SCIP_CALL( SCIPcreateConsBasicQuadraticNonlinear(scip, cons, name, nlinvars, linvars, lincoefs, nquadterms, quadvars1, quadvars2, quadcoefs, lhs, rhs) );
124 
125  return SCIP_OKAY;
126 }
127 
128 /** Adds a constant to the constraint function, that is, subtracts a constant from both sides
129  *
130  * @deprecated Use SCIPchgLhsNonlinear() and SCIPchgRhsNonlinear() instead.
131  */
133  SCIP* scip, /**< SCIP data structure */
134  SCIP_CONS* cons, /**< constraint */
135  SCIP_Real constant /**< constant to subtract from both sides */
136  )
137 {
138  SCIP_Real side;
139 
140  assert(cons != NULL);
141  assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "nonlinear") == 0);
142 
143  side = SCIPgetLhsNonlinear(cons);
144  if( !SCIPisInfinity(scip, -side) )
145  {
146  SCIP_CALL_ABORT( SCIPchgLhsNonlinear(scip, cons, side-constant) );
147  }
148 
149  side = SCIPgetRhsNonlinear(cons);
150  if( !SCIPisInfinity(scip, side) )
151  {
152  SCIP_CALL_ABORT( SCIPchgRhsNonlinear(scip, cons, side-constant) );
153  }
154 }
155 
156 /** Adds a linear variable with coefficient to a quadratic constraint.
157  *
158  * @deprecated Use SCIPaddLinearVarNonlinear() instead.
159  */
161  SCIP* scip, /**< SCIP data structure */
162  SCIP_CONS* cons, /**< constraint */
163  SCIP_VAR* var, /**< variable */
164  SCIP_Real coef /**< coefficient of variable */
165  )
166 {
167  assert(cons != NULL);
168  assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "nonlinear") == 0);
169 
170  SCIP_CALL( SCIPaddLinearVarNonlinear(scip, cons, var, coef) );
171 
172  return SCIP_OKAY;
173 }
174 
175 /** Adds a quadratic variable with linear and square coefficient to a quadratic constraint.
176  *
177  * @deprecated Use SCIPaddLinearVarNonlinear() and SCIPaddExprNonlinear() instead.
178  */
180  SCIP* scip, /**< SCIP data structure */
181  SCIP_CONS* cons, /**< constraint */
182  SCIP_VAR* var, /**< variable */
183  SCIP_Real lincoef, /**< linear coefficient of variable */
184  SCIP_Real sqrcoef /**< square coefficient of variable */
185  )
186 {
187  assert(cons != NULL);
188  assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "nonlinear") == 0);
189 
190  if( lincoef != 0.0 )
191  {
192  SCIP_CALL( SCIPaddLinearVarNonlinear(scip, cons, var, lincoef) );
193  }
194 
195  if( sqrcoef != 0.0 )
196  {
197  SCIP_EXPR* varexpr;
198  SCIP_EXPR* sqrexpr;
199 
200  SCIP_CALL( SCIPcreateExprVar(scip, &varexpr, var, NULL, NULL) );
201  SCIP_CALL( SCIPcreateExprPow(scip, &sqrexpr, varexpr, 2.0, NULL, NULL) );
202 
203  SCIP_CALL( SCIPaddExprNonlinear(scip, cons, sqrexpr, sqrcoef) );
204 
205  SCIP_CALL( SCIPreleaseExpr(scip, &sqrexpr) );
206  SCIP_CALL( SCIPreleaseExpr(scip, &varexpr) );
207  }
208 
209  return SCIP_OKAY;
210 }
211 
212 /** Adds a linear coefficient for a quadratic variable.
213  *
214  * Variable will be added with square coefficient 0.0 if not existing yet.
215  *
216  * @deprecated Use SCIPaddLinearVarNonlinear() instead.
217  */
219  SCIP* scip, /**< SCIP data structure */
220  SCIP_CONS* cons, /**< constraint */
221  SCIP_VAR* var, /**< variable */
222  SCIP_Real coef /**< value to add to linear coefficient of variable */
223  )
224 {
225  assert(cons != NULL);
226  assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "nonlinear") == 0);
227 
228  SCIP_CALL( SCIPaddLinearVarNonlinear(scip, cons, var, coef) );
229 
230  return SCIP_OKAY;
231 }
232 
233 /** Adds a square coefficient for a quadratic variable.
234  *
235  * Variable will be added with linear coefficient 0.0 if not existing yet.
236  *
237  * @deprecated Use SCIPaddExprNonlinear() instead.
238  */
240  SCIP* scip, /**< SCIP data structure */
241  SCIP_CONS* cons, /**< constraint */
242  SCIP_VAR* var, /**< variable */
243  SCIP_Real coef /**< value to add to square coefficient of variable */
244  )
245 {
246  SCIP_EXPR* varexpr;
247  SCIP_EXPR* sqrexpr;
248 
249  assert(cons != NULL);
250  assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "nonlinear") == 0);
251 
252  SCIP_CALL( SCIPcreateExprVar(scip, &varexpr, var, NULL, NULL) );
253  SCIP_CALL( SCIPcreateExprPow(scip, &sqrexpr, varexpr, 2.0, NULL, NULL) );
254 
255  SCIP_CALL( SCIPaddExprNonlinear(scip, cons, sqrexpr, coef) );
256 
257  SCIP_CALL( SCIPreleaseExpr(scip, &sqrexpr) );
258  SCIP_CALL( SCIPreleaseExpr(scip, &varexpr) );
259 
260  return SCIP_OKAY;
261 }
262 
263 /** Adds a bilinear term to a quadratic constraint.
264  *
265  * Variables will be added with linear and square coefficient 0.0 if not existing yet.
266  * If variables are equal, only the square coefficient of the variable is updated.
267  *
268  * @deprecated Use SCIPaddExprNonlinear() instead.
269  */
271  SCIP* scip, /**< SCIP data structure */
272  SCIP_CONS* cons, /**< constraint */
273  SCIP_VAR* var1, /**< first variable */
274  SCIP_VAR* var2, /**< second variable */
275  SCIP_Real coef /**< coefficient of bilinear term */
276  )
277 {
278  SCIP_EXPR* varexprs[2];
279  SCIP_EXPR* prodexpr;
280 
281  assert(cons != NULL);
282  assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "nonlinear") == 0);
283 
284  SCIP_CALL( SCIPcreateExprVar(scip, &varexprs[0], var1, NULL, NULL) );
285  SCIP_CALL( SCIPcreateExprVar(scip, &varexprs[1], var2, NULL, NULL) );
286  SCIP_CALL( SCIPcreateExprProduct(scip, &prodexpr, 2, varexprs, 1.0, NULL, NULL) );
287 
288  SCIP_CALL( SCIPaddExprNonlinear(scip, cons, prodexpr, coef) );
289 
290  SCIP_CALL( SCIPreleaseExpr(scip, &prodexpr) );
291  SCIP_CALL( SCIPreleaseExpr(scip, &varexprs[1]) );
292  SCIP_CALL( SCIPreleaseExpr(scip, &varexprs[0]) );
293 
294  return SCIP_OKAY;
295 }
296 
297 /** Gets the quadratic constraint as a nonlinear row representation.
298  *
299  * @deprecated Use SCIPgetNlRowNonlinear() instead.
300  */
302  SCIP* scip, /**< SCIP data structure */
303  SCIP_CONS* cons, /**< constraint */
304  SCIP_NLROW** nlrow /**< pointer to store nonlinear row */
305  )
306 {
307  assert(cons != NULL);
308  assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "nonlinear") == 0);
309 
310  SCIP_CALL( SCIPgetNlRowNonlinear(scip, cons, nlrow) );
311 
312  return SCIP_OKAY;
313 }
314 
315 /** sets the left hand side of a quadratic constraint
316  *
317  * @note This method may only be called during problem creation stage for an original constraint.
318  *
319  * @deprecated Use SCIPchgLhsNonlinear() instead.
320  */
322  SCIP* scip, /**< SCIP data structure */
323  SCIP_CONS* cons, /**< constraint data */
324  SCIP_Real lhs /**< new left hand side */
325  )
326 {
327  assert(cons != NULL);
328  assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "nonlinear") == 0);
329 
330  SCIP_CALL( SCIPchgLhsNonlinear(scip, cons, lhs) );
331 
332  return SCIP_OKAY;
333 }
334 
335 /** sets the right hand side of a quadratic constraint
336  *
337  * @note This method may only be called during problem creation stage for an original constraint.
338  *
339  * @deprecated Use SCIPchgRhsNonlinear() instead.
340  */
342  SCIP* scip, /**< SCIP data structure */
343  SCIP_CONS* cons, /**< constraint data */
344  SCIP_Real rhs /**< new right hand side */
345  )
346 {
347  assert(cons != NULL);
348  assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "nonlinear") == 0);
349 
350  SCIP_CALL( SCIPchgRhsNonlinear(scip, cons, rhs) );
351 
352  return SCIP_OKAY;
353 }
#define NULL
Definition: def.h:267
SCIP_RETCODE SCIPaddQuadVarQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real lincoef, SCIP_Real sqrcoef)
SCIP_RETCODE SCIPcreateExprPow(SCIP *scip, SCIP_EXPR **expr, SCIP_EXPR *child, SCIP_Real exponent, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_pow.c:3194
void SCIPaddConstantQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_Real constant)
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_Real SCIPgetRhsNonlinear(SCIP_CONS *cons)
SCIP_RETCODE SCIPchgRhsNonlinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
SCIP_RETCODE SCIPgetNlRowNonlinear(SCIP *scip, SCIP_CONS *cons, SCIP_NLROW **nlrow)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_RETCODE SCIPcreateExprVar(SCIP *scip, SCIP_EXPR **expr, SCIP_VAR *var, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_var.c:390
variable expression handler
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_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)
SCIP_RETCODE SCIPchgLhsQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
SCIP_RETCODE SCIPcreateConsBasicQuadraticNonlinear(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)
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4199
SCIP_RETCODE SCIPcreateConsQuadraticNonlinear(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_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)
some API functions of removed constraint handler for quadratic constraints
SCIP_RETCODE SCIPcreateExprProduct(SCIP *scip, SCIP_EXPR **expr, int nchildren, SCIP_EXPR **children, SCIP_Real coefficient, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
power and signed power expression handlers
SCIP_RETCODE SCIPaddExprNonlinear(SCIP *scip, SCIP_CONS *cons, SCIP_EXPR *expr, SCIP_Real coef)
SCIP_RETCODE SCIPgetNlRowQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_NLROW **nlrow)
#define SCIP_CALL(x)
Definition: def.h:380
SCIP_RETCODE SCIPaddLinearVarNonlinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef)
SCIP_RETCODE SCIPaddBilinTermQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real coef)
#define SCIP_Bool
Definition: def.h:91
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition: scip_expr.c:1417
constraint handler for nonlinear constraints specified by algebraic expressions
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8236
SCIP_RETCODE SCIPchgLhsNonlinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
product expression handler
#define SCIP_Real
Definition: def.h:173
SCIP_RETCODE SCIPaddQuadVarLinearCoefQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef)
#define SCIP_CALL_ABORT(x)
Definition: def.h:359
SCIP_Real SCIPgetLhsNonlinear(SCIP_CONS *cons)