Решение технико-экономического обоснования LP с использованием CGAL

Можем ли мы решить проблему выполнимости линейного программирования формы, указанной ниже, с помощью CGAL (если нет, предложите альтернативы):

v.x_a > c и,

v.x_b = c

где _3 _, _ 4 _, _ 5 _, _ 6_ - векторные, векторные, векторные и скалярные значения соответственно. Я хочу найти кортеж (v,c) для данного набора x (x_a и x_b являются элементами x), который удовлетворяет этому неравенству.

Я видел документацию, но допустимая форма имеет тип Ax(relation operator)b, где relation operator может быть> =, ‹= или =, где A и b известны, а x неизвестно, но мое требование противоположное, то есть у меня есть x, но я хочу определить, существует ли кортеж (A,b), удовлетворяющий неравенству.

Контекст: я пытаюсь реализовать генератор трехмерной сетки, для которого мне нужно проверить, является ли край (соединяющий две трехмерные вершины) Делоне. Ребро Делоне определяется как: Ребро - это Делоне, если существует описанная сфера его конечных точек, не содержащая никаких других вершин внутри.

Мой вопрос основан на подходе, описанном здесь


algorithm cgal linear-programming
person Pranav    schedule 20.05.2014    source источник
comment
Разве неравенство не является тривиальным, если вы выбираете v = c = 0? Или даже просто c = -infinity?   -  person Niklas B.    schedule 20.05.2014
comment
Что ж, я думаю, в контексте алгоритма Дэвида Эппштейна у вас есть дополнительные ограничения v != 0 и c = v.x для конкретного x из набора   -  person Niklas B.    schedule 20.05.2014
comment
@NiklasB. Спасибо, я обновил вопрос соответствующим образом.   -  person Pranav    schedule 20.05.2014
comment
Есть еще тривиальное решение v=1; c=-inf. Вам следует обновить вопрос, чтобы устранить двусмысленность   -  person Niklas B.    schedule 20.05.2014

Ответы (1)


arrow_upward
2
arrow_downward

Согласно конструкции, которую Дэвид Эппштейн описывает в связанном вопросе, i и j фиксированы, и у нас есть дополнительное ограничение v.xi = v.xj = c. Итак, проблема становится:

Найдите вектор v != 0 такой, что v.xk >= v.xi для всех k и v.xi = v.xj.

Это можно преобразовать в

Найдите вектор v != 0 такой, что (xk - xi).v >= 0 для всех k, (xi - xj).v >= 0 и -(xi - xj).v >= 0

Определив A как матрицу со строками xk - xi для всех k, xi - xj и xj - xi, мы получаем

Найдите вектор v != 0 такой, что Av >= 0

который имеет нужную вам форму. Вы можете применить v != 0 путем перебора ненулевого компонента. Для каждого компонента i и, пытаясь добавить условие vi >= 1 или vi <= -1 и проверить получившуюся систему на разрешимость. Поскольку вектор нормали к плоскости можно масштабировать произвольно, существует решение, если любая из результирующих программ разрешима (их 2d, если d - размерность v).

person Niklas B.    schedule 20.05.2014
comment
Я думаю, что Av>=0; v!=0 кажется более полным. - person Pranav; 21.05.2014
comment
@Pranav Я просто использую определение Эппштейна, не более или менее. Одно из условий состоит в том, что v.xi = v.xj = c согласно его описанию. Это означает, что две точки, соответствующие xi и xj, фактически лежат на гиперплоскости - person Niklas B.; 21.05.2014
comment
Согласен, формулировка Эппштейна не требует v!=0. Что касается xi, xj, лежащих на плоскости, это уже было учтено в Av>=0, как вы определили матрицу A, верно. - person Pranav; 21.05.2014
comment
@Pranav О, теперь я понимаю, что вы имеете в виду. Обновлено - person Niklas B.; 21.05.2014
comment
CGAL имеет только {<=,>=,=} операторов отношения для выражения ограничений. Можем ли мы представить v!=0 с помощью этого? - person Pranav; 21.05.2014
comment
@Pranav Ну, вы можете просто использовать v.v как целевую функцию для максимизации. - person Niklas B.; 21.05.2014
comment
Позвольте нам продолжить это обсуждение в чате. - person Pranav; 21.05.2014
comment
@Pranav Я только что заметил, что ориентация плоскости на самом деле важна, поэтому вам нужно проверить как vi >= 1, так и vi <= -1 для каждого компонента i - person Niklas B.; 21.05.2014
comment
Просто чтобы убедиться, что я понял значение ориентации вектора нормали в этой задаче: Av>=0; vi>=1 и Av>=0; vi<=-1 эквивалентны Av>=0; vi>=1 и Av<=0; vi>=1? - person Pranav; 22.05.2014
comment
Ну да, это довольно простая алгебра - person Niklas B.; 22.05.2014