lrs - Online di Awan

PROGRAM:

NAMA

lrslib - Mengonversi antara representasi polihedra cembung.

RINGKASAN

lrs masukan.ine

lrs masukan.ine | lrsbuffer

lrsfourier file.ine [file keluar]

berlebihan masukan.ine

DESKRIPSI

Sebuah polihedron dapat digambarkan dengan daftar ketidaksetaraan (H-representasi) atau menurut daftar
dari simpul dan sinar ekstremnya (V-representasi). lrs adalah program C yang mengubah a
Representasi H dari polihedron ke representasi V-nya, dan sebaliknya. Masalah-masalah ini
diketahui masing-masing pada puncak pencacahan dan cembung lambung kapal masalah.

Fukuda FAQ halaman[1] berisi pengantar masalah yang lebih rinci, bersama dengan
banyak tips berguna untuk pengguna baru.

lrsbuffer dapat menghapus beberapa output duplikat. berlebihan menemukan ketidaksetaraan yang berlebihan dalam
memasukkan.

FILE FORMAT

Format file dikembangkan bersama dengan Komei Fukuda dan kompatibel dengan cdd[2].

Masukan untuk lrs adalah representasi H- atau V- dari politop.

nama
{garis representasi}
{pilihan}
{linearitas[3]}
mulai
mn rasional
{matriks masukan}
akhir
{pilihan}

nama adalah nama yang diberikan pengguna untuk polytope. Komentar mungkin muncul sebelum dimulai atau
setelah akhir, dan untuk menghindari interpretasi sebagai pilihan, harus dimulai dengan yang khusus
karakter seperti "*" atau "#".

nama adalah nama yang diberikan pengguna untuk polytope. perwakilan line juga
"H-representasi" atau "V-representasi". Jika dihilangkan, representasi-H diasumsikan. NS
koefisien input dibaca dalam format bebas, dan tidak diperiksa jenisnya. Koefisiennya adalah
dipisahkan oleh spasi putih. m adalah jumlah baris dan n jumlah kolom input
matriks.

H-representasi
Bilangan bulat m adalah jumlah pertidaksamaan, dan bilangan bulat n adalah dimensi dari
masukan +1. Daftar pertidaksamaan berisi koefisien pertidaksamaan berbentuk

a0 + a1x1+ ... + an-1 xn-1 >= 0.

Pertidaksamaan ini dimasukkan sebagai garis

a0 a1... dan-1

Koefisien dapat dimasukkan sebagai bilangan bulat atau rasional dalam format x/y.

V-representasi
Bilangan bulat m adalah jumlah simpul dan sinar, dan bilangan bulat n adalah dimensi dari
masukan +1. Setiap simpul diberikan dalam bentuk

1 v0 v 1... vn-1

Setiap sinar diberikan dalam bentuk

0 r0 r 1...rn-1

di mana r0 r 1... rn-1 adalah titik pada sinar.

Harus ada setidaknya satu simpul di setiap file. Untuk polihedra berbatas tidak akan ada
sinar masuk. Koefisien dapat dimasukkan sebagai bilangan bulat atau rasional dalam format x/y.

Note untuk cdd Pengguna: lrs pada dasarnya menggunakan format file yang sama dengan cdd. File disiapkan untuk
cdd harus bekerja dengan sedikit atau tanpa modifikasi. Perhatikan bahwa representasi-V
sesuai dengan opsi "lambung" di cdd. Opsi khusus untuk cdd dapat ditinggalkan di input
file dan akan diabaikan oleh lrs. Perhatikan file input untuk lrs dibaca dalam format bebas,
setelah garis m n rasional, lrs akan mencari tepat m*n rasional atau bilangan bulat yang dipisahkan
dengan spasi putih (kosong, carriage return, tab, dll.). lrs tidak akan "menjatuhkan" kolom tambahan dari
masukan jika n kurang dari jumlah kolom yang disediakan.

Dasar Opsi
Hampir semua opsi ditempatkan setelah pernyataan akhir, menjaga kompatibilitas dengan cdd.
Jika hal ini tidak terjadi, maka akan disebutkan secara eksplisit.

semua basis Opsi ini menginstruksikan lrs untuk membuat daftar setiap simpul (atau segi) untuk setiap basisnya.
Keluaran Duplikasi[4].[5] Opsi ini sering dikombinasikan dengan printcobasis.

terikat x Gunakan dengan representasi-H - untuk lrs atau nash Baik maksimalkan atau minimalkan
pilihan harus dipilih. x adalah bilangan bulat atau rasional. Untuk memaksimalkan (mis.
minimisasi) pohon pencarian terbalik terpotong setiap kali nilai tujuan saat ini
kurang (resp. lebih) dari x.

