Вовед во рутирање на возила PG 534

Вовед во рутирање на возила PG 534 Маркус Чимани и Карстен Клајн LS11, ТУ Дортмунд

Рамка на целите на ПГ гранка и намалување, гранка и цена, објективни функции што можат да се изберат, ограничувања, хевристика, нееднаквости, методи на раздвојување, итн. Експериментална студија, исто така, практични податоци

Преглед на основите: Мали примери LP наспроти методите на решенија ILP Решавач/рамка Голем пример TSP: формулација, намалувања SCIP: Основи SCIP код за организациски сметки на TSP, веб-сервер и сл. Петок

Линеарно програмирање Формулирање на проблем за оптимизација со променлив вектор x = (x 1, xn) преку: Функција на линеарни трошоци со вектор на трошоци c = (c 1. cn) min i = 1.ncixi (исто така максимум) Линеарни (не) равенки како ограничувања 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 првично трансформирана целна функција максимум cx мин -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: Цена на храна Објект: Најевтина диета со доволно снабдување со храна Калориска вредност/kcal Витамин Ц/mg Цена/леб (500 гр.) 1230 0 2,99 Сок од портокал ( 1л) 560 300 2,50 Барање: 2000 60 мин. 2,99х 1 + 2,50х 2 ста. 1230х 1 + 560х 2 2000 300х 2 60 х 1, х 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 макс 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

Интермецо Интерактивен CPLEX: LP1

Решение за линеарно програмирање во последниот пример беше цел број! Што ако не, но потребен е цел број?

Целосно линеарно програмирање ILP: цел број на решението потребно (дискретно) Мешано ILP: Ако само за некои xi цели 4 3 2 максимум 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 4 2 максимум x 1 + x 2 ставови 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 максимум x 1 + x 2 3 2 или разгранете 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 максимум x 1 + x 2 во 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 е комплетна НП, дури и во посебниот случај x i Јачина на формулацијата: Многу поважно отколку со ЛП! Бројот на променливи и ограничувања не се одлучувачки овде, но како точно ограничувањата го опишуваат конвексот на трупот на валидните цели решенија!

B&C & P (некои) решенија/рамки 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 Функција на целта: мин d (v, w) xv, wv, w стр

TSP: Формулација (2) Променливи: xv, wv, w S Функција на целта: мин d (v, w) xv, w Ограничувања: v, w S w S xv, w = 2 v S v T w T xv, w 2 ТС експоненцијално многу!

Ги завршивте сите под-проблеми? TSP: Методи на решенија Пресметајте хеуристички: горниот дел на О Подпроблем 1. Решете го PL (полином, CPLEX) Започнете со поедноставна линеарна програма P min v, w S 0 xv, w 1 d (v, w) xv, wv, w S 2. Реално Дали важи? О мин (о, Л)! 3. Дали е Л О? Крај на подпроблем. 4. Хеуристички засновано врз L евентуално ново О 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) направи 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/прескокни.1.1.0/примери /

TSP со SCIP: (Некои) важни датотеки Суштински датотеки mymain.cpp main () Поставување на структури на SCIP Регистрација на приклучоци (читач, одделување, хеуристика, цени) myreader.h myreader.cpp mysubtour.h mysubtour.cpp Читање во проблемот Создавање на почетна ЛП Одвојување на подграничните ограничувања

mymain.cpp # вклучи # вклучи "објсип/објсип.х" # вклучи "обејцип/објсипдефплагинс.х" # вклучи "мој читач.х" # вклучи "mysubtour.h" СКИП_РЕТКОД превземање (ин арг, ше ** арвв) < >БЕЗБЕДНОСТ * шипка = НУЛКА; 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 реткод = прескокнување (argc, argv); ако (реткод! = SCIP_OKAY) SCIPprintError (реткод, stderr); SCIP_CALL (. ()); SCIP_RETCODE рет =. (); ако (рет! = SCIP_OKAY) се врати рет; SCIPprocessShellArguments. SCIPsolve (scip);.

TSP со SCIP: (Некои) важни датотеки Суштински датотеки mymain.cpp myreader.h myreader.cpp main () Поставување на структурите на SCIP Регистрација на приклучоците (читач, раздвојување, хевристика, ценовник) Читање во проблемот Креирање на почетната mysubtour LP. 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 # вклучи "myprobdata.h" // класа MyProbData: јавен преглед: 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)); раб-> соодветно вар = вар; 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->соодветна варијанта, 1.0)); 0, NULL, NULL 0 променливи, празна низа за променливи, празна низа за коефициенти> SCIP_CALL (SCIPaddCons (scip, cons)); SCIP_CALL (SCIPreleaseCons (scip, и минуси)); // додадете управувач на ограничувања за субтурни SCIP_CONS * лоши страни; SCIP_CONSDATA * консодатоци; SCIP_CALL (SCIPallocMemory (scip, & консдата)); конс- податоци> графикон = граф; SCIP_CALL (SCIPcreateCons (scip, cons, name, SCIPfindConshdlr (scip, "subtour"), consdata, FALSE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE)); SCIP_CALL (SCIPaddCons (scip, cons)); SCIP_CALL (SCIPreleaseCons (scip, и минуси)); 2.0, 2.0 лево и десно граници 2.0 ограничување 2.0

MySubtour () <> // дали решението е валидно? виртуелен SCIP_RETCODE scip_check (. SCIP_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 * сол.); >; За брзина (*), (**) претежно идентични или многу слични имплементации