Целочисленное программирование

  • Задача целочисленного программирования — это задача математической оптимизации или выполнимости, в которой некоторые или все переменные должны быть целыми числами. Часто термин адресуется к целочисленному линейному программированию (ЦЛП), в котором целевая функция и ограничения (за исключением требования целочисленности) линейны.

    Целочисленное программирование является NP-трудной задачей. Специальный случай, 0-1 целочисленное линейное программирование, в которой переменные принимают значения 0 или 1, является одной из 21 NP-полных задач Карпа.

Источник: Википедия

Связанные понятия

Полуопределённое программирование (en: Semidefinite programming, SDP) — это подраздел выпуклого программирования, которое занимается оптимизацией линейной целевой функции (целевая функция — это заданная пользователем функция, значение которой пользователь хочет минимизировать или максимизировать) на пересечении конусов положительно полуопределённых матриц с аффинным пространством.
Не путать с «симплекс-методом» — методом оптимизации произвольной функции. См. Метод Нелдера — МидаСимплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.

Подробнее: Симплекс-метод
Метод декомпозиции Данцига — Вулфа представляет собой специализированный вариант симплекс-метода.
Алгоритм Гельфонда — Шенкса (англ. Baby-step giant-step; также называемый алгоритмом больших и малых шагов) — в теории групп детерминированный алгоритм дискретного логарифмирования в мульпликативной группе кольца вычетов по модулю простого числа. Был предложен советским математиком Александром Гельфондом в 1962 году и Дэниэлем Шенксом в 1972 году.
Метод Стронгина — метод решения одномерных задач условной липшицевой оптимизации. Позволяет находить глобально оптимальное решение в задачах с ограничениями неравенствами при условии, что целевая функция задачи и левые части неравенств удовлетворяют условию Липшица в области поиска.
Предобуславливание (также предобусловливание) — процесс преобразования условий задачи для её более корректного численного решения. Предобуславливание обычно связано с уменьшением числа обусловленности задачи. Предобуславливаемая задача обычно затем решается итерационным методом.
Поточный алгоритм (англ. streaming algorithm) — алгоритм для обработки последовательности данных в один или малое число проходов.
Метод обратного распространения ошибки (англ. backpropagation) — метод вычисления градиента, который используется при обновлении весов многослойного перцептрона. Впервые метод был описан в 1974 г. А. И. Галушкиным, а также независимо и одновременно Полом Дж. Вербосом. Далее существенно развит в 1986 г. Дэвидом И. Румельхартом, Дж. Е. Хинтоном и Рональдом Дж. Вильямсом и независимо и одновременно С.И. Барцевым и В.А. Охониным (Красноярская группа). Это итеративный градиентный алгоритм, который используется...
В исследовании операций под аппроксимационным алгоритмом понимается алгоритм, использующийся для поиска приближённого решения оптимизационной задачи.

Подробнее: Аппроксимационный алгоритм
Вероятностное округление — это широко используемый подход для разработки и анализа таких аппроксимационных алгоритмов. Базовая идея — использование вероятностного метода для преобразования соответствующей оптимального решения задачи линейного программирования (ЛП) в приближённое к оптимальному решению исходной задачи.
Ме́тоды Ру́нге — Ку́тты (в литературе встречаются названия: ме́тоды Ру́нге — Ку́тта или же ме́тоды Ру́нге — Кутта́) — большой класс численных методов решения задачи Коши для обыкновенных дифференциальных уравнений и их систем. Первые методы данного класса были предложены около 1900 года немецкими математиками К. Рунге и М. В. Куттой.
Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией сложности вычислений. Объём работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется...
Обучение с ошибками в кольце (англ. Ring learning with errors, RLWE)— это вычислительная задача, которая была сформулирована как вариант более общей задачи обучения с ошибками (с англ. LWE), с целью использовать преимущество дополнительной алгебраической структуры (т.е. кольца многочленов) из теории решеток, что дало возможность повысить и расширить возможности шифрования тех криптографических приложений, которые ранее основывались на LWE. Задача RLWE стала основой новых криптографических алгоритмов...
Генерация столбцов или отложенная генерация столбцов — это эффективный подход к решению больших задач линейного программирования.
Обучение с ошибками (англ. Learning with errors) — это концепция машинного обучения, суть которой заключается в том, что в простые вычислительные задачи (например, системы линейных уравнений) намеренно вносится ошибка, делая их решение известными методами неосуществимым за приемлемое время.
Метод конечных элементов (МКЭ) — это численный метод решения дифференциальных уравнений с частными производными, а также интегральных уравнений, возникающих при решении задач прикладной физики. Метод широко используется для решения задач механики деформируемого твёрдого тела, теплообмена, гидродинамики и электродинамики.
Универса́льное хеши́рование (англ. Universal hashing) — это вид хеширования, при котором используется не одна конкретная хеш-функция, а происходит выбор из заданного семейства по случайному алгоритму. Такой подход обеспечивает равномерное хеширование: для очередного ключа вероятности помещения его в любую ячейку совпадают. Известно несколько семейств универсальных хеш-функций, которые имеют многочисленные применения в информатике, в частности в хеш-таблицах, вероятностных алгоритмах и криптографии...
Неотрицательное матричное разложение (НМР), а также неотрицательное приближение матрицы, это группа алгоритмов в мультивариантном анализе и линейной алгебре, в которых матрица V разлагается на (обычно) две матрицы W и H, со свойством, что все три матрицы имеют неотрицательные элементы. Эта неотрицательность делает получившиеся матрицы более простыми для исследования. В приложениях, таких как обработка спектрограмм аудиосигнала или данных мускульной активности, неотрицательность свойственна рассматриваемым...
Квадрати́чная зада́ча о назначе́ниях (КЗН, англ. Quadratic assignment problem, QAP) — одна из фундаментальных задач комбинаторной оптимизации в области оптимизации или исследования операций, принадлежащая категории задач размещения объектов.
Обучение признакам или обучение представлениям — это набор техник, которые позволяют системе автоматически обнаружить представления, необходимые для выявления признаков или классификации исходных (сырых) данных. Это заменяет ручное конструирование признаков и позволяет машине как изучать признаки, так и использовать их для решения специфичных задач.
Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой, выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.
В комбинаторной оптимизации под линейной задачей о назначениях на узкие места (linear bottleneck assignment problem, LBAP) понимается задача, похожая на задачу о назначениях.

