PG 534 Въведение в маршрута на автомобила

PG 534 Въведение в маршрута Markus Chimani & Karsten Klein LS11, TU Dortmund

PG Цели Рамка Branch & Cut, Branch & Price, избираеми целеви функции, ограничения, евристика, неравенства, методи за разделяне и др. Експериментално проучване също практически данни

Преглед на основите: малки примери LP vs. Методи за решение на ILP Solver/Framework Голям пример TSP: формулиране, изрязва SCIP: Основи SCIP код за организационни акаунти на TSP, уеб сървър и др. Петък

Линейно програмиране Формулиране на оптимизационен проблем с променлив вектор x = (x 1, xn) чрез: Линейна функция на разходите с вектор на разходите c = (c 1. cn) min i = 1.ncixi (също max) Линейни (in) уравнения като ограничения i = 1.naixib (също,) специални форми: xi 0 вектор x, който отговаря на всички условия: валиден вектор на решение x * с cx * cx валиден x: оптимално решение

Линейна програма Изписана: мин/макс c 1 x 1 +. + c n x n sto a 11 x 1 +. + a 1n x n b 1. Стандартна форма: a m1 x 1 +. + a mn x n b m x i неограничени променливи, или x i 0 първоначално трансформирана целева функция max cx min -cx уравнение a j x b j a j x + s = b j, s 0 неограничена променлива x i x i + x i - с x i +, x i- 0

Линейна програма компактна нотация с матрица A R m, n, вектори b R m, c, x R n: мин

Пример: Диетичен проблем xi: Различни храни bi: Идеално снабдяване с хранителни вещества (напр. Витамини,) ci: Разходи за храна Обект: Най-евтината диета с достатъчно количество храна Калорична стойност/ккал Витамин С/mg Цена/хляб (500g) 1230 0 2.99 Портокалов сок ( 1l) 560 300 2,50 Изискване: 2000 60.min 2,99x 1 + 2,50x 2 sto 1230x 1 + 560x 2 2000 300x 2 60 x 1, x 2 0

Сложност на линейното програмиране: Проблемите с линейната оптимизация могат да бъдат решени в полиномиално време Методи: Метод с вътрешни точки Елипсоиден метод Симплекс метод (експоненциален в най-лошия случай)

Вектори за геометрична интерпретация: посока, разходи за дължина x 1 + x 2 вектор c = (1,1) 4 3 2 1 1 2 3 4

Вектори за геометрична интерпретация: посока, разходи за дължина x 1 + x 2 вектор c = (1,1) уравнение x 1 + 2x 2 = 3 вектор a = (1,2) 4 3 2 1 1 2 3 4

Вектори за геометрична интерпретация: посока, дължина разходи x 1 + x 2 вектор c = (1,1) уравнение x 1 + 2x 2 = 3 вектор a = (1,2) 4 x 2 = ½ (3-x 1) 3 2 1 1 2 3 4

Вектори на геометрична интерпретация: посока, дължина разходи x 1 + x 2 вектор c = (1,1) уравнение x 1 + 2x 2 = 3 вектор a = (1,2) 4 3 2 1 x 1 + 2x 2 = 4 1 2 3 4

Вектори за геометрична интерпретация: посока, разходи за дължина x 1 + x 2 вектор c = (1,1) уравнение x 1 + 2x 2 = 3 вектор a = (1,2) 4 3 2 1 хиперплан, общ, n-1 мерна 1 2 3 4

Вектори за геометрична интерпретация: посока, дължина разходи x 1 + x 2 вектор c = (1,1) уравнение x 1 + 2x 2 = 3 вектор a = (1,2) 4 3 неравенство x 1 + 2x 2 3? 2 1 полупространство, общо, n-мерно 1 2 3 4

Вектори на геометрична интерпретация: посока, дължина разходи x 1 + x 2 вектор c = (1,1) уравнение x 1 + 2x 2 = 3 вектор a = (1,2) 4 3 2 1 max x 1 + x 2 x 1 + 2x 2 3 2x 1 + x 2 3 x 1, x 2 0 полиедри, общи, 1 2 3 4 оптимално решение (1, 1), стойност 2

Intermezzo Interactive CPLEX: LP1

Решението за линейно програмиране в последния пример беше цяло число! Ами ако не, но се изисква цяло число?

Целочислено линейно програмиране ILP: цяло число на необходимото решение (дискретно) Смесено ILP: Ако само за някои xi цели числа 4 3 2 max x 1 + x 2 sto 14 x 1-18x 2-9 2x 1-2 x 2 1 x 1, x 2 0 1 Интерактивен CPLEX: LP2 1 2 3 4

