Nilai Absolut dalam Kendala Linear

12

Saya memiliki masalah pengoptimalan berikut ini di mana saya memiliki nilai absolut dalam batasan saya:

xRnf0,f1,,fmn

minf0Txs.t.|f1Tx||f2Tx||fmTx|

Saya tahu bahwa ruang yang layak tidak akan cembung dan saya mungkin akan membutuhkan MILP untuk menyelesaikan masalah. Saya mencari paling sedikit jumlah variabel biner yang saya perlukan dan pengaturan yang akan memecahkan masalah.

Berurusan dengan nilai absolut umumnya mudah ketika hanya satu sisi ketidaksetaraan memiliki nilai absolut (http://lpsolve.sourceforge.net/5.1/absolute.htm); Namun kasus ini tampaknya lebih rumit.

Terima kasih sebelumnya.

Mohammad Fawaz
sumber

Jawaban:

5

Cara termudah adalah dengan menambahkan nilai biner , dan memecahkanmsi0,1

minf0Txs.t.0(2si1)fiTx(2si+11)fi+1Txi

Saya berpikir bahwa (1) tidak ada yang secara substansial lebih cepat ada atau (2) ada trik khusus untuk dirumuskan kembali sebagai program cembung. Mungkin (1).

Geoffrey Irving
sumber