Случайное решение набора целочисленных ограничений

У меня есть набор целочисленных ограничений, которые я хотел бы решить. Ограничения могут состоять из добавления переменных, которые больше, меньше или равны некоторой константе.

Пример:

A >= 20
A <= 30
B <= 10
A + B <= 25
...

Таких простых ограничений будут сотни, а константы на практике имеют гораздо большие значения (сотни тысяч).

Однако мне нужно не просто решение этих ограничений: мне нужно случайное решение из пространства решений. Это не означает, что каждое решение должно иметь равную вероятность (я не думаю, что это возможно без перечисления их всех?), но я хочу, чтобы, например, для переменной A решение обычно было не 20 или 30, а скорее что промежуточные значения так же (или даже более вероятно) будут выбраны.

Какие методы подходят для такого рода задач? Мне трудно понять, где искать, потому что большинство алгоритмов сосредоточены на поиске оптимальных, быстрых или минимальных решений, а не случайных.


random algorithm constraint-programming linear-programming
person Wouter Lievens    schedule 23.12.2013    source источник
comment
Один (возможно, крайне неэффективный) метод — это проб и ошибок: создать случайную точку в пространстве и проверить, удовлетворяет ли он всем ограничениям. Повторяйте, пока точка не пройдет.   -  person Ted Hopp    schedule 24.12.2013
comment
Являются ли ограничения также линейными? Являются ли какие-либо термины произведениями двух или более переменных?   -  person phs    schedule 24.12.2013
comment
В чем проблема домиан? Это может дать некоторое представление о том, как подойти к проблеме.   -  person corsiKa    schedule 24.12.2013
comment
@TedHopp: это было бы непомерно дорого. Какой-то управляемый случайный поиск может быть вариантом.   -  person Wouter Lievens    schedule 24.12.2013
comment
@phs нет товаров, только дополнения, как показано в задаче   -  person Wouter Lievens    schedule 24.12.2013
comment
@corsiKlauseHoHoHo Я пытаюсь процедурно сгенерировать повествовательный граф. Надуманный пример: dl.dropboxusercontent.com/u/17511787/   -  person Wouter Lievens    schedule 24.12.2013
comment
У вас есть дополнительная информация об ограничивающих неравенствах? Будут ли коэффициенты ваших переменных всегда равны 1?   -  person Andrey Mishchenko    schedule 24.12.2013
comment
Метод проб и ошибок непомерно дорог только в том случае, если объем допустимой области очень мал по сравнению с объемом, в котором генерируются случайные испытания. Это полностью зависит от характера ограничений и того, как вы ограничиваете пространство пробной генерации. Это поднимает еще одну проблему методом проб и ошибок: ограничена ли допустимая область?   -  person Ted Hopp    schedule 24.12.2013

Ответы (3)


arrow_upward
3
arrow_downward

Многие системы программирования с ограничениями имеют эвристику поиска (называемую «indomain_random» или что-то подобное), которая дает решения в случайном порядке (с учетом некоторого начального числа). Вот модель MiniZinc для простой задачи:

 var 20..30: A;
 var 0..10: B;     
 solve :: int_search([A,B], first_fail, indomain_random, complete) satisfy;
 constraint A + B <= 25;
 output [ show([A,B])];

Вот несколько решений для пары семян с использованием решателя Gecode FlatZinc:

Seed   Solution
---------------
0      [22,0]
2      [25,0]
3      [22,2]
person hakank    schedule 24.12.2013
comment
Спасибо за совет. Мой проект на Java, и я раньше баловался с JaCoP, и похоже, что он поддерживает эту эвристику. Я это проверю. - person Wouter Lievens; 26.12.2013
comment
Кажется, это работает как шарм. Было действительно легко реализовать с помощью JaCoP, и я получаю, казалось бы, случайные результаты. Спасибо за совет! - person Wouter Lievens; 26.12.2013
comment
Может быть интересно узнать, что, хотя использование рандомизации в эвристике даст случайные результаты, оно не гарантирует какого-либо распределения возможных решений. Существуют более продвинутые методы, которые можно использовать для эффективной эвристической выборки всего пространства решений, но это может быть больше, чем то, что необходимо здесь. Два примера: books.nips.cc/papers/files/nips19/NIPS2006_0084.pdf. и auai.org/uai2012/papers/160.pdf . - person Zayenz; 09.01.2014

arrow_upward
2
arrow_downward

Я бы начал с установления отношений между всеми узлами, которые взаимодействуют с переменными других узлов.

Пройдитесь по графу, отметив все узлы, которые не зависят ни от каких других узлов, как посещенные. Затем выполните итерацию по каждому из узлов, которые зависят от этих узлов, сокращая их диапазон (увеличивая min и уменьшая max) таким образом, чтобы их формулы были согласованы. Итак, если у вас есть A.min=10, A.max=20, B.min = 10, A+B=25, вы можете уменьшить A.max до 15 (потому что B должно быть 10, а 25-10=15). Вы только что уменьшили масштаб А на 50%.

Это становится проще, если вы устанавливаете главный узел: если A+B=25, зависит ли A от B или зависит ли B от A? Сделать ваш граф ориентированным графом намного проще, так как алгоритмы в ориентированных графах проще.

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

person corsiKa    schedule 23.12.2013

arrow_upward
0
arrow_downward

Не совсем полный ответ, но, возможно, полезный и слишком длинный для комментария:

Вам может помочь знание того, что пространство решений выпукло. Это означает, что если у вас есть два решения A1, B1, C1 и A2, C2, B2, то любая тройка между ними также является решением.

(Здесь «между» означает, что в диапазоне [0,1] есть некоторое действительное число t, так что:

  • Anew = t * A1 + (1 - t) * A2
  • Bnew = t * B1 + (1 - t) * B2
  • Cnew = t * C1 + (1 - t) * C2

Чтобы понять, почему, вы можете просто попробовать подставить эти выражения для Anew, Bnew, Cnew в ваши неравенства, и неравенства будут расширяться как истинные, потому что они делают это для A1, B1, C1 и A2, B2, C2.)

Вы можете использовать эту информацию, чтобы ограничить область поиска n пространством. Например, если вы нашли одно решение и хотите узнать, как далеко в каком-либо направлении простирается пространство вашего решения, вы можете запустить что-то вроде бинарного поиска вниз к известному решению. И т.д...

person Andrey Mishchenko    schedule 23.12.2013