Mulai Menggunakan OR-Tools untuk Java

Bagian berikut akan membantu Anda memulai OR-Tools untuk Java:

• Apa yang dimaksud dengan masalah pengoptimalan?
• Menyelesaikan masalah pengoptimalan di Java
• Contoh Java lainnya
• Mengidentifikasi jenis masalah yang ingin Anda selesaikan

Apa yang dimaksud dengan masalah pengoptimalan?

Tujuan pengoptimalan adalah menemukan solusi terbaik untuk masalah dari sejumlah besar kemungkinan solusi. (Terkadang Anda akan puas menemukan solusi yang layak; OR-Tools juga dapat melakukannya.)

Berikut masalah pengoptimalan yang umum. Misalkan perusahaan pengiriman mengirimkan paket kepada pelanggannya menggunakan armada truk. Setiap hari, perusahaan harus memasukkan paket ke truk, lalu memilih rute untuk setiap truk untuk mengirimkan paketnya. Setiap kemungkinan penetapan paket dan rute memiliki biaya, berdasarkan total jarak perjalanan truk, dan mungkin faktor lainnya juga. Masalahnya adalah memilih penetapan paket dan rute yang memiliki biaya paling rendah.

Seperti semua masalah pengoptimalan, masalah ini memiliki elemen berikut:

• Tujuan—kuantitas yang ingin Anda optimalkan. Dalam contoh di atas, tujuannya adalah untuk meminimalkan biaya. Untuk menyiapkan masalah pengoptimalan, Anda perlu menentukan fungsi yang menghitung nilai objektif untuk setiap kemungkinan solusi. Ini disebut fungsi objektif. Pada contoh sebelumnya, fungsi objektif akan menghitung total biaya untuk setiap penetapan paket dan rute.

  Solusi yang optimal adalah solusi yang nilai fungsi objektifnya paling tinggi. ("Terbaik" dapat berupa nilai maksimum atau minimum.)

• Batasan—batasan pada serangkaian kemungkinan solusi, berdasarkan persyaratan spesifik dari masalah. Misalnya, jika perusahaan pengiriman tidak dapat menetapkan paket di atas berat yang ditentukan untuk truk, hal ini akan menerapkan batasan pada solusinya.

  Solusi yang layak adalah solusi yang memenuhi semua batasan yang diberikan untuk masalah tersebut, tanpa harus optimal.

Langkah pertama dalam memecahkan masalah pengoptimalan adalah mengidentifikasi tujuan dan batasan.

Menyelesaikan masalah pengoptimalan di Java

Selanjutnya, kita berikan contoh masalah pengoptimalan, dan cara menyiapkan serta menyelesaikannya di Java.

Contoh pengoptimalan linear

Salah satu area pengoptimalan terlama dan paling banyak digunakan adalah pengoptimalan linear (atau pemrograman linear), yang mana fungsi objektif dan batasan dapat ditulis sebagai ekspresi linear. Berikut adalah contoh sederhana dari masalah seperti ini.

Maksimalkan 3x + y sesuai dengan batasan berikut:

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

Fungsi objektif dalam contoh ini adalah 3x + y. Fungsi objektif dan batasan diberikan oleh ekspresi linear, yang menjadikannya masalah linear.

Langkah utama dalam memecahkan masalah

Untuk setiap bahasa, langkah dasar penyiapan dan pemecahan masalah adalah sama:

1. Impor library yang dibutuhkan,
2. Deklarasikan pemecahnya,
3. Buat variabel-variabel,
4. Tentukan batasan-batasan,
5. Tentukan fungsi tujuan,
6. Panggil pemecah masalah dan
7. Menampilkan hasilnya.

Program Java<

Bagian ini membahas program Java yang menyiapkan dan mengatasi masalah.

Catatan: Program Java lengkap dan langkah-langkah untuk menjalankannya ditampilkan di akhir bagian ini.

Berikut langkah-langkahnya:

