Mulai Menggunakan Alat OR untuk Python

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

• Apa yang dimaksud dengan masalah pengoptimalan?
• Menyelesaikan masalah pengoptimalan di Python
• Contoh Python 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.

Memecahkan masalah pengoptimalan di Python

Selanjutnya, kita akan memberikan contoh masalah pengoptimalan, serta cara menyiapkan dan menyelesaikannya di Python.

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 hasil.

Program Python

Bagian ini membahas program Python yang menyiapkan dan memecahkan masalah.

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

Berikut langkah-langkahnya:

• Impor library yang diperlukan.

  from ortools.init.python import init
  from ortools.linear_solver import pywraplp

• Mendeklarasikan pemecahnya.

  # Create the linear solver with the GLOP backend.
  solver = pywraplp.Solver.CreateSolver("GLOP")
  if not solver:
      print("Could not create solver GLOP")
      return

  pywraplp adalah wrapper Python untuk pemecah masalah C++ yang mendasarinya. Argumen "GLOP" menentukan GLOP, pemecah masalah linear OR-Tools.
• Buat variabel.

  # Create the variables x and y.
  x_var = solver.NumVar(0, 1, "x")
  y_var = solver.NumVar(0, 2, "y")
  
  print("Number of variables =", solver.NumVariables())

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

  infinity = solver.infinity()
  # Create a linear constraint, x + y <= 2.
  constraint = solver.Constraint(-infinity, 2, "ct")
  constraint.SetCoefficient(x_var, 1)
  constraint.SetCoefficient(y_var, 1)
  
  print("Number of constraints =", solver.NumConstraints())

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

  # Create the objective function, 3 * x + y.
  objective = solver.Objective()
  objective.SetCoefficient(x_var, 3)
  objective.SetCoefficient(y_var, 1)
  objective.SetMaximization()

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

  print(f"Solving with {solver.SolverVersion()}")
  result_status = solver.Solve()
  print(f"Status: {result_status}")
  if result_status != pywraplp.Solver.OPTIMAL:
      print("The problem does not have an optimal solution!")
      if result_status == pywraplp.Solver.FEASIBLE:
          print("A potentially suboptimal solution was found")
      else:
          print("The solver could not solve the problem.")
          return
  
  print("Solution:")
  print("Objective value =", objective.Value())
  print("x =", x_var.solution_value())
  print("y =", y_var.solution_value())

Selesaikan program

Program lengkapnya ditampilkan di bawah ini.

from ortools.init.python import init
from ortools.linear_solver import pywraplp


def main():
    print("Google OR-Tools version:", init.OrToolsVersion.version_string())

    # Create the linear solver with the GLOP backend.
    solver = pywraplp.Solver.CreateSolver("GLOP")
    if not solver:
        print("Could not create solver GLOP")
        return

    # Create the variables x and y.
    x_var = solver.NumVar(0, 1, "x")
    y_var = solver.NumVar(0, 2, "y")

    print("Number of variables =", solver.NumVariables())

    infinity = solver.infinity()
    # Create a linear constraint, x + y <= 2.
    constraint = solver.Constraint(-infinity, 2, "ct")
    constraint.SetCoefficient(x_var, 1)
    constraint.SetCoefficient(y_var, 1)

    print("Number of constraints =", solver.NumConstraints())

    # Create the objective function, 3 * x + y.
    objective = solver.Objective()
    objective.SetCoefficient(x_var, 3)
    objective.SetCoefficient(y_var, 1)
    objective.SetMaximization()

    print(f"Solving with {solver.SolverVersion()}")
    result_status = solver.Solve()

    print(f"Status: {result_status}")
    if result_status != pywraplp.Solver.OPTIMAL:
        print("The problem does not have an optimal solution!")
        if result_status == pywraplp.Solver.FEASIBLE:
            print("A potentially suboptimal solution was found")
        else:
            print("The solver could not solve the problem.")
            return

    print("Solution:")
    print("Objective value =", objective.Value())
    print("x =", x_var.solution_value())
    print("y =", y_var.solution_value())

    print("Advanced usage:")
    print(f"Problem solved in {solver.wall_time():d} milliseconds")
    print(f"Problem solved in {solver.iterations():d} iterations")


if __name__ == "__main__":
    init.CppBridge.init_logging("basic_example.py")
    cpp_flags = init.CppFlags()
    cpp_flags.stderrthreshold = True
    cpp_flags.log_prefix = False
    init.CppBridge.set_flags(cpp_flags)
    main()

Menjalankan program

Anda dapat menjalankan program di atas sebagai berikut:

1. Salin dan tempel kode di atas ke dalam file baru dan simpan sebagai program.py.
2. Buka jendela perintah dan ubah ke direktori tempat Anda menyimpan program.py. Di command prompt, masukkan:

   python relative/path/to/program.py

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

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

Solution:
x =  1.0
y =  1.0

Contoh Python lainnya

Untuk contoh Python 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