C++ İçin VEYA Araçlarını Kullanmaya Başlama

Aşağıdaki bölümler, C++ ile VEYA Araçları'nı kullanmaya başlamanızı sağlayacaktır:

Optimizasyon sorunu nedir?

Optimizasyonun amacı, bir sorun için birçok olası çözüm arasından en iyi çözümü bulmaktır. (Bazen uygun bir çözüm bulmak sizi tatmin eder; VEYA araçları bunu da yapabilir.)

Tipik bir optimizasyon problemi aşağıda açıklanmıştır. Bir nakliye şirketinin, kamyon filosu kullanarak paketleri müşterilerine teslim ettiğini varsayalım. Şirketin her gün paketleri kamyonlara ataması ve ardından her kamyonun paketlerini teslim edeceği bir rota seçmesi gerekir. Paket ve rotalar için her olası atamanın, kamyonların toplam seyahat mesafesine ve diğer muhtemel faktörlere bağlı olarak bir maliyeti vardır. Sorun, en düşük maliyetli paket ve rota atamalarını seçmektir.

Tüm optimizasyon problemlerinde olduğu gibi bu sorun da aşağıdaki öğeleri içerir:

  • Hedef: Optimize etmek istediğiniz miktar. Yukarıdaki örnekte amaç maliyeti en aza indirmektir. Optimizasyon problemi oluşturmak için olası herhangi bir çözüm için hedefin değerini hesaplayan bir fonksiyon tanımlamanız gerekir. Buna nesne işlevi denir. Yukarıdaki örnekte amaç işlevi, paket ve rota atamalarının toplam maliyetini hesaplar.

    Optimum çözüm, hedef fonksiyonu değerinin en iyi olduğu çözümdür. ("En iyi", maksimum veya minimum bir değer olabilir.)

  • Kısıtlamalar: Sorunun özel gereksinimlerine bağlı olarak olası çözüm grubu üzerindeki kısıtlamalar. Örneğin, gönderim şirketi belirli bir ağırlığın üzerindeki paketleri kamyonlara atayamazsa bu durum çözümlere bir kısıtlama uygular.

    Uygulanabilir çözüm, mutlaka optimum olmasa da sorun için verilen tüm kısıtlamaları karşılayan bir çözümdür.

Bir optimizasyon sorununu çözmenin ilk adımı, hedefi ve kısıtlamaları belirlemektir.

C++'ta bir optimizasyon problemi çözme

Ardından, bir optimizasyon sorunu örneği vererek bu problemin C++'ta nasıl oluşturulup çözüleceğini göstereceğiz.

Doğrusal optimizasyon örneği

En eski ve en çok kullanılan optimizasyon alanlarından biri, hedef fonksiyonu ve kısıtlamaların doğrusal ifadeler olarak yazılabileceği doğrusal optimizasyon (veya doğrusal programlama) alanıdır. Aşağıda, bu tür bir soruna ilişkin basit bir örnek verilmiştir.

Aşağıdaki kısıtlamalara tabi olarak 3x + y değerini en üst düzeye çıkarın:

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

Bu örnekteki amaç fonksiyonu 3x + y'dir. Hem amaç fonksiyonu hem de kısıtlar doğrusal ifadelerle verilir. Bu nedenle, problem doğrusaldır.

Sorunun çözümündeki ana adımlar

Her dilde sorun oluşturma ve çözme temel adımları aynıdır:

  1. Gerekli kitaplıkları içe aktarın,
  2. Çözücüyü tanımlayın,
  3. Değişkenleri oluşturun,
  4. Kısıtlamaları tanımlayın,
  5. Hedef fonksiyonunu tanımlayın,
  6. Çözücüyü çağırın ve
  7. Sonuçları görüntüleyin.

C++ programı

Bu bölümde, sorunu oluşturan ve çözen bir C++ programı ele alınmaktadır.