• Impor library yang diperlukan.

  import com.google.ortools.Loader;
  import com.google.ortools.init.OrToolsVersion;
  import com.google.ortools.linearsolver.MPConstraint;
  import com.google.ortools.linearsolver.MPObjective;
  import com.google.ortools.linearsolver.MPSolver;
  import com.google.ortools.linearsolver.MPVariable;

• Mendeklarasikan pemecahnya.

  // Create the linear solver with the GLOP backend.
  MPSolver solver = MPSolver.createSolver("GLOP");
  if (solver == null) {
    System.out.println("Could not create solver GLOP");
    return;
  }

  MPSolver adalah wrapper untuk memecahkan masalah pemrograman linear atau pemrograman bilangan bulat campuran.
• Buat variabel.

  // Create the variables x and y.
  MPVariable x = solver.makeNumVar(0.0, 1.0, "x");
  MPVariable y = solver.makeNumVar(0.0, 2.0, "y");
  
  System.out.println("Number of variables = " + solver.numVariables());

• Tentukan batasan. Dua batasan pertama, 0 &leq; x ≤ 1 dan 0 &leq; y ≤ 2, sudah ditetapkan oleh definisi variabel. Kode berikut menentukan batasan x + y &leq; 2:

  double infinity = Double.POSITIVE_INFINITY;
  // Create a linear constraint, x + y <= 2.
  MPConstraint ct = solver.makeConstraint(-infinity, 2.0, "ct");
  ct.setCoefficient(x, 1);
  ct.setCoefficient(y, 1);
  
  System.out.println("Number of constraints = " + solver.numConstraints());

  Metode setCoefficient menetapkan koefisien x dan y dalam ekspresi untuk batasan.
• Tentukan fungsi tujuan.

  // Create the objective function, 3 * x + y.
  MPObjective objective = solver.objective();
  objective.setCoefficient(x, 3);
  objective.setCoefficient(y, 1);
  objective.setMaximization();

  Metode setMaximization mendeklarasikan sebagai masalah pemaksimalan.
• Panggil pemecah masalah dan tampilkan hasilnya.

  System.out.println("Solving with " + solver.solverVersion());
  final MPSolver.ResultStatus resultStatus = solver.solve();
  System.out.println("Status: " + resultStatus);
  if (resultStatus != MPSolver.ResultStatus.OPTIMAL) {
    System.out.println("The problem does not have an optimal solution!");
    if (resultStatus == MPSolver.ResultStatus.FEASIBLE) {
      System.out.println("A potentially suboptimal solution was found");
    } else {
      System.out.println("The solver could not solve the problem.");
      return;
    }
  }
  
  System.out.println("Solution:");
  System.out.println("Objective value = " + objective.value());
  System.out.println("x = " + x.solutionValue());
  System.out.println("y = " + y.solutionValue());

Selesaikan program

Program lengkapnya ditampilkan di bawah ini.

package com.google.ortools.linearsolver.samples;

import com.google.ortools.Loader;
import com.google.ortools.init.OrToolsVersion;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;

/** Minimal Linear Programming example to showcase calling the solver. */
public final class BasicExample {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();

    System.out.println("Google OR-Tools version: " + OrToolsVersion.getVersionString());

    // Create the linear solver with the GLOP backend.
    MPSolver solver = MPSolver.createSolver("GLOP");
    if (solver == null) {
      System.out.println("Could not create solver GLOP");
      return;
    }

    // Create the variables x and y.
    MPVariable x = solver.makeNumVar(0.0, 1.0, "x");
    MPVariable y = solver.makeNumVar(0.0, 2.0, "y");

    System.out.println("Number of variables = " + solver.numVariables());

    double infinity = Double.POSITIVE_INFINITY;
    // Create a linear constraint, x + y <= 2.
    MPConstraint ct = solver.makeConstraint(-infinity, 2.0, "ct");
    ct.setCoefficient(x, 1);
    ct.setCoefficient(y, 1);

