Comece a usar ferramentas OR para C++

As seções a seguir mostram os primeiros passos com as ferramentas OR com C++:

O que é um problema de otimização?

O objetivo da otimização é encontrar a melhor solução para um problema entre um grande conjunto de soluções possíveis. Às vezes, você ficará satisfeito em encontrar uma solução viável; o OR-Tools também pode fazer isso.

Veja um problema de otimização típico. Suponha que uma empresa de remessa entregue pacotes aos clientes usando uma frota de caminhões. Todos os dias, a empresa precisa atribuir pacotes aos caminhões e escolher um trajeto para cada caminhão para entregar as encomendas. Cada atribuição possível de pacotes e trajetos tem um custo, com base na distância total de viagem dos caminhões e possivelmente em outros fatores. O problema é escolher as atribuições de pacotes e trajetos com o menor custo.

Como todos os problemas de otimização, esse problema tem os seguintes elementos:

  • O objetivo: a quantidade que você quer otimizar. No exemplo acima, o objetivo é minimizar o custo. Para configurar um problema de otimização, defina uma função que calcule o valor do objetivo para qualquer solução possível. Isso é chamado de função de objetivo. No exemplo anterior, a função objetiva calcularia o custo total de qualquer atribuição de pacotes e rotas.

    Uma solução ideal é aquela em que o valor da função objetiva é o melhor. ("Melhor" pode ser o máximo ou o mínimo.)

  • As restrições: restrições no conjunto de soluções possíveis, com base nos requisitos específicos do problema. Por exemplo, se a transportadora não puder atribuir pacotes acima de um determinado peso aos caminhões, isso imporá uma restrição às soluções.

    Uma solução viável é aquela que satisfaz todas as restrições dadas para o problema, sem ser necessariamente ideal.

A primeira etapa para resolver um problema de otimização é identificar o objetivo e as restrições.

Como resolver um problema de otimização em C++

Em seguida, apresentamos um exemplo de um problema de otimização e mostramos como configurá-lo e resolvê-lo em C++.

Um exemplo de otimização linear

Uma das áreas mais antigas e mais usadas de otimização é a otimização linear (ou programação linear), em que a função objetiva e as restrições podem ser escritas como expressões lineares. Veja um exemplo simples desse tipo de problema.

A estratégia "Maximizar 3x + y" está sujeita às seguintes restrições:

  1. 0 ≤ x ≤ 1
  2. 0 ≤ y ≤ 2
  3. x + y ≤ 2

A função de objetivo neste exemplo é 3x + y. Tanto a função objetiva quanto as restrições são fornecidas por expressões lineares, o que torna isso um problema linear.

Principais etapas para resolver o problema

Para cada linguagem, as etapas básicas para configurar e resolver um problema são as mesmas:

  1. Importe as bibliotecas necessárias,
  2. Declare o solucionador,
  3. Crie as variáveis
  4. Defina as restrições,
  5. Defina a função objetiva,
  6. Invoque o solucionador e
  7. Exiba os resultados.

Programa C++

Esta seção aborda um programa em C++ que configura e resolve o problema.

Siga estas etapas:

  • Importe as bibliotecas necessárias. 
    #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 o solucionador. 
    // 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 é um wrapper para resolver problemas de programação linear ou programação de números inteiros mista.
  • Crie as variáveis. 
    // 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();
  • Defina as restrições. As duas primeiras restrições, 0 &leq; x ≤ 1 e 0 &leq; y ≤ 2, já estão definidas pelas definições das variáveis. O código a seguir define a restrição x + y &leq; 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();
    . O método SetCoefficient define os coeficientes de x e y na expressão da restrição.
  • Defina a função objetiva. 
    // Create the objective function, 3 * x + y.
MPObjective* const objective = solver->MutableObjective();
objective->SetCoefficient(x, 3);
objective->SetCoefficient(y, 1);
objective->SetMaximization();
    O método SetMaximization declara que esse é um problema de maximização.
  • Invoque o solucionador e exiba os resultados. 
    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();

Concluir programa

O programa completo é mostrado abaixo.

// 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;
}

Como executar o programa C++

Você pode executar o programa acima da seguinte maneira:

  1. Copie e cole o código acima no novo arquivo e salve como program.cc.
  2. Abra uma janela de comando no nível superior do diretório em que você instalou OR-Tools e digite: 
    make run SOURCE=relative/path/to/program.cc
    , em que relative/path/to/ é o caminho para o diretório em que você salvou o programa.

O programa retorna os valores de x e y que maximizam a função de objetivo:

Solution:
x =  1.0
y =  1.0

Para compilar o programa sem executá-lo, digite:

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

Compilar no modo opcional

Para compilar no modo O3:

make DEBUG='-O3' all

Como executar o executável C++

