lrsbuffer - Trực tuyến trên đám mây

CHƯƠNG TRÌNH:

TÊN

lrslib - Chuyển đổi giữa các tập hợp lại của khối đa diện lồi.

SYNOPSIS

lrs đầu vào.ine

lrs đầu vào.ine | lrsbuffer

lrsbourier tập tin.ine [tập tin ra]

dư thừa đầu vào.ine

MÔ TẢ

Một khối đa diện có thể được mô tả bằng một danh sách các bất đẳng thức (Đại diện H) hoặc như một danh sách
các đỉnh và các tia cực của nó (Đại diện V). lrs là một chương trình C chuyển đổi một
Biểu diễn H của một đa diện thành biểu diễn V của nó và ngược lại. Những vấn đề này
được biết đến tương ứng tại đỉnh đầu sự liệt kê và lồi vỏ tàu vấn đề.

Của Fukuda Câu Hỏi Thường Gặp trang[1] chứa phần giới thiệu chi tiết hơn về vấn đề, cùng với
nhiều mẹo hữu ích cho người dùng mới.

lrsbuffer có thể loại bỏ một số đầu ra trùng lặp. dư thừa tìm các bất bình đẳng dư thừa trong
đầu vào.

FILE M FORU ĐƠN

Các định dạng tệp được phát triển cùng với Komei Fukuda và tương thích với cdd[2.

Đầu vào cho lrs là biểu diễn H- hoặc V- của một đa giác.

tên
{dòng đại diện}
{tùy chọn}
{tuyến tính[3]}
bắt đầu
mn hợp lý
{ma trận đầu vào}
cuối
{tùy chọn}

tên là tên do người dùng cung cấp cho polytope. Nhận xét có thể xuất hiện trước khi bắt đầu hoặc
sau khi kết thúc, và để tránh việc diễn giải như một lựa chọn, nên bắt đầu bằng một
ký tự như "*" hoặc "#".

tên là tên do người dùng cung cấp cho polytope. đại diện hàng là một trong hai
"Biểu diễn chữ H" hoặc "Biểu diễn chữ V". Nếu bị bỏ qua, biểu diễn H được giả định. Các
hệ số đầu vào được đọc ở định dạng tự do và không được kiểm tra loại. Hệ số là
ngăn cách bởi khoảng trắng. m là số hàng và n là số cột của đầu vào
ma trận.

Đại diện H
Số nguyên m là số bất phương trình và số nguyên n là số chiều của
đầu vào +1. Một danh sách các bất đẳng thức chứa các hệ số của các bất đẳng thức có dạng

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

Bất đẳng thức này được nhập dưới dạng dòng

a0 a1 ... an-1

Các hệ số có thể được nhập dưới dạng số nguyên hoặc số hữu tỉ ở định dạng x / y.

Biểu diễn chữ V
Số nguyên m là số đỉnh và tia, số nguyên n là số chiều của
đầu vào +1. Mỗi đỉnh được cho dưới dạng

1 v0 v 1 ... vn-1

Mỗi tia được đưa ra dưới dạng

0 r0 r 1 ... rn-1

trong đó r0 r 1 ... rn-1 là một điểm trên tia.

Phải có ít nhất một đỉnh trong mỗi tệp. Đối với khối đa diện bị giới hạn sẽ không có
tia vào. Các hệ số có thể được nhập dưới dạng số nguyên hoặc số hữu tỉ ở định dạng x / y.

Chú thích cho cdd Người sử dụng: lrs về cơ bản sử dụng cùng một định dạng tệp như cdd. Các tệp được chuẩn bị cho
cdd nên hoạt động với ít hoặc không có sửa đổi. Lưu ý rằng biểu diễn chữ V
tương ứng với tùy chọn "thân tàu" trong cdd. Các tùy chọn dành riêng cho cdd có thể được để lại trong đầu vào
các tệp và sẽ bị bỏ qua bởi lrs. Lưu ý các tệp đầu vào cho lrs được đọc ở định dạng miễn phí,
sau dòng m n hợp lý, lrs sẽ tìm kiếm chính xác m * n số hữu tỉ hoặc số nguyên được phân tách
bởi khoảng trắng (trống, ký tự xuống dòng, tab, v.v.). lrs sẽ không "thả" thêm các cột
đầu vào nếu n nhỏ hơn số cột được cung cấp.

Cơ bản Các lựa chọn
Hầu hết tất cả các tùy chọn đều được đặt sau khi câu lệnh kết thúc, duy trì khả năng tương thích với cdd.
Trường hợp không đúng như vậy, nó sẽ được đề cập một cách rõ ràng.

cơ bản Tùy chọn này hướng dẫn lrs để liệt kê từng đỉnh (hoặc mặt) cho mỗi cơ sở của nó.
Đầu ra Sao chép[4].[5] Tùy chọn này thường được kết hợp với bệnh nhiễm trùng da (printcobasis).

ràng buộc x Sử dụng với biểu diễn H - cho lrs hoặc nash Hoặc tối đa hóa hoặc thu nhỏ
tùy chọn nên được chọn. x là số nguyên hoặc số hữu tỉ. Để tối đa hóa (tương ứng
tối thiểu hóa) cây tìm kiếm ngược bị cắt ngắn bất cứ khi nào giá trị mục tiêu hiện tại
nhỏ hơn (tương ứng nhiều hơn) so với x.

bộ nhớ cache nlrs lưu trữ n từ điển mới nhất trong cây tìm kiếm ngược. Điều này tăng tốc độ
bước backtracking, nhưng yêu cầu nhiều bộ nhớ hơn.

gỡ lỗi khởi đầu endbasisIn ra dấu vết khó hiểu nhưng chi tiết, từ điển, v.v.
bắt đầu ở # B = startbasis và kết thúc ở # B = endbasis. gỡ lỗi 0 0 cung cấp một hoàn thành
theo dõi.

chữ số n đặt trước các bắt đầu tuyên bố n là số chữ số thập phân tối đa là
đã sử dụng. Nếu vượt quá mức này, chương trình sẽ kết thúc bằng một thông báo (thường có thể là
khởi động lại). Giá trị mặc định được đặt thành khoảng 100 chữ số. Khi kết thúc một cuộc chạy, một thông báo là
đưa ra thông báo cho người dùng về kích thước số nguyên tối đa gặp phải. Điều này có thể được sử dụng để
tối ưu hóa việc sử dụng bộ nhớ và tốc độ trong các lần chạy tiếp theo (ví dụ: nếu thực hiện ước tính).

nhiễu loạn kép Nếu lrs được thực thi với tùy chọn tối đa hóa hoặc thu nhỏ, thì tìm kiếm ngược lại
cây có gốc ở đỉnh tối ưu cho chức năng này.
đỉnh, đầu ra thường sẽ không đầy đủ. Tùy chọn này gây ra một sự xáo trộn nhỏ đối với
mục tiêu để tránh điều này. Một thông báo cảnh báo được đưa ra nếu từ điển bắt đầu là kép
thoái hóa.

dự toán k Ước tính kích thước đầu ra. Được sử dụng kết hợp với maxdepth - xem
Ước lượng.[6]

hình học // Chỉ tùy chọn biểu diễn H hoặc voronoi // Với tùy chọn này, mỗi tia là
được in cùng với đỉnh mà nó là sự cố. Để biết thêm thông tin, hãy xem
tia hình học trong Gợi ý và Nhận xét[5].

tỷ lệTùy chọn này tự động bật bệnh giun chỉ , vì vậy hãy xem bên dưới để biết
mô tả của tùy chọn này đầu tiên. Có thể được sử dụng với printcobasis n. (Động từ 4.2b) .PP Đối với
biểu diễn đầu vào H, chỉ số của tất cả các bất đẳng thức đầu vào có chứa đỉnh / tia
sắp được xuất. Đối với một mặt đơn giản, không có đầu ra mới, vì các chỉ số này
đã được liệt kê. Nếu không, các bất đẳng thức chặt chẽ bổ sung được liệt kê sau dấu hai chấm.
.PP Đối với biểu diễn chữ V đầu vào, chỉ số của tất cả các đỉnh / tia đầu vào nằm trên mặt
sắp được xuất. Dấu sao cho biết rằng đỉnh này cũng nằm trong
cobasis, nhưng không được chứa trong các khía cạnh. Nó phát sinh do hoạt động nâng hạ được sử dụng
với các biểu diễn chữ V đầu vào.

#tỷ lệ mắc bệnhGiống như printcobasis. Bao gồm để tương thích với cdd.

tuyến tính k i1i2 i hữu ích. Cảm ơn ! ikĐầu vào chứa k tuyến tính trong các hàng i1i2i hữu ích. Cảm ơn ! ikcủa
tập tin đầu vào là các phương trình. Nhìn thấy Các tuyến tính.[3]

độ sâu tối đa k Tìm kiếm sẽ bị cắt ngắn ở độ sâu k. Tất cả các căn cứ có độ sâu nhỏ hơn hoặc
bằng k sẽ được tính. k là một số nguyên không âm và tùy chọn này được sử dụng cho
ước tính - xem Ước lượng.[6]Chú thích: Đối với biểu diễn H, tia ở độ sâu k sẽ không
đã báo cáo. Đối với biểu diễn chữ V, các khía cạnh ở độ sâu k sẽ không được báo cáo.

tối đa hóa a0 a1 ... an-1 // Chỉ biểu diễn H //

giảm thiểu a0 a1 ... an-1 // Chỉ biểu diễn H //

Nếu được sử dụng với lrs, đỉnh bắt đầu tối đa hóa (hoặc tối thiểu hóa) hàm a0 + a1x1 + ...
+ an-1 xn-1. Có thể cần tùy chọn tần số kép để tránh suy biến kép.
Equilibria và tuyến tính Lập trình[7]

Đầu ra tối đa n Giới hạn số dòng đầu ra được tạo ra (đỉnh + tia hoặc mặt) cho n

suy nghĩ k Bẻ khóa ngược sẽ kết thúc ở độ sâu k, đối với số nguyên không âm ka. Cái này
có thể được sử dụng để chạy tìm kiếm ngược trên các cây con dưới dạng các quy trình riêng biệt, ví dụ: trong một
môi trường điện toán phân tán.

không âm // Tùy chọn này phải xuất hiện trước câu lệnh begin // // Chỉ biểu diễn H
// Lỗi: Chỉ có thể được sử dụng nếu điểm gốc là một đỉnh của hình đa diện Đối với các vấn đề trong đó
đầu vào là biểu diễn H có dạng b + Ax> = 0, x> = 0 (tức là tất cả các biến
không tiêu cực, tất cả các ràng buộc bất bình đẳng) không nhất thiết phải cung cấp cho
ràng buộc rõ ràng nếu tùy chọn không âm được sử dụng. Tùy chọn này không thể được sử dụng cho
Biểu diễn chữ V hoặc với tùy chọn độ tuyến tính (trong trường hợp đó, độ tuyến tính sẽ là
được coi là bất bình đẳng). Tùy chọn này có thể được sử dụng với dự phòng, nhưng ngụ ý
các ràng buộc không mang tính chất không tự kiểm tra tính dư thừa. Để kiểm tra mọi thứ nó
là cần thiết để nhập các ràng buộc không âm một cách rõ ràng trong tệp đầu vào. (Trong Ver
4.1, điểm gốc phải là một đỉnh).

bệnh giun chỉ k;Được sửa đổi trong lrs 4.0 Mọi cobasis k'th được in. Nếu k bị bỏ qua,
cobasis được in cho mỗi đỉnh / tia / mặt được xuất ra. Về lâu dài, nó rất hữu ích
để thỉnh thoảng in cobasis để chương trình có thể được khởi động lại nếu cần.
Biểu diễn chữ H: Nếu đầu vào là biểu diễn chữ H thì cobasis là danh sách các chỉ số của
bất đẳng thức từ tệp đầu vào xác định đỉnh hoặc tia hiện tại. Xem tùy chọn
tỷ lệ ở trên để biết thêm thông tin. Đối với cá đuối, một cobasis cũng được in. Trong trường hợp này
cobasis là hình chóp của đỉnh mà từ đó tia phát ra. Một trong những chỉ số
được gắn dấu sao, điều này cho biết sự bất bình đẳng sẽ được loại bỏ khỏi cobasis để xác định
cá đuối. Ngoài ra, nếu cơ bảntùy chọn được sử dụng, tất cả các lõi sẽ được in ra.
Biểu diễn chữ V: Nếu đầu vào là biểu diễn chữ V, cobasis là danh sách đầu vào
đỉnh / tia xác định mặt hiện tại. Xem tùy chọn tỷ lệ ở trên để biết thêm
thông tin. Để bắt đầu lrs từ khía cạnh này, tất cả 4 chỉ số phải được cung cấp theo thứ tự này
(bỏ dấu *).

màu đen Mới trong Phiên bản 4.2; // Sử dụng với biểu diễn H // lrs in ra danh sách
chỉ số của các bất đẳng thức đầu vào được thỏa mãn nghiêm ngặt cho đỉnh hiện tại, tức là.
biến slack tương ứng là số dương. Nếu không âm được đặt, danh sách cũng sẽ
bao gồm các chỉ số n + i cho mỗi biến quyết định xi là số dương. dự án Được sử dụng bởi
lrsbourier[8] thôi.

khởi động lại V# R# B# chiều sâu {khía cạnh #s or đỉnh / tia #s} Đã sửa đổi trong lrs4.0 lrs có thể
bắt đầu lại từ bất kỳ cobasis nào đã biết. Việc tính toán sẽ tiến hành kết thúc bình thường. Tất cả các
thông tin được chứa trong đầu ra từ một bệnh giun chỉ Lựa chọn. Các gọi món of
các chỉ số is rất quan trọng, nhập chúng chính xác như chúng xuất hiện trong đầu ra từ
trước đó đã bỏ chạy.

khởi đầu i1i2i hữu ích. Cảm ơn ! trong 1 Điều này cho phép người dùng chỉ định một cobasis đã biết cho
bắt đầu tìm kiếm ngược lại. i1i2i hữu ích. Cảm ơn ! trong 1 là một danh sách các bất bình đẳng (đối với
Biểu diễn H) hoặc các đỉnh / tia (đối với biểu diễn V) xác định một cobasis. Nếu nó là
không hợp lệ hoặc tùy chọn này không được chỉ định, lrs sẽ tìm thấy cobasis bắt đầu của riêng nó. Các
cây tìm kiếm ngược bị cắt bớt (cắt bớt) bất cứ khi nào gặp đỉnh mới. Lưu ý: Cái này
lưu ý không nhất thiết phải tạo ra tập hợp tất cả các đỉnh liền kề với đỉnh tối ưu trong
khối đa diện, nhưng chỉ là một tập hợp con của chúng.

dài dòngIn thông tin chi tiết hơn một chút về cuộc chạy.

khối lượng // Chỉ biểu diễn chữ V // Tính âm lượng - xem phần Khối lượng Tính toán.[9]

voronoi // Chỉ biểu diễn chữ V - đặt ngay sau câu lệnh kết thúc // Tính toán
Sơ đồ Voronoi - xem phần Voronoi Các sơ đồ.[10]

GHI CHÚ

1. Trang câu hỏi thường gặp
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. tuyến tính
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # Tuyến tính

4. Nhân bản đầu ra
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # Output% 20Duplication

5.
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # Gợi ý% 20 và% 20Comments

6. Ước tính.
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # Ước tính

7. Lập trình tuyến tính
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # Tuyến tính% 20 Lập trình

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

9. Tính toán khối lượng.
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # Khối lượng% 20 Tính toán

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

Sử dụng lrsbuffer trực tuyến bằng các dịch vụ onworks.net