    System.out.println("Number of constraints = " + solver.numConstraints());

    // Create the objective function, 3 * x + y.
    MPObjective objective = solver.objective();
    objective.setCoefficient(x, 3);
    objective.setCoefficient(y, 1);
    objective.setMaximization();

    System.out.println("Solving with " + solver.solverVersion());
    final MPSolver.ResultStatus resultStatus = solver.solve();

    System.out.println("Status: " + resultStatus);
    if (resultStatus != MPSolver.ResultStatus.OPTIMAL) {
      System.out.println("The problem does not have an optimal solution!");
      if (resultStatus == MPSolver.ResultStatus.FEASIBLE) {
        System.out.println("A potentially suboptimal solution was found");
      } else {
        System.out.println("The solver could not solve the problem.");
        return;
      }
    }

    System.out.println("Solution:");
    System.out.println("Objective value = " + objective.value());
    System.out.println("x = " + x.solutionValue());
    System.out.println("y = " + y.solutionValue());

    System.out.println("Advanced usage:");
    System.out.println("Problem solved in " + solver.wallTime() + " milliseconds");
    System.out.println("Problem solved in " + solver.iterations() + " iterations");
  }

  private BasicExample() {}
}

Menjalankan program Java

Anda dapat menjalankan program di atas sebagai berikut:

1. Salin dan tempel kode di atas ke dalam file baru, dan simpan sebagai my_program.java.
2. Buka jendela perintah di tingkat teratas direktori tempat Anda menginstal OR-Tools, lalu masukkan:

   make run SOURCE=relative/path/to/my_program.java

   dengan relative/path/to/ adalah jalur ke direktori tempat Anda menyimpan program.

Catatan: Anda harus menjalankan perintah di atas dari tingkat teratas direktori tempat Anda menginstal OR-Tools (tempat Makefile berada).

Program ini menampilkan nilai x dan y yang memaksimalkan fungsi tujuan:

Solution:
x =  1.0
y =  1.0

Untuk mengompilasi program tanpa menjalankannya saja, masukkan:

make build SOURCE=relative/path/to/my_program.java

Contoh Java lainnya

Untuk contoh Java lainnya yang menggambarkan cara menyelesaikan berbagai jenis masalah pengoptimalan, lihat Contoh.

Mengidentifikasi jenis masalah yang ingin Anda selesaikan

Ada banyak jenis masalah pengoptimalan di dunia. Untuk setiap jenis masalah, ada pendekatan dan algoritma yang berbeda untuk menemukan solusi yang optimal.

Sebelum dapat mulai menulis program untuk memecahkan masalah pengoptimalan, Anda harus mengidentifikasi jenis masalah yang dihadapi, lalu memilih pemecah masalah yang sesuai, yaitu sebuah algoritma untuk menemukan solusi yang optimal.

Di bawah ini Anda akan menemukan ringkasan singkat tentang jenis masalah yang dapat diselesaikan OR-Tools, dan link ke bagian dalam panduan ini yang menjelaskan cara menyelesaikan setiap jenis masalah.

• Pengoptimalan linear
• Pengoptimalan batasan
• Pengoptimalan bilangan bulat campuran
• Pemindahan Hak
• Penjadwalan
• Pengemasan
• Perutean
• Alur jaringan

Pengoptimalan linear

Seperti yang Anda pelajari di bagian sebelumnya, masalah pengoptimalan linear adalah masalah yang mana fungsi objektif dan batasannya adalah ekspresi linear dalam variabel.

Pemecah masalah utama dalam OR-Tools untuk jenis masalah ini adalah pemecah pengoptimalan linear, yang sebenarnya merupakan wrapper beberapa library yang berbeda untuk linear dan pengoptimalan bilangan bulat campuran, termasuk library pihak ketiga.

Pelajari pengoptimalan linear lebih lanjut

Pengoptimalan bilangan bulat campuran

