Dalam Pemrograman Kendala, apakah ada model yang memperhitungkan jumlah perubahan variabel?

10

Pertimbangkan model CSP di mana mengubah nilai variabel tertentu itu mahal. Apakah ada pekerjaan di mana fungsi objektif juga mempertimbangkan jumlah perubahan nilai variabel selama proses pencarian?

Contoh: Variabel mahal-untuk-perubahan mungkin ada dalam kendali beberapa agen lain dan ada beberapa biaya tambahan yang melibatkan agen tersebut untuk mengubah variabel. Contoh lain: Variabel berpartisipasi dalam salah satu kendala, dan kepuasan kendala ini melibatkan memanggil fungsi yang mahal (seperti, simulator), misalnya adalah kendala, dan adalah mahal- untuk menghitung fungsi. Oleh karena itu, dan adalah variabel mahal untuk diubah.z=f(x,y)fxy

algorithms constraint-programming ya
sumber
1
Fungsi obyektif berbicara tentang nilai akhir CSP dan tidak mengetahui proses pencarian. Jadi, dalam formulasi standar, perubahan dalam variabel tersebut tidak terpapar dengan model CSP. Beberapa pemecah masalah, seperti Choco, memberikan heuristik untuk memandu proses pencarian. Beberapa di antaranya bahkan mungkin ditentukan oleh pengguna. Mungkin itulah tempat untuk mengubah cara pencarian dilakukan.
Dave Clarke
1
Tetapi mengapa fungsi objektif mencerminkan betapa mahalnya solusi tersebut? Jika Anda tidak membandingkan solusi dengan seberapa berguna mereka di domain masalah setelah itu? Atau apakah waktu-untuk-solusi bagian dari masalah dunia nyata?
Raphael
1
Kedengarannya seperti Anda berada dalam pengaturan kepuasan kendala terdistribusi dan sepertinya Anda mencari heuristik.
Dave Clarke

Jawaban:

4

Sepertinya Anda menginginkan teknik pengoptimalan yang hemat biaya (sadar biaya, dianggarkan) . Meminimalkan dua nilai (misalnya solusi tujuan Anda dan biaya operasi pada dan ) adalah masalah optimisasi multikriteria , dan itu cenderung sangat sulit untuk dipecahkan. Pendekatan umum adalah menentukan anggaran untuk biaya maksimum yang diijinkan dan kemudian meminimalkan fungsi tujuan sehubungan dengan . Formulasi ini cenderung cocok dengan kerangka kerja yang ada sebagai kendala tambahan. Tentu saja, menentukan fungsi biaya dan anggaran yang diizinkan sedemikian rupa sehingga Anda mendapatkan solusi yang berarti bisa sulit - ini akan tergantung pada masalah spesifik yang Anda coba selesaikan.xycosts(x,y)≤Budget

Nick
sumber