İzleyeceğiniz adımlar aşağıda açıklanmıştır:

  • Gerekli kitaplıkları içe aktarın. 
    #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"
  • Çözücüyü tanımlayın. 
    // 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, doğrusal programlama veya karma tamsayı programlama problemlerini çözmek için kullanılan bir sarmalayıcıdır.
  • Değişkenleri oluşturun. 
    // 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();
  • Kısıtlamaları tanımlayın. İlk iki kısıtlama (0 &leq; x ≤ 1 ve 0 &leq; y ≤ 2) değişkenlerin tanımlarına göre zaten belirlenmiştir. Aşağıdaki kod x + y &leq; 2 kısıtlamasını tanımlar: 
    // 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();
    SetCoefficient yöntemi, kısıtlama ifadesindeki x ve y katsayılarını belirler.
  • Hedef işlevini tanımlama. 
    // Create the objective function, 3 * x + y.
MPObjective* const objective = solver->MutableObjective();
objective->SetCoefficient(x, 3);
objective->SetCoefficient(y, 1);
objective->SetMaximization();
    SetMaximization yöntemi, bunun bir maksimizasyon problemi olduğunu bildirir.
  • Çözücüyü çağırın ve sonuçları görüntüleyin. 
    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();

Programı tamamlayın

Programın tamamı aşağıda gösterilmektedir.

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

C++ programını çalıştırma

Yukarıdaki programı şu şekilde yürütebilirsiniz:

  1. Yukarıdaki kodu kopyalayıp yeni bir dosyaya yapıştırın ve program.cc olarak kaydedin.
  2. OR-Tools'u yüklediğiniz dizinin en üst düzeyinde bir komut penceresi açın ve şunu girin: 
    make run SOURCE=relative/path/to/program.cc
    Burada relative/path/to/, programı kaydettiğiniz dizinin yoludur.

Program, hedef işlevini en üst düzeye çıkaran x ve y değerlerini döndürür:

Solution:
x =  1.0
y =  1.0

Programı çalıştırmadan derlemek için şunu girin:

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

Opt modunda derleniyor

O3 modunda derlemek için:

make DEBUG='-O3' all

C++ yürütülebilir dosyasını çalıştırma

make ile bir OR-Tools C++ programı derlediğinizde, yürütülebilir dosya bin dizininde oluşturulur. Örnek programın yürütülebilir dosyasını aşağıdaki gibi çalıştırabilirsiniz:

cd bin && ./program

Programda değişiklik yaparsanız, programı yukarıda gösterildiği gibi yeniden derlemeniz gerekir.

Diğer C++ örnekleri

Çeşitli optimizasyon sorunlarının nasıl çözüleceğini gösteren daha fazla C++ örneği için Örnekler bölümüne bakın.

Çözmek istediğiniz problem türünü belirleme

Dünyada birçok farklı türde optimizasyon sorunu vardır. Her sorun türü için en uygun çözümü bulmaya yönelik farklı yaklaşımlar ve algoritmalar vardır.

Bir optimizasyon problemini çözmek üzere program yazmaya başlamadan önce, ne tür bir sorunla uğraştığınızı belirlemeniz ve ardından uygun bir çözücü (en uygun çözümü bulmaya yönelik bir algoritma) seçmeniz gerekir.

Aşağıda, VEYA araçlarının çözdüğü sorun türlerine kısa bir genel bakışın yanı sıra bu kılavuzdaki, her bir sorun türünün nasıl çözüleceğini açıklayan bölümlerin bağlantıları yer almaktadır.

Doğrusal optimizasyon

Bir önceki bölümde öğrendiğiniz gibi, doğrusal optimizasyon problemi, hedef fonksiyonu ve kısıtlamaların değişkenlerdeki doğrusal ifadeler olduğu sorundur.

Bu tür sorunlar için OR Araçları'ndaki birincil çözücü, doğrusal optimizasyon çözücüdür. Bu çözücü, aslında üçüncü taraf kitaplıklar da dahil olmak üzere, doğrusal ve karma tamsayı optimizasyonu için birkaç farklı kitaplığın sarmalayıcısıdır.

Doğrusal optimizasyon hakkında daha fazla bilgi

Karma tam sayı optimizasyonu

