The following sections will get you started with OR-Tools with C++:

- What is an optimization problem?
- Solving an optimization problem in C++
- More C++ examples
- Identifying the type of problem you wish to solve

## What is an optimization problem?

The goal of optimization is to find the **best** solution to a problem out of a
large set of possible solutions. (Sometimes you'll be satisfied with finding any
feasible solution; OR-Tools can do that as well.)

Here's a typical optimization problem. Suppose that a shipping company delivers packages to its customers using a fleet of trucks. Every day, the company must assign packages to trucks, and then choose a route for each truck to deliver its packages. Each possible assignment of packages and routes has a cost, based on the total travel distance for the trucks, and possibly other factors as well. The problem is to choose the assignments of packages and routes that has the least cost.

Like all optimization problems, this problem has the following elements:

The

**objective**—the quantity you want to optimize. In the example above, the objective is to minimize cost. To set up an optimization problem, you need to define a function that calculates the value of the objective for any possible solution. This is called the**objective function**. In the preceding example, the objective function would calculate the total cost of any assignment of packages and routes.An

**optimal**solution is one for which the value of the objective function is the best. ("Best" can be either a maximum or a minimum.)The

**constraints**—restrictions on the set of possible solutions, based on the specific requirements of the problem. For example, if the shipping company can't assign packages above a given weight to trucks, this would impose a constraint on the solutions.A

**feasible**solution is one that satisfies all the given constraints for the problem, without necessarily being optimal.

The first step in solving an optimization problem is identifying the objective and constraints.

## Solving an optimization problem in C++

Next, we give an example of an optimization problem, and show how to set up and solve it in C++.

### A linear optimization example

One of the oldest and most widely-used areas of optimization is
**linear optimization**
(or **linear programming**), in which the objective function and the constraints
can be written as linear expressions. Here's a simple example of this type of
problem.

**Maximize 3x + y subject to the following constraints:**

- 0 ≤
`x`

≤ 1 - 0 ≤
`y`

≤ 2 `x + y`

≤ 2

The objective function in this example is `3x + y`

.
Both the objective function and the constraints are given by linear expressions,
which makes this a linear problem.

### Main steps in solving the problem

For each language, the basic steps for setting up and solving a problem are the same:

- Import the required libraries,
- Declare the solver,
- Create the variables,
- Define the constraints,
- Define the objective function,
- Invoke the solver and
- Display the results.

### C++ program

This section walks through a C++ program that sets up and solves the problem.

Here are the steps:

- Import the required libraries.
#include <cstdlib> #include <memory> #include "absl/flags/flag.h" #include "absl/log/flags.h" #include "ortools/base/init_google.h" #include "ortools/base/logging.h" #include "ortools/init/init.h" #include "ortools/linear_solver/linear_solver.h"

- Declare the solver.
// Create the linear solver with the GLOP backend. std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP")); if (!solver) { LOG(WARNING) << "Could not create solver GLOP"; return; }

`MPSolver`

is a wrapper for solving any linear programming or mixed integer programming problems. - Create the variables.
// Create the variables x and y. MPVariable* const x = solver->MakeNumVar(0.0, 1, "x"); MPVariable* const y = solver->MakeNumVar(0.0, 2, "y"); LOG(INFO) << "Number of variables = " << solver->NumVariables();

- Define the constraints.
The first two constraints,
`0`

≤`x`

≤`1`

and`0`

≤`y`

≤`2`

, are already set by the definitions of the variables. The following code defines the constraint`x + y`

≤`2`

:// Create a linear constraint, x + y <= 2. const double infinity = solver->infinity(); MPConstraint* const ct = solver->MakeRowConstraint(-infinity, 2.0, "ct"); ct->SetCoefficient(x, 1); ct->SetCoefficient(y, 1); LOG(INFO) << "Number of constraints = " << solver->NumConstraints();

The method`SetCoefficient`

sets the coefficients of`x`

and`y`