Masalah pengoptimalan bilangan bulat campuran adalah masalah saat beberapa atau semua variabel harus berupa bilangan bulat. Contohnya adalah masalah penetapan, ketika sekelompok pekerja perlu ditetapkan ke serangkaian tugas. Untuk setiap pekerja dan tugas, Anda menentukan variabel yang nilainya adalah 1 jika pekerja yang ditentukan ditetapkan ke tugas yang diberikan, dan 0 jika sebaliknya. Dalam hal ini, variabel hanya dapat mengambil nilai 0 atau 1.

Pelajari pengoptimalan bilangan bulat campuran lebih lanjut

Pengoptimalan batasan

Pengoptimalan batasan, atau pemrograman batasan (CP), mengidentifikasi solusi yang memungkinkan dari sekumpulan kandidat yang sangat besar, yang mana masalah tersebut dapat dimodelkan dalam hal batasan arbitrer. CP didasarkan pada kelayakan (menemukan solusi yang layak), bukan pengoptimalan (menemukan solusi yang optimal) dan berfokus pada batasan dan variabel, bukan fungsi objektif. Namun, CP dapat digunakan untuk menyelesaikan masalah pengoptimalan, cukup dengan membandingkan nilai fungsi objektif untuk semua solusi yang memungkinkan.

Pelajari pengoptimalan batasan lebih lanjut

Assignment

Masalah penetapan berarti menetapkan sekelompok agen (misalnya, pekerja atau mesin) ke sekumpulan tugas, dengan biaya tetap untuk menetapkan setiap agen ke tugas tertentu. Masalahnya adalah menemukan tugas dengan total biaya terkecil. Masalah penetapan sebenarnya adalah kasus khusus masalah alur jaringan.

Pelajari tugas lebih lanjut

Pengemasan

Pengemasan keranjang adalah masalah pengemasan kumpulan objek dengan ukuran yang berbeda ke dalam kontainer dengan kapasitas berbeda. Tujuannya adalah untuk mengemas objek sebanyak mungkin, sesuai dengan kapasitas container. Kasus khusus dari hal ini adalah masalah Knapsack, yang hanya memiliki satu container.

Pelajari pengemasan sampah lebih lanjut

Penjadwalan

Masalah penjadwalan melibatkan penetapan resource untuk melakukan serangkaian tugas pada waktu tertentu. Contoh pentingnya adalah masalah di bengkel kerja, ketika beberapa pekerjaan diproses di beberapa mesin. Setiap tugas terdiri dari serangkaian tugas, yang harus dilakukan dalam urutan tertentu, dan setiap tugas harus diproses pada mesin tertentu. Masalahnya adalah menetapkan jadwal sehingga semua tugas selesai dalam interval waktu sesingkat mungkin.

Pelajari penjadwalan lebih lanjut

Pemilihan rute

Masalah rute melibatkan pencarian rute optimal bagi armada kendaraan untuk melintasi jaringan, yang ditentukan oleh grafik terarah. Masalah penetapan paket ke truk pengiriman, yang dijelaskan dalam Apa yang dimaksud dengan masalah pengoptimalan?, adalah salah satu contoh masalah perutean. Masalah lainnya adalah masalah penjual yang bepergian.

Pelajari pemilihan rute lebih lanjut

Alur jaringan

Banyak masalah pengoptimalan dapat direpresentasikan oleh grafik terarah yang terdiri dari node dan busur terarah di antara keduanya. Misalnya, masalah transportasi, yang mana barang dikirimkan melalui jaringan kereta api, dapat diwakili oleh grafik yang busurnya adalah jalur kereta api dan node-nodenya adalah pusat distribusi.

Pada masalah alur maksimum, setiap busur memiliki kapasitas maksimum yang dapat dipindahkan. Masalahnya adalah menetapkan jumlah barang yang akan dikirim melalui setiap busur sehingga jumlah total yang diangkut sebesar mungkin.

Pelajari alur jaringan lebih lanjut