Cache nlrs menyimpan kamus n terbaru di pohon pencarian terbalik. Ini mempercepat
langkah mundur, tetapi membutuhkan lebih banyak memori.

men-debug dasar awal dasar akhirCetak jejak, kamus, dll yang samar namun detail.
dimulai dari #B=dasar awal dan berakhir di #B=dasar akhir. men-debug 0 0 memberikan lengkap
jejak.

digit n ditempatkan sebelum itu mulai pernyataan n adalah jumlah maksimum digit desimal menjadi
digunakan. Jika ini terlampaui, program akan diakhiri dengan sebuah pesan (biasanya dapat berupa
dimulai ulang). Standarnya diatur ke sekitar 100 digit. Di akhir lari sebuah pesan adalah
diberikan menginformasikan pengguna tentang ukuran bilangan bulat maksimum yang ditemui. Ini dapat digunakan untuk
mengoptimalkan penggunaan memori dan kecepatan pada proses selanjutnya (jika melakukan estimasi misalnya).

gangguan ganda Jika lrs dijalankan dengan opsi maksimalkan atau minimalkan, pencarian terbalik
pohon berakar pada titik optimal untuk fungsi ini. Jika ada banyak optimal
simpul, output sering kali tidak lengkap. Opsi ini memberikan sedikit gangguan pada
tujuan untuk menghindari hal ini. Pesan peringatan diberikan jika kamus awal adalah ganda
merosot.

perkiraan k Perkirakan ukuran keluaran. Digunakan bersama dengan maxdepth - lihat
Perkiraan.[6]

geometris // Hanya opsi representasi-H atau voronoi // Dengan opsi ini, setiap sinar adalah
dicetak bersama-sama dengan vertex yang insidennya. Untuk informasi lebih lanjut lihat
Sinar Geometris di Petunjuk dan komentar[5].

insidensiOpsi ini secara otomatis aktif printcobasi , jadi lihat di bawah untuk
deskripsi opsi ini terlebih dahulu. Dapat digunakan dengan printcobasis n. (Ver 4.2b) .PP Untuk
masukan representasi-H, indeks dari semua pertidaksamaan masukan yang mengandung simpul/sinar yang
akan keluar. Untuk wajah sederhana, tidak ada output baru, karena indeks ini
sudah terdaftar. Jika tidak, ketidaksetaraan ketat tambahan dicantumkan setelah titik dua.
.PP Untuk representasi V masukan, indeks dari semua simpul/sinar masukan yang terletak pada segi
yang akan dikeluarkan. Indeks berbintang menunjukkan bahwa simpul ini juga berada di
cobasis, tetapi tidak terkandung dalam segi. Itu muncul karena operasi pengangkatan yang digunakan
dengan input V-representasi.

#insidensiSama seperti printcobasi. Termasuk untuk kompatibilitas dengan CD

linearitas k i1i2 i ... ikInput berisi k linearitas dalam baris i1i2i ... ikdari
file input adalah persamaan. Lihat Linearitas.[3]

kedalaman maksimum k Pencarian akan terpotong pada kedalaman k. Semua pangkalan dengan kedalaman kurang dari or
sama dengan k akan dihitung. k adalah bilangan bulat non-negatif, dan opsi ini digunakan untuk
perkiraan - lihat Perkiraan.[6]Note: Untuk representasi H, sinar pada kedalaman k tidak akan
dilaporkan. Untuk representasi V, faset pada kedalaman k tidak akan dilaporkan.

memaksimalkan a0 a1 ... sebuah-1 // Hanya representasi-H //

memperkecil a0 a1 ... sebuah-1 // Hanya representasi-H //

Jika digunakan dengan lrs, simpul awal memaksimalkan (atau meminimalkan) fungsi a0 + a1x1+ ...
+ an-1 xn-1.Opsi dualperturb mungkin diperlukan untuk menghindari degenerasi ganda.Lihat Nash
keseimbangan dan Linear Pemrograman[7]

keluaran maksimal n Membatasi jumlah jalur keluaran yang dihasilkan (baik simpul+sinar atau segi) hingga n

kedalaman kecil k Backtracking akan dihentikan pada kedalaman k, untuk ka bilangan bulat non-negatif. Ini
dapat digunakan untuk menjalankan pencarian terbalik pada subpohon sebagai proses terpisah, misalnya dalam a
lingkungan komputasi terdistribusi.