in the expression for the constraint. - Define the objective function.
// Create the objective function, 3 * x + y. MPObjective* const objective = solver->MutableObjective(); objective->SetCoefficient(x, 3); objective->SetCoefficient(y, 1); objective->SetMaximization();

The method`SetMaximization`

declares this to be a maximization problem. - Invoke the solver and display the results.
LOG(INFO) << "Solving with " << solver->SolverVersion(); const MPSolver::ResultStatus result_status = solver->Solve(); // Check that the problem has an optimal solution. LOG(INFO) << "Status: " << result_status; if (result_status != MPSolver::OPTIMAL) { LOG(INFO) << "The problem does not have an optimal solution!"; if (result_status == MPSolver::FEASIBLE) { LOG(INFO) << "A potentially suboptimal solution was found"; } else { LOG(WARNING) << "The solver could not solve the problem."; return; } } LOG(INFO) << "Solution:"; LOG(INFO) << "Objective value = " << objective->Value(); LOG(INFO) << "x = " << x->solution_value(); LOG(INFO) << "y = " << y->solution_value();

### Complete program

The complete program is shown below.

```
// Minimal example to call the GLOP solver.
#include <cstdlib>
#include <memory>
#include "absl/flags/flag.h"
#include "absl/log/flags.h"
#include "ortools/base/init_google.h"
#include "ortools/base/logging.h"
#include "ortools/init/init.h"
#include "ortools/linear_solver/linear_solver.h"
namespace operations_research {
void BasicExample() {
LOG(INFO) << "Google OR-Tools version : " << OrToolsVersion::VersionString();
// Create the linear solver with the GLOP backend.
std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));
if (!solver) {
LOG(WARNING) << "Could not create solver GLOP";
return;
}
// Create the variables x and y.
MPVariable* const x = solver->MakeNumVar(0.0, 1, "x");
MPVariable* const y = solver->MakeNumVar(0.0, 2, "y");
LOG(INFO) << "Number of variables = " << solver->NumVariables();
// Create a linear constraint, x + y <= 2.
const double infinity = solver->infinity();
MPConstraint* const ct = solver->MakeRowConstraint(-infinity, 2.0, "ct");
ct->SetCoefficient(x, 1);
ct->SetCoefficient(y, 1);
LOG(INFO) << "Number of constraints = " << solver->NumConstraints();
// Create the objective function, 3 * x + y.
MPObjective* const objective = solver->MutableObjective();
objective->SetCoefficient(x, 3);
objective->SetCoefficient(y, 1);
objective->SetMaximization();
LOG(INFO) << "Solving with " << solver->SolverVersion();
const MPSolver::ResultStatus result_status = solver->Solve();
// Check that the problem has an optimal solution.
LOG(INFO) << "Status: " << result_status;
if (result_status != MPSolver::OPTIMAL) {
LOG(INFO) << "The problem does not have an optimal solution!";
if (result_status == MPSolver::FEASIBLE) {
LOG(INFO) << "A potentially suboptimal solution was found";
} else {
LOG(WARNING) << "The solver could not solve the problem.";
return;
}
}
LOG(INFO) << "Solution:";
LOG(INFO) << "Objective value = " << objective->Value();
LOG(INFO) << "x = " << x->solution_value();
LOG(INFO) << "y = " << y->solution_value();
LOG(INFO) << "Advanced usage:";
LOG(INFO) << "Problem solved in " << solver->wall_time() << " milliseconds";
LOG(INFO) << "Problem solved in " << solver->iterations() << " iterations";
}
} // namespace operations_research
int main(int argc, char* argv[]) {
InitGoogle(argv[0], &argc, &argv, true);
absl::SetFlag(&FLAGS_stderrthreshold, 0);
operations_research::BasicExample();
return EXIT_SUCCESS;
}
```

### Running the C++ program

You can run the program above as follows:

- Copy and paste the code above into new file, and save it as
`program.cc`

. - Open a command window at the top level of the directory where you installed
OR-Tools, and enter:
make run SOURCE=

where`relative/path/to/`program.cc`relative/path/to/`