Подробнее: Линейная задача о назначениях в узких местах
Метод внутренней точки — это метод позволяющий решать задачи выпуклой оптимизации с условиями, заданными в виде неравенств, сводя исходную задачу к задаче выпуклой оптимизации.
В математике методы проверки на простоту с помощью эллиптических кривых (англ. - Elliptic Curve Primality Proving, сокр. ЕСРР) являются одними из самых быстрых и наиболее широко используемых методов проверки на простоту . Эту идею выдвинули Шафи Гольдвассер и Джо Килиан в 1986 году; она была превращена в алгоритм А.О.Л. Аткином в том же году. Впоследствии алгоритм был несколько раз изменён и улучшен, в особенности Аткином и François Morain в 1993. Концепция использования факторизации с помощью эллиптических...

Подробнее: Тест простоты с использованием эллиптических кривых
Обучение дерева решений использует дерево решений (как предиктивную модель), чтобы перейти от наблюдений над объектами (представленными в ветвях) к заключениям о целевых значениях объектов (представленных в листьях). Это обучение является одним из подходов моделирования предсказаний, используемых в статистике, интеллектуальном анализе данных и обучении машин. Модели деревьев, в которых целевая переменная может принимать дискретный набор значений, называются деревьями классификации. В этих структурах...
Односторонняя функция — математическая функция, которая легко вычисляется для любого входного значения, но трудно найти аргумент по заданному значению функции. Здесь «легко» и «трудно» должны пониматься с точки зрения теории сложности вычислений. Разрыв между сложностью прямого и обратного преобразований определяет криптографическую эффективность односторонней функции. Неинъективность функции не является достаточным условием для того, чтобы называть её односторонней. Односторонние функции могут называться...
Постепенная оптимизация — это техника глобальной оптимизации, которая пытается решить трудную задачу оптимизации путём решения сначала сильно упрощённой задачи с последовательным преобразованием этой задачи, пока она не станет эквивалентна исходной трудной оптимизационной задаче.
Байесовское программирование — это формальная система и методология определения вероятностных моделей и решения задач, когда не вся необходимая информация является доступной.
Ядерные методы в машинном обучении — это класс алгоритмов распознавания образов, наиболее известным представителем которого является метод опорных векторов (МОВ, англ. SVM). Общая задача распознавания образов — найти и изучить общие типы связей (например, кластеров, ранжирования, главных компонент, корреляций, классификаций) в наборах данных. Для многих алгоритмов, решающих эти задачи, данные, представленные в сыром виде, явным образом преобразуются в представление в виде вектора признаков посредством...