Karışık tam sayı optimizasyon problemi, değişkenlerin bazılarının veya tümünün tam sayı olmasını gerektiren bir problemdir. Örneğin, bir çalışan grubunun bir dizi göreve atanması gereken atama problemi. Her çalışan ve görev için, belirtilen çalışan belirli bir göreve atanmışsa değeri 1, aksi halde 0 olan bir değişken tanımlarsınız. Bu durumda, değişkenler yalnızca 0 veya 1 değerlerini alabilir.

Karma tam sayı optimizasyonu hakkında daha fazla bilgi

Kısıtlama optimizasyonu

Kısıtlama optimizasyonu veya kısıt programlama (CP), sorunun rastgele kısıtlamalara göre modellenebileceği çok büyük bir aday grubu içinden uygulanabilir çözümleri tanımlar. CP, optimizasyon (en iyi çözüm bulma) yerine fizibiliteyi (uygun bir çözüm bulma) temel alır ve amaç işlevi yerine kısıtlar ve değişkenlere odaklanır. Bununla birlikte CP, optimizasyon problemlerini çözmek için kullanılabilir. Tüm uygulanabilir çözümler için hedef fonksiyonunun değerlerini karşılaştırarak kullanılabilir.

Kısıtlama optimizasyonu hakkında daha fazla bilgi

Ödev

Atama problemleri, bir aracı grubunun (ör. çalışanlar veya makineler) bir görev kümesine atanmasını içerir. Bu durumda, her bir aracıyı belirli bir göreve atamanın sabit bir maliyeti vardır. Problem, toplam maliyeti en düşük olan ödevi bulmaktır. Atama sorunları aslında ağ akışı sorunlarının özel bir durumudur.

Atama hakkında daha fazla bilgi

Paketleme

Kutu paketleme, farklı boyutlardaki bir dizi nesneyi farklı kapasitelere sahip kapsayıcılara paketleme sorunudur. Amaç, container'ların kapasitesine bağlı olarak mümkün olduğunca çok nesneyi paketlemektir. Bunun özel bir durumu, yalnızca bir container'ın bulunduğu Sırt çantası sorunudur.

Kutu paketleme hakkında daha fazla bilgi

Scheduling (Zaman planlama)

Zaman çizelgesi problemleri, bir dizi görevi belirli zamanlarda gerçekleştirmek için kaynaklar atamayı içerir. Önemli bir örnek olarak, birden fazla işin birkaç makinede işlendiği iş atölyesi sorunu verilebilir. Her iş, belirli bir sırada gerçekleştirilmesi ve her görevin belirli bir makinede işlenmesi gereken bir görev dizisinden oluşur. Sorun, tüm işlerin mümkün olduğunca kısa bir zaman aralığı içinde tamamlanmasını sağlayacak bir zaman çizelgesi atamaktır.

Planlama hakkında daha fazla bilgi

Yönlendirme

Rota sorunları, bir araç filosunun bir ağı geçmek için yönlendirilmiş bir grafikle tanımlanan en iyi rotaları bulmayı içerir. Optimizasyon sorunu nedir? bölümünde açıklanan, teslimat kamyonlarına paket atama sorunu yönlendirme sorunlarına bir örnektir. Bir diğeri de seyahat eden satış görevlisi sorunu.

Yönlendirme hakkında daha fazla bilgi

Ağ akışları

Birçok optimizasyon problemi, düğümler ve yönlendirilmiş yaylardan oluşan yönlendirilmiş bir grafikle temsil edilebilir. Örneğin, ürünlerin bir demiryolu ağı boyunca gönderildiği ulaşım sorunları, yayların demiryolu hatları ve düğümlerin dağıtım merkezleri olduğu bir grafikle gösterilebilir.

Maksimum akış probleminde, her bir yay boyunca aktarılabilecek bir maksimum kapasitesi vardır. Sorun, taşınan toplam miktarın mümkün olduğunca büyük olacağı şekilde her bir yay boyunca gönderilecek mal miktarını atamaktır.

Ağ akışları hakkında daha fazla bilgi