Quando você compila um programa C++ OR-Tools com make, o executável é criado no diretório bin. Execute o executável do programa de exemplo desta maneira:

cd bin && ./program

Se você fizer alterações no programa, será necessário recompilá-lo, conforme mostrado acima.

Mais exemplos de C++

Para mais exemplos em C++ que ilustram como resolver vários tipos de problemas de otimização, consulte Exemplos.

Identificar o tipo de problema que você quer resolver

Há muitos tipos diferentes de problemas de otimização no mundo. Para cada tipo de problema, há diferentes abordagens e algoritmos para encontrar a solução ideal.

Antes de começar a escrever um programa para resolver um problema de otimização, você precisa identificar o tipo de problema com o qual está lidando e, em seguida, escolher um solucionador apropriado, um algoritmo para encontrar a solução ideal.

Confira abaixo uma breve visão geral dos tipos de problemas que as ferramentas OU resolvem e links para as seções deste guia que explicam como resolver cada tipo de problema.

Otimização linear

Como você aprendeu na seção anterior, um problema de otimização linear é quando a função objetiva e as restrições são expressões lineares nas variáveis.

O principal solucionador para esse tipo de problema no OR-Tools é o solucionador de otimização linear, que é um wrapper para várias bibliotecas diferentes para otimização linear e de número inteiro misto, incluindo bibliotecas de terceiros.

Saiba mais sobre a otimização linear

Otimização de números inteiros mistos

Em um problema de otimização de números inteiros misto, ocorre um problema em que algumas ou todas as variáveis precisam ser números inteiros. Um exemplo é o problema de atribuição, em que um grupo de workers precisa ser atribuído a um conjunto de tarefas. Para cada worker e tarefa, defina uma variável com o valor 1 se o worker estiver atribuído a ela e 0 se não for. Nesse caso, as variáveis só podem assumir os valores 0 ou 1.

Saiba mais sobre a otimização de números inteiros mistos

Otimização de restrições

A otimização de restrições, ou programação de restrição (CP, na sigla em inglês), identifica soluções viáveis em um conjunto muito grande de candidatos, em que o problema pode ser modelado em termos de restrições arbitrárias. A CP é baseada na viabilidade (encontrar uma solução viável), em vez da otimização (encontrar uma solução ideal), e se concentra nas restrições e variáveis, não na função objetiva. No entanto, a CP pode ser usada para resolver problemas de otimização, simplesmente comparando os valores da função objetiva de todas as soluções viáveis.

Saiba mais sobre a otimização de restrições

Atribuição

Os problemas de atribuição envolvem atribuir um grupo de agentes (por exemplo, workers ou máquinas) a um conjunto de tarefas, em que há um custo fixo para atribuir cada agente a uma tarefa específica. O problema é encontrar a atribuição com o menor custo total. Problemas de atribuição são, na verdade, um caso especial de problemas de fluxo de rede.

Saiba mais sobre a atribuição

Embalar

O empacotamento de contêineres é o problema de empacotar um conjunto de objetos de tamanhos diferentes em contêineres com capacidades distintas. O objetivo é empacotar o maior número possível de objetos, sujeito à capacidade dos contêineres. Um caso especial é o problema do Knapsack, em que há apenas um contêiner.

Saiba mais sobre o empacotamento

Agendamento

Os problemas de programação envolvem a atribuição de recursos para executar um conjunto de tarefas em horários específicos. Um exemplo importante é o problema do job do job, em que vários jobs são processados em diversas máquinas. Cada job consiste em uma sequência de tarefas, que precisam ser executadas em uma determinada ordem, e cada tarefa precisa ser processada em uma máquina específica. O problema é atribuir uma programação para que todos os jobs sejam concluídos no menor intervalo de tempo possível.

Saiba mais sobre agendamento

Roteamento

Os problemas de trajeto envolvem a localização dos trajetos ideais para que uma frota de veículos transporte uma rede, definidos por um gráfico direcionado. O problema de atribuir pacotes a caminhões de entrega, descrito em O que é um problema de otimização?, é um exemplo de problema de roteamento. Outro é o problema do vendedor de viagens.

Saiba mais sobre o roteamento

Fluxos de rede

Muitos problemas de otimização podem ser representados por um grafo direcionado que consiste em nós e arcos direcionados entre eles. Por exemplo, problemas de transporte, em que as mercadorias são enviadas por uma rede ferroviária, podem ser representados por um gráfico em que os arcos são linhas de ferrovia e os nós são centros de distribuição.

No problema de fluxo máximo, cada arco tem uma capacidade máxima que pode ser transportada por ele. O problema é atribuir a quantidade de mercadorias a serem enviadas em cada arco, para que a quantidade total transportada seja a maior possível.

Saiba mais sobre fluxos de rede