idol

Idol - Kerangka kerja C ++ untuk optimasi

Idol adalah perpustakaan C ++ untuk optimasi matematika dan pengambilan keputusan yang kompleks.

Ini dirancang untuk membantu Anda membangun algoritma baru dengan mudah untuk menyelesaikan masalah yang lebih menantang. Ini adalah alat serbaguna dan kuat yang dapat digunakan untuk menyelesaikan berbagai masalah optimasi, termasuk pemrograman linear campuran-integer (MILP), masalah dibatasi kuadratik (MIQCQP dan MIQP), masalah bilevel (BO), masalah optimasi yang kuat (RO dan ARO) dan banyak lagi.

• Dokumentasi
• Menggunakan Idol untuk Penelitian?
• Contoh
  • Cabang dan harga
  • Masalah bilevel (menggunakan koin-or/mibs)
• Fitur yang diimplementasikan
  • Cabang dan terikat
  • Generasi kolom dan cabang dan harga
  • Pemecah eksternal

Dokumentasi

Kunjungi dokumentasi online kami.

Menggunakan Idol untuk Penelitian?

Jika Anda memilih Idol di salah satu proyek penelitian Anda dan menghadapi beberapa masalah, silakan hubungi kami di Lefebvre (at) uni-trier.de.

Contoh

Cabang dan harga

Lihatlah betapa mudahnya menerapkan algoritma cabang dan harga menggunakan Idol.

 const auto [model, decomposition] = create_model(); // Creates the model with an annotation for automatic decomposition

const auto sub_problem_specifications = 
        DantzigWolfe::SubProblem ()
          .add_optimizer(Gurobi()); // Each sub-problem will be solved by Gurobi

const auto column_generation = 
        DantzigWolfeDecomposition (decomposition)
          .with_master_optimizer(Gurobi::ContinuousRelaxation()) // The master problem will be solved by Gurobi
          .with_default_sub_problem_spec(sub_problem_specifications);

const auto branch_and_bound =
        BranchAndBound ()
          .with_node_selection_rule(BestBound()) // Nodes will be selected by the "best-bound" rule
          .with_branching_rule(MostInfeasible()) // Variables will be selected by the "most-fractional" rule
          .with_log_level(Info, Blue);

const auto branch_and_price = branch_and_bound + column_generation; // Embed the column generation in the Branch-and-Bound algorithm

model.use(branch_and_price);

model.optimize();

Masalah bilevel (menggunakan MIBS)

Di sini, Idol menggunakan koin solver eksternal atau/MIB untuk menyelesaikan masalah optimisasi bilevel dengan level bawah integer.

 /*
 This example is taken from "The Mixed Integer Linear Bilevel Programming Problem" (Moore and Bard, 1990).

    min -1 x + -10 y
    s.t.

    y in argmin { y :
        -25 x + 20 y <= 30,
        1 x + 2 y <= 10,
        2 x + -1 y <= 15,
        2 x + 10 y >= 15,
        y >= 0 and integer.
    }
    x >= 0 and integer.

 */

Env env;

// Define High Point Relaxation
Model high_point_relaxation (env);

auto x = high_point_relaxation.add_var( 0 , Inf, Integer, " x " );
auto y = high_point_relaxation.add_var( 0 , Inf, Integer, " y " );

high_point_relaxation.set_obj_expr(-x - 10 * y);
auto follower_c1 = high_point_relaxation.add_ctr(- 25 * x + 20 * y <= 30 );
auto follower_c2 = high_point_relaxation.add_ctr(x + 2 * y <= 10 );
auto follower_c3 = high_point_relaxation.add_ctr( 2 * x - y <= 15 );
auto follower_c4 = high_point_relaxation.add_ctr( 2 * x + 10 * y >= 15 );

// Prepare bilevel description
Bilevel::LowerLevelDescription description (env);
description.set_follower_obj_expr(y);
description.set_follower_var(y);
description.set_follower_ctr(follower_c1);
description.set_follower_ctr(follower_c2);
description.set_follower_ctr(follower_c3);
description.set_follower_ctr(follower_c4);

// Use coin-or/MibS as external solver
high_point_relaxation.use(Bilevel::MibS(description));

// Optimize and print solution
high_point_relaxation.optimize();

std::cout << high_point_relaxation.get_status() << std::endl;
std::cout << high_point_relaxation.get_reason() << std::endl;
std::cout << save_primal(high_point_relaxation) << std::endl;

Idol juga dapat dihubungkan dengan root untuk memantau kemajuan algoritma Anda. Misalnya, berikut adalah tangkapan layar pemantauan MIBS untuk contoh bilevel.

Fitur yang diimplementasikan

Optimasi campuran-integer

Pemecah eksternal

Idol dapat digunakan sebagai antarmuka terpadu untuk beberapa pemecah open-source atau komersial seperti

• Gurobi
• Mosek
• GLPK
• Tertinggi
• Koin-or/OSI-> CPLEX, Symphony, CBC

Cabang dan terikat

• Aturan Seleksi Node: Terikat Terbaik, Terikat Terburuk, Kedalaman Pertama, Perkiraan Terbaik, Luas Pertama.
• Aturan percabangan (untuk percabangan variabel): Biaya semu, percabangan yang kuat (dengan fase), paling tidak layak, paling tidak layak, pertama ditemukan, acak secara seragam.
• Subtree Exploration
• Heuristik (untuk percabangan variabel): lingkungan pembulatan sederhana dan santai, bercabang lokal
• Callbacks: Pemotongan Pengguna, Pemotongan Malas

Generasi kolom dan cabang dan harga

• Reformulasi Dantzig-Wolfe Otomatis
• Tersedia bercabang lembut dan keras (yaitu, bercabang pada master atau sub-masalah)
• Stabilisasi oleh Dual Price Smoothing: Goldges (1997), Neame (2000)
• Dapat memecahkan sub-masalah secara paralel
• Mendukung heuristik harga
• Heuristik: Integer Master

Optimalisasi Bilevel

• Idol dapat menyelesaikan masalah bilevel campuran-integer optimis menggunakan koin solver eksternal atau/MIB.

Optimalisasi Kuat Dua Tahap

Generasi Kolom-dan-Konstruksi (CCG)

• Implementasi generik dari algoritma CCG untuk masalah optimasi yang kuat yang dapat disesuaikan.
• Stabilisasi wilayah kepercayaan untuk masalah dengan keputusan tahap pertama biner.
• Masalah Pemisahan (Max-min) diselesaikan oleh pemecah bilevel.

Benchmark

• Benchmark untuk implementasi cabang dan harga tersedia untuk masalah penugasan umum.
• Benchmark untuk implementasi cabang-dan-terikat tersedia untuk masalah Knapsack.

Ini adalah profil kinerja yang dihitung menurut Dolan, E., Moré, J. Benchmarking Optimization Software dengan profil kinerja. Matematika. Program. 91, 201–213 (2002) https://doi.org/10.1007/s101070100263.

Aneka ragam

Versionning sesuai dengan Semantic Versionning 2.0.0.