Mulai Menggunakan OR-Tools untuk Java

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

Apa yang dimaksud dengan masalah pengoptimalan?

Sasaran 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 adalah masalah pengoptimalan umum. Misalkan perusahaan pengiriman mengirimkan paket kepada pelanggannya menggunakan armada truk. Setiap hari, perusahaan harus memberikan paket ke truk, lalu memilih rute untuk setiap truk untuk mengirimkan paket. Setiap kemungkinan penetapan paket dan rute memiliki biaya, berdasarkan total jarak perjalanan truk, dan mungkin juga faktor-faktor lainnya. 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. Pada contoh di atas, tujuannya adalah untuk meminimalkan biaya. Untuk menyiapkan soal pengoptimalan, Anda perlu menentukan fungsi yang menghitung nilai objektif untuk setiap kemungkinan solusi. Hal ini disebut fungsi objektif. Pada contoh sebelumnya, fungsi objektif akan menghitung total biaya untuk penetapan paket dan rute.

    Solusi yang optimal adalah solusi yang nilai fungsi objeknya paling baik. ("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 ke truk, hal ini akan menerapkan batasan pada solusi.

    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 akan memberikan contoh masalah pengoptimalan, serta menunjukkan cara menyiapkan dan menyelesaikannya di Java.

Contoh pengoptimalan linear

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

Maksimalkan 3x + y sesuai dengan batasan berikut:

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

Fungsi tujuan 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 sama:

  1. Impor {i>library<i} yang dibutuhkan,
  2. Deklarasikan pemecahnya,
  3. Buat variabelnya,
  4. Tentukan batasan-batasan,
  5. Definisikan fungsi tujuan,
  6. Panggil pemecah masalah dan
  7. Menampilkan hasilnya.

Program Java<

Bagian ini membahas program Java yang menyiapkan dan mengatasi masalah.

Berikut langkah-langkahnya:

  • Impor library yang diperlukan. 
    import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;
  • Deklarasikan pemecahnya. 
    // Create the linear solver with the GLOP backend.
MPSolver solver = MPSolver.createSolver("GLOP");
    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 berdasarkan definisi variabel. Kode berikut menentukan batasan x + y &leq; 2: 
    // Create a linear constraint, 0 <= x + y <= 2.
MPConstraint ct = solver.makeConstraint(0.0, 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 ini sebagai masalah pemaksimalan.
  • Panggil pemecah masalah dan tampilkan hasilnya. 
    solver.solve();
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.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();
    // Create the linear solver with the GLOP backend.
    MPSolver solver = MPSolver.createSolver("GLOP");

    // 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());

    // Create a linear constraint, 0 <= x + y <= 2.
    MPConstraint ct = solver.makeConstraint(0.0, 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();

    solver.solve();

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

  private BasicExample() {}
}

Menjalankan program Java

Anda dapat menjalankan program di atas sebagai berikut:

  1. Salin dan tempel kode di atas ke dalam file baru, lalu 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.

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

Solution:
x =  1.0
y =  1.0

Untuk mengompilasi program tanpa menjalankannya, 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 berbagai 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 sedang ditangani, 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 dipecahkan oleh OR-Tools, dan link ke bagian dalam panduan ini yang menjelaskan cara menyelesaikan setiap jenis masalah.

Pengoptimalan linear

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

Pemecah masalah utama di OR-Tools untuk jenis masalah ini adalah pemecah pengoptimalan linear, yang sebenarnya merupakan wrapper untuk 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 ketika 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 diberikan ditugaskan ke tugas yang diberikan, dan 0 jika sebaliknya. Dalam hal ini, variabel hanya dapat mengambil nilai 0 atau 1.

Pelajari pengoptimalan campuran bilangan bulat lebih lanjut

Pengoptimalan batasan

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

Pelajari pengoptimalan batasan lebih lanjut

Assignment

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

Pelajari tugas lebih lanjut

Pengemasan

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

Pelajari pengemasan tempat sampah lebih lanjut

Penjadwalan

Masalah penjadwalan melibatkan penetapan resource untuk menjalankan serangkaian tugas pada waktu tertentu. Contoh penting adalah masalah job shop, yang mana beberapa tugas diproses di beberapa komputer. Setiap tugas terdiri dari urutan tugas, yang harus dilakukan dalam urutan tertentu, dan setiap tugas harus diproses di mesin tertentu. Masalahnya adalah menetapkan jadwal sehingga semua tugas selesai dalam interval waktu sesingkat mungkin.

Pelajari penjadwalan lebih lanjut

Pemilihan rute

Masalah pemilihan 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 itu masalah pengoptimalan?, adalah salah satu contoh masalah pemilihan rute. Lainnya adalah masalah penjual keliling.

Pelajari pemilihan rute lebih lanjut

Alur jaringan

Banyak masalah pengoptimalan dapat direpresentasikan oleh grafik terarah yang terdiri dari node dan busur terarah di antaranya. Misalnya, masalah transportasi, saat barang dikirim melalui jaringan kereta api, dapat diwakili oleh grafik yang busurnya adalah jalur kereta api dan node adalah pusat distribusi.

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

Pelajari alur jaringan lebih lanjut