3.9. How does the solver optimize?

The main idea is simple. When you define an objective function, as in tutorials/cplusplus/chap3/golom1.cc:

OptimizeVar* const length = s.MakeMinimize(Y[num_vars - 1], 1);

you basically tell the solver three things:

1. to minimize the objective function;
2. the objective function is defined by the variable Y[num_vars - 1] and
3. the improvement step is .

The last instruction ensures that each time the solver finds a feasible solution with a value , it will attempt to find a better solution with value and so on until it cannot find a feasible solution with a give value . The optimal value is thus in this case .

You can give any (positive) integer value as an improvement step to the solver:

OptimizeVar* const obj = s.MakeMaximize(obj_var, 42);

but beware that by default, there isn’t any smart algorithm implemented in or-tools to change this improvement step during the search. If the solver finds a solution with an objective value of , it will try next to find a solution with an objective value of [1]. If it finds one, it will try to find another solution with an objective value of but if doesn’t find any feasible solution with a value of , it will stop the search and return the “best” solution with a value of !

If you use an improvement step of , you can be sure to reach an optimal solution if you provide the solver with enough time and memory but you could also devise your own algorithm to change this improvement step during the search.

Footnote

[1]	It took us a while but we are pretty sure that .