tidak negatif // Opsi ini harus ada sebelum pernyataan awal// //representasi-H saja
// Bug: Hanya dapat digunakan jika titik asal adalah titik dari polihedron Untuk masalah dimana
inputnya adalah representasi-H dari bentuk b+Ax>=0, x>=0 (yaitu semua variabel
non-negatif, semua kendala pertidaksamaan) tidak perlu memberikan non-negatif
kendala secara eksplisit jika opsi nonnegatif digunakan. Opsi ini tidak dapat digunakan untuk
V-representasi, atau dengan opsi linearitas (dalam hal ini linearitas akan menjadi
diperlakukan sebagai ketidaksetaraan). Opsi ini dapat digunakan dengan redund , tetapi tersirat
kendala nonnegatif tidak diuji sendiri untuk redundansi. Untuk menguji semuanya itu
diperlukan untuk memasukkan batasan nonnegatif secara eksplisit dalam file input. (Dalam Ver
4.1, asal harus berupa simpul).

printcobasi k;Dimodifikasi dalam lrs 4.0 Setiap cobasis ke-k dicetak. Jika k dihilangkan, maka
cobasis dicetak untuk setiap vertex/ray/facet yang dikeluarkan. Untuk jangka panjang itu berguna
untuk mencetak cobasis sesekali agar program dapat direstart jika diperlukan.
H-representasi: Jika inputnya adalah representasi-H, cobasis adalah daftar indeks dari
ketidaksetaraan dari file input yang menentukan titik atau sinar saat ini. Lihat opsi
insidensi di atas untuk informasi lebih lanjut. Untuk sinar, cobasis juga dicetak. Pada kasus ini
cobasis adalah cobasis dari vertex dari mana sinar berasal. Salah satu indeks
berbintang, ini menunjukkan ketidaksetaraan yang akan dijatuhkan dari cobasis untuk menentukan
sinar. Sebagai alternatif, jika semua basispilihan digunakan, semua cobases akan dicetak.
V-representasi: Jika input adalah representasi-V, cobasis adalah daftar input
simpul / sinar yang mendefinisikan faset saat ini. Lihat opsi insidensi di atas untuk lebih
informasi. Untuk memulai lrs dari segi ini semua 4 indeks harus diberikan dalam urutan ini
(hilangkan *).

kendur cetak Baru di Ver 4.2 ; // Gunakan dengan representasi-H // lrs mencetak daftar
indeks ketidaksetaraan input yang dipenuhi secara ketat untuk simpul saat ini, yaitu.
variabel kendur yang sesuai adalah positif. Jika nonnegatif disetel, daftar juga akan
sertakan indeks n+i untuk setiap variabel keputusan xi yang bernilai positif. proyek Digunakan oleh
lrsfourier[8] saja.

Restart V# R# B# kedalaman {segi #s or simpul/sinar #s} Dimodifikasi di lrs4.0 lrs dapat
dimulai kembali dari cobasis yang diketahui. Perhitungan akan dilanjutkan ke terminasi normal. Semua
dari informasi yang terkandung dalam output dari a printcobasi pilihan. Itu urutan of
itu indeks is sangat penting, masukkan mereka persis seperti yang muncul di output dari
dijalankan sebelumnya dibatalkan.

mulaicobasis i1i2i ... dalam-1 Ini memungkinkan pengguna untuk menentukan cobasis yang diketahui untuk
memulai pencarian terbalik. i1i2i ... dalam-1 adalah daftar pertidaksamaan (untuk
H-representasi) atau simpul/sinar (untuk V-representasi) yang mendefinisikan cobasis. Jika memang
tidak valid, atau opsi ini tidak ditentukan, lrs akan menemukan cobasis awal sendiri. NS
pohon pencarian terbalik dipotong (dipangkas) setiap kali sebuah simpul baru ditemukan. Catatan: Ini
not tentu menghasilkan himpunan semua simpul yang berdekatan dengan simpul optimal di
polihedron, tetapi hanya sebagian dari mereka.

bertele-teleCetak informasi yang sedikit lebih detail tentang lari.

volume // Hanya representasi-V // Hitung volume - lihat bagian Volume Komputasi.[9]

gagak // Hanya representasi-V - tempatkan segera setelah pernyataan akhir // Hitung
Diagram Voronoi - lihat bagian gagak Diagram.[10]

CATATAN

1. halaman FAQ
http://www.ifor.math.ethz.ch/staff/fukuda/polyfaq/polyfaq.html

2. CDD
http://www.cs.mcgill.ca/%7Efukuda/soft/cdd_home/cdd.html

3. linearitas
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Linearitas

4. Duplikasi Keluaran
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Output%20Duplikasi

5.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Hints%20and%20Komentar

6. Estimasi.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Estimasi

7. Pemrograman Linier
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Linear%20Pemrograman

8. lrsfourier
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#fourier

9. Perhitungan Volume.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Volume%20Komputasi

10. Diagram Voronoi.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Voronoi%20Diagram

Gunakan lrs online menggunakan layanan onworks.net