Подробнее: Ядерный метод
Метод Куайна—Мак-Класки (англ. Quine–McCluskey method) — табличный метод минимизации булевых функций, предложенный Уиллардом Куайном и усовершенствованный Эдвардом Мак-Класки. Представляет собой попытку избавиться от недостатков метода Куайна.
Многокритериальная оптимизация, или программирование (англ. Multi-objective optimization) — это процесс одновременной оптимизации двух или более конфликтующих целевых функций в заданной области определения.
Цикломати́ческая сло́жность програ́ммы (англ. cyclomatic complexity of a program) — структурная (или топологическая) мера сложности компьютерной программы. Мера была разработана Томасом Дж. Маккейбом в 1976 году.
Обобщённая задача коммивояжёра — задача комбинаторной оптимизации, являющаяся обобщением хорошо известной задачи коммивояжёра. Исходными данными для задачи является множество вершин, разбиение этого множества на так называемые кластеры, а также матрица стоимостей перехода из одной вершины в другую. Задача заключается в нахождении кратчайшего замкнутого пути, который бы посетил по одной вершине в каждом кластере (существует также модификация, когда путь должен посетить хотя бы по одной вершине в каждом...
Задача коммивояжёра (англ. Travelling salesman problem, сокращённо TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что...
Статистическая теория обучения — это модель для обучения машин на основе статистики и функционального анализа. Статистическая теория обучения имеет дело с задачами нахождения функции предсказывания, основанной на данных. Статистическая теория обучения привела к успешным приложениям в таких областях, как компьютерное зрение, распознавание речи, биоинформатика и бейсбол.
Протокол Диффи-Хеллмана с использованием суперсингулярной изогении (англ. Supersingular isogeny Diffie–Hellman key exchange, SIDH) — это постквантовый криптографический алгоритм, позволяющий двум и более сторонам получить общий секретный ключ, используя незащищенный от прослушивания канал связи. Это аналог протокола Диффи-Хеллмана, основанный на блуждании в суперсингулярном изогенном графе, который предназначен противостоять криптоаналитической атаке противника, владеющего квантовым компьютером...
В информатике временна́я сложность алгоритма определяет время работы, используемое алгоритмом, как функции от длины строки, представляющей входные данные . Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая исключает коэффициенты и члены меньшего порядка. Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, т.е. при стремлении размера входа к бесконечности. Например, если время, которое нужно алгоритму для выполнения...

Подробнее: Временная сложность алгоритма
Метод Пиявского - метод нахождения глобального минимума (максимума) липшицевой функции, заданной на компакте. Прост в реализации и имеет достаточно простые условия сходимости. Подходит для широкого класса функций, производную которых, например, мы можем ограничить.
Вариацио́нное исчисле́ние — раздел анализа, в котором изучаются вариации функционалов. Наиболее типичная задача — найти функцию, на которой заданный функционал достигает экстремального значения.
Параметрическая редукция — это техника для разработки эффективных алгоритмов, которые достигают своей эффективности путём препроцессорного шага, в котором вход алгоритма заменяется на меньший вход, называемый «ядром». Результат решения задачи на ядре должен быть либо тем же самым, что и при исходных данных, либо выход решения для ядра должен легко преобразовываться в желаемый выход исходной задачи.
Метод наименьших квадратов (МНК) — математический метод, применяемый для решения различных задач, основанный на минимизации суммы квадратов отклонений некоторых функций от искомых переменных. Он может использоваться для «решения» переопределенных систем уравнений (когда количество уравнений превышает количество неизвестных), для поиска решения в случае обычных (не переопределенных) нелинейных систем уравнений, для аппроксимации точечных значений некоторой функции. МНК является одним из базовых методов...
Вероятностно приблизительно корректное обучение (ВПК обучение, англ. Probably Approximately Correct learning, (PAC learning) в теории вычислительного обучения — это схема математического анализа машинного обучения. Схему предложил в 1984 Лесли Вэлиант.
Полный перебор (или метод «грубой силы», англ. brute force) — метод решения математических задач. Относится к классу методов поиска решения исчерпыванием всевозможных вариантов. Сложность полного перебора зависит от количества всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий.
Макроконвейер — распределенная многопроцессорная система, обладающая программной и аппаратной поддержкой организации вычислений по макроконвейерному принципу. Этот принцип был предложен в 1978 году советским математиком В. М. Глушковым. Его суть состоит в том, что при распределении вычислительных заданий между процессорами каждому процессору на очередном шаге вычислений дается такое задание, которое может загрузить его работой на определенное время, без взаимодействия с другими процессорами. Последовательное...
Схема шифрования GGH (англ. Goldreich–Goldwasser–Halevi) — асимметричная криптографическая система, основанная на решётках. Также существует схема подписи GGH.
Компромисс времени и памяти (англ. Space-time trade-off, «выбор оптимального соотношения „место-время“» (англ. space-time trade-off), или, иначе, «выбор оптимального соотношения „время-память“» (англ. time-memory trade-off)) — компромиссный подход к решению ряда задач в информатике, при котором используется обратное соотношение требуемого объёма памяти и скорости выполнения программы: время вычислений может быть увеличено за счёт уменьшения используемой памяти или, наоборот, снижено за счёт увеличения...
Криптосистема Джентри (от фамилии создателя Крейга Джентри) — первая возможная конструкция для полностью гомоморфной криптосистемы, основанная на криптографии на решетках. Впервые была предложена Крейгом Джентри в 2009 году и являлась темой его докторской диссертации. Схема Джентри поддерживает операции сложения и умножения над шифротекстом, что позволяет построить кольца для реализации любых произвольных вычислений. Впоследствии имела множество доработок и модификаций с целью улучшения её производительности...
В теории вычислительной сложности сложность алгоритма в среднем — это количество неких вычислительных ресурсов (обычно — время), требуемое для работы алгоритма, усреднённое по всем возможным входным данным. Понятие часто противопоставляется сложности в худшем случае, где рассматривается максимальная сложность алгоритма по всем входным данным.
Задача о размещении объектов, известная также как анализ расположения оборудования или задача k-центра, — это ветвь исследования операций и вычислительной геометрии, исследующей оптимальное расположение объектов с целью минимизировать цены перевозок с учётом таких ограничений, как размещение опасных материалов вблизи жилищ. Техника применима также к кластерному анализу.
а б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ э ю я