Целочислено линейно програмиране ILP: цяло число на необходимото решение (дискретно) Смесен ILP: Ако само за някои xi цели числа 4 3 2 max x 1 + x 2 sto 14 x 1-18x 2-9 2x 1-2 x 2 1 x 1, x 2 0 1 1 2 3 4 Оптимално решение (4.5, 4), стойност 8.5

Целочислено линейно програмиране ILP: изисква се цяло число решение (дискретно) Смесен ILP: Ако само за някои xi цели числа се отдели невалидно решение 4 Генериране x 1 Изрязване 4 x 1 5 max x 1 + x 2 3 2 или разклонение sto 14 x 1-18x 2 -9 2x 1-2 x 2 1 x 1, x 2 0 1 x 1, x 2 цяло число Изчислете първо релаксация 1 2 3 4

Целочислено линейно програмиране ILP: изисква се цяло число решение (дискретно) Смесен ILP: Ако само за няколко xi цели числа Интерактивен CPLEX: LP2ILP 4 3 2 1 max x 1 + x 2 sto 14 x 1-18x 2-9 2x 1-2 x 2 1 x 1, x 2 0 x 1, x 2 цяло число оптимално решение (2, 2), стойност 4 1 2 3 4

Цялостно линейно програмиране ILP е NP-пълно, дори в специалния случай x i Сила на формулировката: Много по-важно, отколкото при LP! Броят на променливите и ограниченията тук не е решаващ, но как точно ограниченията описват изпъкналия корпус на валидните целочислени решения!

B&C & P (някои) Solver/Frame COIN-OR LP (M) ILP CPlex CPlex SCIP SoPlex Abacus BCP Symphony CBC OSI CLP скъп, но най-бърз безплатен софтуер и много други.

TSP: Формулировка (1) Дадено: Търси се: n градове: S = разстояния между градовете: d (a, b) Най-краткото двупосочно пътуване през всички градове Променливи: xv, wv, w S Целева функция: min d (v, w) xv, wv, w p

TSP: Формулация (2) Променливи: xv, wv, w S Целева функция: min d (v, w) xv, w Ограничения: v, w S w S xv, w = 2 v S v T w T xv, w 2 TS експоненциално много!

Завършихте всички подпроблеми? TSP: Методи за решение Изчисляване на евристика: горна граница O Подпроблема 1. Решаване на PL (полином, CPLEX) Започнете с по-проста линейна програма P min v, w S 0 xv, w 1 d (v, w) xv, wv, w S 2. Действително L валиден? O min (o, L)! 3. L O е? Крайна подпроблема. 4. Евристика, базирана на L, вероятно нова O 5. Намерете нарушено неравенство (*)? Добавете към P и отидете на 1. O е оптимално w S x v, w = 2 v S подпроблема x v, w = 0 подпроблема x v, w = 1 x v, w 2 T S (*) v T w T

SCIP: Общ преглед SCIP = Решаване на целочислени програми с ограничения http://scip.zib.de, Doxygen-Docs (много добър и полезен) @home: изтегляне, компилиране чрез (по подразбиране: gcc, linux) make LPS =? READLINE = false ZLIB = false ZIMPL = false spx (SoPlex), clp (CLP) @uni: инсталиран и компилиран (LPS = cpx/CPlex) в /home/plug/scip-1.1.0 Примери: TSP, VRP,/home/plug /scip-1.1.0/examples/

TSP с SCIP: (Някои) важни файлове Основни файлове mymain.cpp main () Настройване на структурите на SCIP Регистриране на приставки (четец, разделяне, евристика, ценообразуване,) myreader.h myreader.cpp mysubtour.h mysubtour.cpp Четене в проблема Създаване на първоначалния LP Разделяне на ограниченията за подтур

mymain.cpp #include #include "objscip/objscip.h" #include "objscip/objscipdefplugins.h" #include "myreader.h" #include "mysubtour.h" SCIP_RETCODE runscip (int argc, char ** argv) < >SCIP * scip = NULL; SCIP_CALL (SCIPcreate (& scip)); SCIP_CALL (SCIPincludeObjReader (scip, нов MyReader (scip), TRUE)); SCIP_CALL (SCIPincludeObjConshdlr (scip, new MySubtour (), TRUE)); SCIP_CALL (SCIPincludeDefaultPlugins (scip)); SCIP_CALL (SCIPprocessShellArguments (scip, argc, argv, "parameter.txt")); SCIP_CALL (SCIPfree (& scip)); връщане SCIP_OKAY; int main (int argc, char ** argv) < >SCIP_RETCODE retcode = runcip (argc, argv); if (retcode! = SCIP_OKAY) SCIPprintError (retcode, stderr); SCIP_CALL (. ()); SCIP_RETCODE ret =. (); if (ret! = SCIP_OKAY) return ret; Аргументи SCIPprocessShell. SCIPsolve (scip);.

