PG 534 Введення маршруту транспортних засобів

PG 534 Введення транспортних засобів Вступ Markus Chimani & Karsten Klein LS11, TU Dortmund

PG Цілі Framework Branch & Cut, Branch & Price, вибір цільових функцій, обмеження, евристика, нерівності, методи поділу тощо. Експериментальне вивчення також практичні дані

Огляд основ: невеликі приклади методів вирішення LP та ILP Розв'язувач/фреймворк Великий приклад 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: Вартість їжі Об’єкт: Найдешевша дієта з достатнім запасом їжі Калорійність/ккал Вітамін С/мг Ціна/хліб (500 г) 1230 0 2,99 Апельсиновий сік ( 1l) 560300 2,50 Вимога: 2000 60. хв 2,99x 1 + 2,50x 2 сто 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 Створіть 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/Framework 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 Цільова функція: 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 дійсний? О хв (о, Л)! 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 = НУЛЬ; 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 = runscip (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. 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, edge-> length, 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->відповідний вар, 1.0)); 0, NULL, NULL 0 змінних, порожній масив для змінних, порожній масив для коефіцієнтів> SCIP_CALL (SCIPaddCons (scip, мінуси)); SCIP_CALL (SCIPreleaseCons (scip, & мінуси)); // додаємо обробник обмежень субтурів SCIP_CONS * мінуси; SCIP_CONSDATA * consdata; SCIP_CALL (SCIPallocMemory (scip, & consdata)); consdata-> графік = графік; SCIP_CALL (SCIPcreateCons (scip, мінуси, ім'я, SCIPfindConshdlr (scip, "підтур"), консадати, 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.); >; Для швидкості (*), (**) переважно однакові або дуже схожі реалізації