is the path to the directory where you saved the program.

The program returns the values of `x`

and `y`

that maximize the objective
function:

```
Solution:
x = 1.0
y = 1.0
```

To just compile the program without running it, enter:

make build SOURCE=relative/path/to/program.cc

#### Compiling in opt mode

To compile in O3 mode:

make DEBUG='-O3' all

#### Running the C++ executable

When you compile an OR-Tools C++ program with `make`

, the executable is created
in the `bin`

directory. You can run the executable for the example program as
follows:

cd bin && ./program

If you make changes to the program, you'll need to re-compile it as shown above.

## More C++ examples

For more C++ examples that illustrate how to solve various types of optimization problems, see Examples.

## Identifying the type of problem you wish to solve

There are many different types of optimization problems in the world. For each type of problem, there are different approaches and algorithms for finding an optimal solution.

Before you can start writing a program to solve an optimization problem, you
need to identify what type of problem you are dealing with, and then choose an
appropriate **solver** — an algorithm for finding an optimal solution.

Below you will find a brief overview of the types of problems that OR-Tools solves, and links to the sections in this guide that explain how to solve each problem type.

- Linear optimization
- Constraint optimization
- Mixed-integer optimization
- Assignment
- Scheduling
- Packing
- Routing
- Network flows

### Linear optimization

As you learned in the previous section, a linear optimization problem is one in which the objective function and the constraints are linear expressions in the variables.

The primary solver in OR-Tools for this type of problem is the linear optimization solver, which is actually a wrapper for several different libraries for linear and mixed-integer optimization, including third-party libraries.

Learn more about linear optimization

### Mixed-integer optimization

A **mixed integer optimization** problem is one in which some or all of the
variables are required to be integers. An example is the
assignment problem, in which a group of workers needs be assigned
to a set of tasks. For each worker and task, you define a variable whose value
is 1 if the given worker is assigned to the given task, and 0 otherwise. In this
case, the variables can only take on the values 0 or 1.

Learn more about mixed-integer optimization

### Constraint optimization

Constraint optimization, or constraint programming (CP), identifies feasible solutions out of a very large set of candidates, where the problem can be modeled in terms of arbitrary constraints. CP is based on feasibility (finding a feasible solution) rather than optimization (finding an optimal solution) and focuses on the constraints and variables rather than the objective function. However, CP can be used to solve optimization problems, simply by comparing the values of the objective function for all feasible solutions.

Learn more about constraint optimization

### Assignment

**Assignment problems** involve assigning a group of agents (say, workers or
machines) to a set of tasks, where there is a fixed cost for assigning each
agent to a specific task. The problem is to find the assignment with the least
total cost. Assignment problems are actually a special case of
network flow problems.

### Packing

**Bin packing** is the problem of packing a set of objects of different sizes
into containers with different capacities. The goal is to pack as many of the
objects as possible, subject to the capacities of the containers. A special case
of this is the **Knapsack problem**, in which there is just one container.

### Scheduling

**Scheduling problems** involve assigning resources to perform a set of tasks at
specific times. An important example is the **job shop problem**, in which
multiple jobs are processed on several machines.
Each job consists of a sequence of tasks, which must be performed in a given
order, and each task must be processed on a specific machine. The problem is to
assign a schedule so that all jobs are completed in as short an interval of time
as possible.

### Routing

**Routing problems** involve finding the optimal routes for a fleet of vehicles
to traverse a network, defined by a directed graph.
The problem of assigning packages to delivery trucks, described in
What is an optimization problem ?, is one example of a routing
problem. Another is the traveling salesperson problem.

### Network flows

Many optimization problems can be represented by a directed graph consisting of nodes and directed arcs between them. For example, transportation problems, in which goods are shipped across a railway network, can be represented by a graph in which the arcs are rail lines and the nodes are distribution centers.

In the **maximum flow problem**, each arc has a maximum capacity that can be
transported across it. The problem is to assign the amount of goods to be
shipped across each arc so that the total quantity being transported is as large
as possible.