Какие целочисленные линейные программы просты?

Пытаясь решить проблему, я выразил ее часть в виде следующей целочисленной линейной программы. Здесь - все натуральные числа, заданные как часть входных данных. Указанное подмножество переменных устанавливается в ноль, а остальные могут принимать положительные целые значения: $\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w$ $x_{ij}$

Свести к минимуму

$\sum_{j=1}^{m}c_{j}\sum_{i=1}^{\ell}x_{ij}$

При условии:

$\sum_{j=1}^{m}x_{ij}=n_{i}\,\,\forall i$

$\sum_{i=1}^{\ell}x_{ij}\ge w\,\,\forall j$

Я хотел бы знать, разрешима ли эта целочисленная программа за полиномиальное время; Моя оригинальная проблема решена, если это так, и я должен попробовать другой способ, если это не так. Итак, мой вопрос:

Как выяснить, можно ли решить некоторую целочисленную линейную программу за полиномиальное время? Какие целочисленные линейные программы известны как простые? В частности, может ли вышеуказанная программа быть решена за полиномиальное время? Не могли бы вы указать мне некоторые ссылки на это?

reference-request linear-programming polynomial-time integer-programming integrality-gap gphilip
источник

Ответы:

Это особый случай транспортной проблемы (или проблемы потока с минимальными затратами), и поэтому он может быть решен за полиномиальное время. Матрица коэффициентов абсолютно унимодулярна, поскольку она является матрицей инцидентности двудольного графа.

Следующие статьи Википедии могут быть полезны.

Ёсио Окамото
источник

@Yoshio: Спасибо, это отвечает на мой конкретный пример проблемы (как только я проверил это для себя). Знаете ли вы об условиях, отличных от полной унимодулярности, которые гарантируют решение за полиномиальное время?

gphilip

@gphilip: Я бы суммировал эти вопросы термином «целостность многогранников», и литература по этому вопросу огромна. В книге «Комбинаторная оптимизация: упаковка и покрытие» Джерарда Корнуэйлса (опубликованной в 2001 году) описаны некоторые результаты в этом направлении.

Ёсио Окамото

@Yoshio: Не могли бы вы сказать мне, почему вы думаете, что матрица коэффициентов является матрицей заболеваемости двудольного графа? Простите за мое невежество, но если говорить о матрице коэффициентов, разве мы не должны сначала преобразовать все ограничения в стандартную форму (

)? Как только мы это сделаем, матрица будет иметь -1 запись, и тогда она не будет соответствовать определению матрицы инцидентности (AFAIK). Или это тот случай, когда мы можем говорить о матрице коэффициентов без предварительного преобразования ограничений в стандартную форму?

A x \leq b

$Ax\le b$

gphilip

@gphilip: Извините. Я сделал неявное сокращение, и я говорил о матрице коэффициентов без преобразования в стандартную форму. Я использовал следующие ярлыки. (1) Если

является полностью унимодулярным (TU, для краткости), то

также является TU, что означает, что нам не нужно заботиться о направлении неравенства. (2) Если

является TU, то

также является TU, что означает, что нам не нужно заботиться об ограничениях равенства. (3) Каждая подматрица матрицы TU является TU. Применение этих правил к матрице инцидентности двудольного графа должно доказать свойство для стандартной формы.

A

$A$

- A

$-A$

A

$A$

[A ∣ - A]

$[A \mid -A]$

Ёсио Окамото

Позвольте мне изменить мои краткие правила следующим образом. (1) Дублирование строки поддерживает полную унимодулярность. (2) Обращение знака ряда сохраняет полную унимодулярность. Они должны делать эту работу.

Ёсио Окамото

В общем, сложно сказать. Но достаточным условием является то, что ваша матрица ограничений является полностью унимодулярной, а правая часть всегда целочисленной (в этом случае правая часть является целочисленной, но вам все равно нужно проверить унимодулярность)

Вы должны взглянуть на это: http://en.wikipedia.org/wiki/Linear_program#Integer_unknowns

Виниций душ Сантуш
источник

Я думал о твоей матрице, и она выглядит абсолютно унимодулярной.

Виниций душ Сантуш

@Vinicius: Не могли бы вы сказать мне, почему матрица выглядит абсолютно унимодулярной для вас? Я не мог понять это, несмотря на комментарий Йошио (см. Мой ответ там).

gphilip

@gphilip: на en.wikipedia.org/wiki/Unimodular_matrix в разделе «Общие полностью унимодулярные матрицы» первый список элементов содержит 4 достаточных условия, чтобы матрица была унимодулярной. Я думаю, что этих условий вместе с ярлыками, которые прокомментировал Йошио, достаточно, чтобы показать, что проблема может быть решена за полиномиальное время.

Виниций душ Сантуш

@gphilip: Какова мотивация для этой линейной программы?

Виниций душ Сантуш

@Vinicius: Мы пытаемся решить проблему, выраженную в терминах, изменяющих входную матрицу определенным способом, чтобы получить другую матрицу с некоторыми хорошими свойствами. Этот LP вышел из одной подзадачи во время процесса.

gphilip

Целочисленная программа только с равенствами может быть решена линейной программой.

Т ....
источник

это казалось важным само по себе.

Т ....

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

Сашо Николов

@SashoNikolov вырожденный случай, но, безусловно, действительный.

T ....

почему отрицательный голос?

T ....