Documentation

Filter Content By
Version
Text Search
${sidebar_list_label} - Back
Languages
${item.name}
next up previous
Next: Tolerances and Ill Conditioning Up: Variables and Constraints Previous: Variables


Constraints

A constraint in Gurobi captures a restriction on the values that a set of variables may take. The simplest example is a linear constraint, which states that a linear expression on a set of variables take a value that is either less-than-or-equal, greater-than-or-equal, or equal another linear expression. Recall that Gurobi works in finite-precision arithmetic, so constraints are only satisfied to tolerances. Tolerances can be tightened to reduce such violations, but there are limits to how small the violations can be - errors are inherent in floating-point arithmetic.

The available constraint types are linear, SOS, quadratic, and general.

Linear Constraints

A linear constraint allows you to restrict the value of a linear expression. For example, you may require that any feasible solution satisfy the constraint <span>$</span>3 x + 4 y \leq 5z<span>$</span>. Note that the matrix-oriented Gurobi API's (C, MATLAB, and R) require the right-hand side of a linear constraint to be a constant, while the object-oriented APIs (C++, Java, .NET, and Python) allow arbitrary linear expressions on both sides of the comparator.

The computed solution should satisfy the stated constraint to within FeasibilityTol (although it may not in cases of numerical ill-conditioning - we'll discuss this shortly).

Gurobi supports a limited set of comparators. Specifically, you can constrain an expression to be less-than-or-equal, greater-than-or-equal, or equal another. We do not support strict less-than, strict greater-than, or not-equal comparators. While these other comparators may seem appropriate for mathematical programming, we exclude them to avoid potential confusion related to numerical tolerances. Consider a simple example of a strict inequality constraint on a pair of continuous variables: <span>$</span>x > y<span>$</span>. How large would <span>$</span>x-y<span>$</span> need to be in order to satisfy the constraint? Rather than trying to embed a subtle and potentially confusing strategy for handling such constraints into the solver, we've chosen not to support them instead.

SOS Constraints

An Special-Ordered Set, or SOS constraint, is a highly specialized constraint that places restrictions on the values that variables in a given list can take. There are two types of SOS constraints. In an SOS constraint of type 1 (an SOS1 constraint), at most one variable in the specified list is allowed to take a non-zero value. In an SOS constraint of type 2 (an SOS2 constraint), at most two variables in the specified, ordered list are allowed to take a non-zero value, and those non-zero variables must be contiguous in the list. The variables in an SOS constraint can be continuous, integer, or binary.

Again, tolerances play an important role in SOS constraints. Specifically, variables that take values less than IntFeasTol (in absolute value) are considered to be zero for the purposes of determining whether an SOS constraint is satisfied.

An SOS constraint is described using a list of variables and a list of corresponding weights. While the weights have historically had intuitive meanings associated with them, we simply use them to order the list of variables. The weights should be unique. This is especially important for an SOS2 constraint, which relies on the notion of contiguous variables. Since the variables in the SOS are ordered by weight, contiguity becomes ambiguous when multiple variables have the same weight.

It is often more efficient to capture SOS structure using linear constraints rather than SOS constraints. The optimizer will often perform this conversion automatically. This is controlled with two parameters: PreSOS1BigM and PreSOS2BigM. The conversion is done by adding constraints of the form <span>$</span>x <= M b<span>$</span>, where <span>$</span>x<span>$</span> is the variable that participates in the SOS constraint, <span>$</span>b<span>$</span> is a binary variable, and <span>$</span>M<span>$</span> is an upper bound on the value of variable <span>$</span>x<span>$</span>. Large values of <span>$</span>M<span>$</span> can lead to numerical issues, so these parameters control the maximum value of <span>$</span>M<span>$</span> that can be introduced by this conversion. SOS constraints that would require a larger value aren't converted.

Quadratic Constraints

A quadratic constraint allows you to restrict the value of a quadratic expression. For example, you may require that any feasible solution satisfy the constraint <span>$</span>3 x^2 + 4 y^2 + 5 z \leq 10<span>$</span>. Note that the matrix-oriented Gurobi API's (C, MATLAB, and R) require the right-hand side of a quadratic constraint to be a constant, while the object-oriented APIs (C++, Java, .NET, and Python) allow arbitrary quadratic expressions on both sides of the comparator.

The computed solution should satisfy the stated constraint to within FeasibilityTol. Quadratic constraints are often much more challenging to satisfy than linear constraints, so tightening the parameter may increase runtimes dramatically.

The algorithms that Gurobi uses to solve quadratically constrained problems can only handle certain types of quadratic constraints. Constraints of the following forms are always accepted:

  • <span>$</span>x^TQx + q^Tx \le b<span>$</span>, where <span>$</span>Q<span>$</span> is Positive Semi-Definite (PSD)
  • <span>$</span>x^Tx \le y^{2}<span>$</span>, where <span>$</span>x<span>$</span> is a vector of variables, and <span>$</span>y<span>$</span> is a non-negative variable (a Second-Order Cone)
  • <span>$</span>x^Tx \le y z<span>$</span>, where <span>$</span>x<span>$</span> is a vector of variables, and <span>$</span>y<span>$</span> and <span>$</span>z<span>$</span> are non-negative variables (a rotated Second-Order Cone)
If you add a constraint that isn't in one of these forms (and Gurobi presolve is unable to transform the constraint into one of these forms), you'll get an error when you try to solve the model. Constraints where the quadratic terms only involve binary variables will always be transformed into one of these forms.

General Constraints

The previously-described constraints are typically handled directly by the underlying optimization algorithms (although not always). Gurobi also includes an additional set of constraints, which we collectively refer to as general constraints. General constraints are a convenience feature, designed to allow you to capture certain relationships between variables without having to immerse yourself in the often esoteric details of how to model these relationships in terms of the more fundamental constraints of MIP. Capturing a single one of these general constraints can often require a large set of linear and SOS constraints, plus a number of auxiliary decision variables. By supporting them directly in the Gurobi API, we simplify the modeling process by performing the transformation to a corresponding MIP formulation automatically and transparently during the solution process.

Gurobi supports a number of different types of general constraints, each having its own syntax and semantics:

  • MAX constraint: The constraint <span>$</span>r = \max\{x_1,\ldots,x_k,c\}<span>$</span> states that the resultant variable <span>$</span>r<span>$</span> should be equal to the maximum of the operand variables <span>$</span>x_1,\ldots,x_k<span>$</span> and the constant <span>$</span>c<span>$</span>. For example, a solution <span>$</span>(r=3, x_1=2, x_2=3, x_3=0)<span>$</span> would be feasible for the constraint <span>$</span>r = \max\{x_1,x_2,x_3,1.7\}<span>$</span> because <span>$</span>3<span>$</span> is indeed the maximum of <span>$</span>2<span>$</span>, <span>$</span>3<span>$</span>, <span>$</span>0<span>$</span>, and <span>$</span>1.7<span>$</span>.
  • MIN constraint: Similar to a MAX constraint, the constraint <span>$</span>r = \min\{x_1,\ldots,x_k,c\}<span>$</span> states that the resultant variable <span>$</span>r<span>$</span> should be equal to the minimum of the operand variables <span>$</span>x_1,\ldots,x_k<span>$</span> and the constant <span>$</span>c<span>$</span>.
  • ABS constraint: The constraint <span>$</span>r = \mbox{abs}\{x\}<span>$</span> states that the resultant variable <span>$</span>r<span>$</span> should be equal to the absolute value of the operand variable <span>$</span>x<span>$</span>. For example, a solution <span>$</span>(r=3, x=-3)<span>$</span> would be feasible for the constraint <span>$</span>r = \mbox{abs}\{x\}<span>$</span>.
  • AND constraint: The constraint <span>$</span>r = \mbox{and}\{x_1,\ldots,x_k\}<span>$</span> states that the binary resultant variable <span>$</span>r<span>$</span> should be equal <span>$</span>1<span>$</span> if and only if all of the binary operand variables <span>$</span>x_1,\ldots,x_k<span>$</span> are equal to <span>$</span>1<span>$</span>. For example, a solution <span>$</span>(r=1, x_1=1, x_2=1, x_3=1)<span>$</span> would be feasible for the constraint <span>$</span>r = \mbox{and}\{x_1,x_2,x_3\}<span>$</span>. Note that declaring an AND constraint implicitly declares all involved variables to be of binary type.
  • OR constraint: Similar to an AND constraint, the constraint <span>$</span>r = \mbox{or}\{x_1,\ldots,x_k\}<span>$</span> states that the binary resultant variable <span>$</span>r<span>$</span> should be <span>$</span>1<span>$</span> if and only if at least one of the binary operand variables <span>$</span>x_1,\ldots,x_k<span>$</span> is equal to <span>$</span>1<span>$</span>. Note that declaring an OR constraint implicitly declares all involved variables to be of binary type.
  • INDICATOR constraints: An indicator constraint <span>$</span>y = f \rightarrow a^Tx \leq b<span>$</span> states that if the binary indicator variable <span>$</span>y<span>$</span> has the value <span>$</span>f \in \{0,1\}<span>$</span> in a given solution, then the linear constraint <span>$</span>a^Tx \leq b<span>$</span> has to be satisfied. On the other hand, if <span>$</span>y \neq f<span>$</span> (i.e., <span>$</span>y = 1-f<span>$</span>) then the linear constraint may be violated. Note that the sense of the linear constraint can also be <span>$</span>=<span>$</span> or <span>$</span>\geq<span>$</span>; refer to this earlier section for a more detailed description of linear constraints. Note also that declaring an INDICATOR constraint implicitly declares the indicator variable to be of binary type.

As stated above, each general constraint has an equivalent MIP formulation that consists of linear and SOS constraints, and possibly auxiliary variables. Thus, you could always model such constraints yourself without using a Gurobi general constraint. For example, the MAX constraint <span>$</span>r = \max\{x_1,\ldots,x_k,c\}<span>$</span> can be modeled as follows:

\begin{displaymath} \begin{array}{rcll} r & = & x_j + s_j & \mbox{ for all } j =... ...& \in & \{0,1\} & \mbox{ for all } j = 1,\ldots,k+1 \end{array}\end{displaymath}

The first two constraints state that <span>$</span>r \geq \max\{x_1,\ldots,x_k,c\}<span>$</span>, i.e., that the resultant variable <span>$</span>r<span>$</span> has to be at least as large as each of the operand variables <span>$</span>x_j<span>$</span> and the constant <span>$</span>c<span>$</span>. This can be modeled using inequalities, but we turned them into equations by introducing explicit continuous slack variables <span>$</span>s_j \geq 0<span>$</span>, which we will reuse below.

Those slack variables and the remaining constraints model <span>$</span>r \leq \max\{x_1,\ldots,x_k,c\}<span>$</span>, which is more complicated. In addition to the explicit slacks, this requires the introduction of binary auxiliary variables <span>$</span>z_j \in \{0,1\}<span>$</span>. The SOS1 constraints state that at most one of the two variables <span>$</span>s_j<span>$</span> and <span>$</span>z_j<span>$</span> can be non-zero, which models the implication <span>$</span>z_j = 1 \rightarrow s_j = 0<span>$</span>. Due to the third constraint, one <span>$</span>z_j<span>$</span> will be equal to <span>$</span>1<span>$</span> and thus at least one <span>$</span>s_j<span>$</span> will be zero. Hence, <span>$</span>r = x_j<span>$</span> for at least one <span>$</span>j<span>$</span> due to the first constraint, or <span>$</span>r = c<span>$</span> due to the second constraint.

Tolerances play a role in general constraints, although as you might expect, the exact role depends on the constraint type. Generally, violations in the resultant will be smaller than the feasibility tolerance, and integrality violations in integer resultants will also satisfy the integrality tolerance.

If a model contains general constraints, then Gurobi adds the respective MIP formulations for those constraints during the solution process. In this respect, general constraints are just a means of concisely capturing these relationships between variables while removing the burden of creating an equivalent MIP formulation. However, general constraints have another potential advantage: Gurobi might be able to simplify parts of the MIP formulation if it can prove during presolve that the simplified version suffices for the correctness of the model. For this reason, Gurobi might be able to produce a smaller or tighter representation of the general constraint than you would get from the most general formulation. For example, it might be the case that <span>$</span>r \leq \max\{x_1,\ldots,x_k,c\}<span>$</span> is already implied by the other constraints in the model, so that a simple set of inequalities

\begin{eqnarray*} r & \geq & x_j \;\;\mbox{ for all } j = 1,\ldots,k \ r & \geq & c \end{eqnarray*}


to describe <span>$</span>r \geq \max\{x_1,\ldots,x_k,c\}<span>$</span> suffices to model the relevant part of the MAX constraint.

next up previous
Next: Tolerances and Ill Conditioning Up: Variables and Constraints Previous: Variables