Objectives

Every optimization model has an objective function, which is the function on the decision variables that you wish to minimize or maximize. The objective is meant to capture your goals in solving the problem. Given a set of feasible solutions, the objective tells the solver which is preferred.

Most optimization problems have multiple optimal solutions, plus many solutions whose objectives are within a small gap from the optimal value. The solution that is returned by Gurobi depends on the type of problem you are solving. The simple rule is that Gurobi returns a single optimal solution for continuous models (LP, QP, and QCP), and a sequence of improving solutions for discrete models (MIP, MIQP, and MIQCP).

The Gurobi algorithms work on solving a model until they find a solution that is optimal to within the specified tolerances. For the simplex algorithms (including barrier with crossover), the relevant tolerance is the OptimalityTol. For the barrier algorithm (without crossover), the relevant tolerances are the BarConvTol or BarQCPConvTol (depending on the problem type). You can relax these tolerances, but note that it is rare for this to significantly improve solution times. The simplex and barrier algorithms both return a single optimal solution.

For discrete models, while you can ask the MIP solver to find a solution with the best possible objective value, it is more common to stop when the solution objective is within a specified gap from the optimal value. This optimality gap is controlled by the MIPGap parameter, and the default value is 0.01%.

The MIP solver typically finds multiple sub-optimal solutions on the way to eventually finding an optimal solution. These intermediate solutions can be queried once the optimization is complete (using the Xn attribute). You can use the Solution Pool feature to take a more systematic approach to finding multiple solutions. This feature allows you to indicate how many solutions you would like, to specify the largest gap to the optimal value you are willing to accept, etc.

We should add that it is possible to specify a pure feasibility problem, where the sole goal is to find a solution that satisfies the constraints. You can think of a feasibility problem as an optimization problem with a constant objective function.

The available objective types are linear, piecewise-linear, quadratic (both convex and non-convex), and multi-objective. While the property of having multiple objectives may appear to be orthogonal to the types of the objectives, Gurobi only supports multi-objective models where all objectives are linear.

Linear Objectives

The simplest and most common objective function is linear - minimizing or maximizing a linear function on the decision variables (e.g., \(3 x + 4 y + 2\)). Linear objectives can be specified in a few ways. The first is by providing an objective term when the decision variable is added to the model (typically through the addVar method). The second is by setting the Obj attribute on the variable. The third and most convenient approach, available in the object-oriented interfaces, is through the setObjective method (in C++, Java, .NET, or Python). This method accepts a linear expression object as its argument.

A model with a linear objective, only linear constraints, and only continuous variables is a Linear Program (LP). It can be solved using the simplex or barrier algorithms.

Piecewise-Linear Objectives

A useful variant of a linear objective is a piecewise-linear objective, where the objective for a single variable is captured in a set of linear pieces. For example, suppose we want to define the objective value \(f(x)\) for variable \(x\) as follows:

The vertices of the function occur at the points \((1, 1)\), \((3, 2)\) and \((5, 4)\), so we define \(f(1) = 1\), \(f(3) = 2\) and \(f(5) = 4\). Other objective values are linearly interpolated between neighboring points. The first pair and last pair of points each define a ray, so values outside the specified \(x\) values are extrapolated from these points. Thus, in our example, \(f(-1)=0\) and \(f(6)=5\).

More formally, a piecewise-linear function is defined by a set of \(n\) points:

\[\mathtt{x} = [x_1, \ldots, x_n], \quad \mathtt{y} = [y_1, \ldots, y_n]\]

These define the following piecewise-linear function:

\[\begin{split}f(v) = \left\{ \begin{array}{ll} y_1 + \frac{y_2-y_1}{x_2-x_1} (v - x_1), & \mathrm{if}\; v \le x_1,\\[7pt] y_i + \frac{y_{i+1}-y_i}{x_{i+1}-x_i} (v - x_i), & \mathrm{if}\; v \ge x_i\; \mathrm{and}\; v \le x_{i+1}, \\[7pt] y_n + \frac{y_n - y_{n-1}}{x_n - x_{n-1}} (v - x_n), & \mathrm{if}\; v \ge x_n. \\[7pt] \end{array} \right.\end{split}\]

We also allow special cases, such as jumps and single points, which are quite useful to define the fixed charges or the penalties. A jump at \(x=x_i\) means that the left piece and the right piece don’t intersect at \(x=x_i\), i.e. we have \((x_{i-1}, y_{i-1}),(x_i, y_i), (x_{i+1}, y_{i+1}), (x_{i+2}, y_{i+2})\) with \(x_i = x_{i+1}\) and \(y_i \neq y_{i+1}\). So for the left piece, i.e. \(x_{i-1} \le x < x_{i}\), the line segment between points \((x_{i-1}, y_{i-1})\) and \((x_i, y_i)\) defines \(y\), for the right piece, i.e. \(x_{i} \le x < x_{i+2}\), the line segment between points \((x_{i+1}, y_{i+1})\) and \((x_{i+2}, y_{i+2})\) defines \(y\). Since we must allow some tolerance for numeric computation, it means that at \(x = x_i\), \(y\) can take the value of either \(y_i\) or \(y_{i+1}\). A single point at \(x=x_i\) means that both left and right pieces extend to \(x=x_i\), but both have different \(y\) values than \(y_i\). It can be described by the five points \((x_{i-2}, y_{i-2}), (x_{i-1}, y_{i-1}), (x_i, y_i), (x_{i+1}, y_{i+1}), (x_{i+2}, y_{i+2})\) with \(x_{i-1} = x_i = x_{i+1}\) and \(y_i \neq y_{i-1}\) and \(y_i \neq y_{i+1}\). Note that \(y_{i-1}\) and \(y_{i+1}\) can be equal or different. Because of the tolerance, it means that at \(x = x_i\), \(y\) can take the value of \(y_{i-1}\), \(y_i\) or \(y_{i+1}\). Here below is an example with a jump and a single point.

The above piecewise function for variable \(x\) are defined by 7 points \((-1, 0), (1, 1), (1, 2), (3, 2), (3, 0), (3,2)\) and \((5,4)\). It has a jump at \(x=1\) from \((1,1)\) to \((1,2)\) and a single point \((3,0)\). Note that both left and right points have the same \(x\) coordinate and for this example the two points are the same.

Note that a piecewise-linear objective can change the type of a model. Specifically, including a non-convex piecewise-linear objective function in a continuous model will transform that model into a MIP. This can significantly increase the cost of solving the model.

How do you determine whether your piecewise-linear objective is convex? A convex function has the property that you can’t obtain a better objective value by interpolating between two points on the function. In the figure below, you will note that all convex combinations of points on the piecewise-linear function are in the shaded (feasible) region.

Stated another way, successive pieces will have non-decreasing slopes in a convex piecewise-linear objective (assuming you are minimizing).

In contrast, in a non-convex piecewise-linear function you can get a better value by interpolating between points. In the figure below, the value of \(f(1)\) for the piecewise-linear function is worse (larger) than the value obtained by interpolation.

Piecewise-linear objectives are defined on variables using a special method (in C, C++, Java, .NET, or Python). Each variable can have its own piecewise-linear objective function, and each function requires a separate call to this method.

A variable can’t have both a linear and a piecewise-linear objective term. Setting a piecewise-linear objective for a variable will set the Obj attribute on that variable to 0. Similarly, setting the Obj attribute will delete the piecewise-linear objective on that variable.

We should point out that it is fairly easy to specify a piecewise-linear function on a variable using a few extra variables and simple linear objective terms. The advantages of using the piecewise-linear API methods are twofold. The first is convenience - specifying the function directly leads to simpler and more readable code. The second is that Gurobi includes a piecewise-linear simplex algorithm. If you provide a model that contains only linear constraints, only continuous variables, and only linear or convex piecewise-linear objective terms, then this specialized simplex algorithm will be used to solve the model. If your piecewise-linear function contains a large number of segments, the specialized algorithm will be much faster than the standard simplex solver.

Quadratic Objectives

Your optimization objective can also contain quadratic terms (e.g., \(3 x^2 + 4 y^2 + 2 x y + 2 x + 3\)). You specify quadratic objectives in the object-oriented interfaces by building quadratic expressions and then calling setObjective (C++, Java, .NET, or Python). In C, you input your quadratic terms using GRBaddqpterms.

There are four distinct algorithms that could be used to solve a model with a quadratic objective. The appropriate one depends on a few specific properties of the objective and the rest of the model.

• Continuous Convex QP If your quadratic objective is convex and your model only contains linear constraints and continuous variables, then your model is a quadratic program (QP) and can be solved using either the simplex or barrier algorithms. QP simplex will return an optimal basic solution. Gurobi does not have a QP crossover, so QP barrier will return an interior solution.

• Discrete QP with Convex Relaxation If your quadratic objective is convex but the model contains discrete elements (integer variables, SOS constraints, general constraints, etc.), then your model is a mixed integer quadratic program (MIQP) and is solved using the MIP solver. Since MIP relies heavily on simplex bases, the root relaxation must be solved using the primal or dual simplex algorithm.

• Non-convex QP and Discrete QP with Non-Convex Relaxation If your quadratic objective is not convex, then the model will be solved using the MIP solver, even if your model has no explicit discrete elements. Non-convex problems often lead to much larger solve times, and it might be that the non-convexity in your model is unexpected, for example due to an error in the model data or in the model formulation. It you think that your model should be convex (or, in the discrete case, have a convex relaxation), you can set the NonConvex parameter to 0 or 1. With this setting, a non-convex quadratic objective leads to a Q_NOT_PSD error.

These properties are checked on the presolved model. As is always the case, presolve will try to simplify the model. In this context, it will try to transform a non-convex MIQP into an equivalent convex MIQP. This simplification will always succeed if each quadratic term contains at least one binary variable.

How can you determine whether your quadratic objective is convex? As was noted earlier, the crucial property for convexity is that interpolation between any two points on the function never puts you below the function (assuming minimization). In this figure, all points on a line segment between any two points on the parabola are always in the shaded region.

How does this translate to multiple variables? For a quadratic function to be convex, the associated Q matrix must be Positive Semi-Definite (PSD).

Multiple Objectives

You can also specify multiple (linear) objectives for your model, and Gurobi provides tools that allow you explore the tradeoffs between them. Refer to the Multiple Objectives section for additional details.