TSP с SCIP: (Някои) важни файлове Основни файлове mymain.cpp myreader.h myreader.cpp main () Настройване на структурите на SCIP Регистриране на приставки (четец, разделяне, евристика, ценообразуване,) Четене в проблема Създаване на първоначалния LP mysubtour. h mysubtour.cpp Разделяне на ограниченията за подтур

MyReader () <> виртуален SCIP_RETCODE scip_free (SCIP * scip, SCIP_READER * четец) < return SCIP_OKAY; >виртуален SCIP_RETCODE scip_write (. SCIP_RESULT * резултат) < >* резултат = SCIP_DIDNOTRUN; връщане SCIP_OKAY; >; виртуален SCIP_RETCODE scip_read (SCIP * scip, SCIP_READER * четец, const char * име на файл, SCIP_RESULT * резултат);

myreader.cpp #include "myprobdata.h" // клас MyProbData: public scip: objprobdata; SCIP_RETCODE MyReader: scip_read (SCIP * scip, SCIP_READER * четец, const char * име на файл, SCIP_RESULT * резултат) < *result = SCIP_DIDNOTRUN; MyProbData* graph = loadgraphfromfile(filename); // assume function exists if(graph == NULL) return SCIP_READERROR; SCIP_CALL( SCIPcreateObjProb(scip, "MyProblemData", graph, TRUE) ); // add variables for( alle kanten edge von graph ) < >SCIP_VAR * var; низ поток име; ИД на име; SCIP_CALL (SCIPcreateVar (scip, & var, name.str (). C_str (), 0, 1, ръб-> дължина, SCIP_VARTYPE_BINARY, TRUE, FALSE, NULL, NULL, NULL, NULL)); ръб-> съответстващ var = var; SCIP_CALL (SCIPaddVar (scip, var)); > *** следващ слайд тук: добавете ограничения *** * резултат = SCIP_SUCCESS; връщане SCIP_OKAY; 0, 1, ръб-> дължина долна граница: 0, горна граница: 1, коефициент в целевата функция

myreader.cpp // добавяне на ограничения за степен за (всички възлови възли на графика) < SCIP_CONS* cons; stringstream name; name id; SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name.str().c_str(), 0, NULL, NULL, 2.0, 2.0, TRUE, FALSE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) ); w S x v,w = 2 v S for( alle kanten edge adjazent zu node ) SCIP_CALL( SCIPaddCoefLinear(scip, cons, edge->съответстващ var, 1.0)); 0, NULL, NULL 0 променливи, празен масив за променливи, празен масив за коефициенти> SCIP_CALL (SCIPaddCons (scip, минуси)); SCIP_CALL (SCIPreleaseCons (scip, & минуси)); // добавяне на манипулатор на ограничения за подтур SCIP_CONS * cons; SCIP_CONSDATA * consdata; SCIP_CALL (SCIPallocMemory (scip, & consdata)); consdata-> графика = графика; SCIP_CALL (SCIPcreateCons (scip, cons, name, SCIPfindConshdlr (scip, "subtour"), consdata, FALSE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE)); SCIP_CALL (SCIPaddCons (scip, минуси)); SCIP_CALL (SCIPreleaseCons (scip, & минуси)); 2.0, 2.0 лява и дясна граница 2.0 ограничение 2.0

MySubtour () <> // валидно ли е решение? виртуален SCIP_RETCODE scip_check (. SCIP_SOL * sol.); виртуален SCIP_RETCODE scip_enfolp (.); lp = частично решение виртуален SCIP_RETCODE scip_enfops (.); ps = псевдо решение enfo = налагане // закръгляване последици от ограничения виртуален SCIP_RETCODE scip_lock (.); За валидност // отделно виртуално SCIP_RETCODE scip_sepalp (.); виртуален SCIP_RETCODE scip_sepasol (. SCIP_SOL * sol.); >; За скорост (*), (**) най-вече еднакви или много подобни реализации