Оптимизация раскроя рулонных тканей: На примере ОАО "Тверская швейная фабрика" тема диссертации и автореферата по ВАК РФ 05.13.06, кандидат технических наук Мазанов, Павел Георгиевич

• Мазанов, Павел Георгиевич
• кандидат технических наук
• 2006

Оглавление диссертации кандидат технических наук Мазанов, Павел Георгиевич

ВВЕДЕНИЕ.

ГЛАВА 1. ТЕХНОЛОГИЧЕСКАЯ СХЕМА РАСКРОЯ ТКАНЕЙ И ПОСТАНОВКА ЗАДАЧИ ОПТИМАЛЬНОГО РАСКРОЯ.

1.1. Технологическая схема раскроя тканей и существующая система управления (СУ) на ОАО "Тверская швейная фабрика".

1.2. Классификация задач раскроя.

1.3. Обзор литературы по постановкам и методам решения задач раскроя.

1.4. Постановка задачи оптимального раскроя.

ГЛАВА 2. КЛАССИЧЕСКИЕ АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ ЦЛП И ОБОСНОВАНИЕ НЕОБХОДИМОСТИ ИХ МОДЕРНИЗАЦИИ.

2.1. Обзор по методам и алгоритмам решения задач линейного программирования.

2.2. Обзор литературы по методам и алгоритмам решения задач целочисленного линейного программирования.

2.2.1. Метод ветвей и границ.

2.2.2. Методы отсечений.

2.3. Процедуры предварительной обработки и анализа.

ГЛАВА 3. РАЗРАБОТКА МОДИФИЦИРОВАННОГО АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ ЦЛП.

3.1. Разработка и особенности модифицированного алгоритма решения задачи ЛП.

3.2. Разработка и особенности модифицированного алгоритма решения задачи ЦЛП.

ГЛАВА 4. РАЗРАБОТКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ СИСТЕМЫ АВТОМАТИЗАЦИИ ПОДГОТОВИТЕЛЬНО-РАСКРОЙНОГО ПРОИЗВОДСТВА.

4.1. Обзор программных средств по решению задач ЛП и ЦЛП.

4.2. Обзор комплексов программного обеспечения автоматизации швейных производств.

4.3. Описание комплекса программного обеспечения системы автоматизации подготовительно-раскройного производства на ОАО "ТШФ".

4.4. Разработка комплекса программного обеспечения системы автоматизации подготовительно-раскройного производства.

ГЛАВА 5. СРАВНИТЕЛЬНЫЕ АНАЛИЗ И РЕЗУЛЬТАТЫ ВНЕДРЕНИЯ РАЗРАБОТАННЫХ АЛГОРИТМОВ И ПРОГРАММНЫХ СРЕДСТВ.

5.1. Анализ результатов применения ДРМ симплекс-метода для решения задач ЛП.

5.2. Результаты внедрения разработанного комплекса программного обеспечения автоматизации подготовительно-раскройного производства.

Введение диссертации (часть автореферата) на тему «Оптимизация раскроя рулонных тканей: На примере ОАО "Тверская швейная фабрика"»

В настоящее время одним из самых актуальных вопросов является комплексная автоматизация предприятий. Под комплексной автоматизацией предприятий понимается создание системы автоматизации не только производственных процессов, а пронизывание всей деятельности предприятия, которая включает управление запасами, полным циклом производства изделия или продукта, управленческий, материальный, бухгалтерский учет и т.д. при интенсивном использовании вычислительной техники и разнообразного программного обеспечения. Применение вычислительной техники вызвано в первую очередь постоянным усложнением любого технологического процесса и возрастанием задействованных в нем разнообразных ресурсов, увеличением объемов обрабатываемой информации.

Комплексные системы автоматизации с каждым годом становится универсальными, чтобы охватить как можно больше направлений отраслей промышленности. Универсальность таких систем достигается за счет модульной реализации, т.е. каждый модуль системы реализует соответствующий функционал участка производства или сферу управления предприятием.

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

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

Решение вопросов повышения конкурентоспособности и снижения себестоимости выпускаемой продукции в значительной степени связано с автоматизацией работ на этапе подготовительного производства. Одним из путей повышения технико-экономических показателей швейного производства является оптимизация раскроя ткани за счет уменьшения отходов. Как показали исследования, использование систем автоматизации подготовительно-раскройного производства не только снижает затраты на производство одежды, повышаете ее качество, но существенно повышает степень использования материалов - при экономии материалов на 1-2% прибыль возрастает на 5-7%. По оценке [15] свыше 1500 предприятий швейной промышленности России производят раскрой рулонных тканей и перерабатывают в год на сумму около 30 млрд. рублей. Под данным исследований ведущих фирм по производству настилочно-раскройных комплексов и систем автоматизированного проектирования швейной промышленности, суммарные технологические отходы (потери) швейных изделий составляют в среднем 26%. Данные отходы распределяют:

1. 17,4% - межлекальные отходы;

2. 1,5% - потери по ширине ткани;

3. 1,5% — потери при настилании ткани;

4. 2,9% — потери при расчете кусков ткани в настилы;

5. 2,4% - брак в ткани.

Суммарная стоимость технологических отходов [15] от перерабатываемых в России материалов (при 26% отходов) составляет примерно 7,8 млрд. рублей.

Перечисленные факты позволяют считать, что постановка задача раскроя и разработка алгоритмов их решения является актуальным направлением исследования

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

Данная цель предполагает решение следующих задач:

1. Математическая постановка задачи оптимального раскроя рулонных тканей на ОАО "Тверская швейная фабрика" (далее ОАО "ТШФ") с учетом особенностей технологии раскроя - наличие различных типов пороков ткани и "красных" полотен, обеспечение равномерности настила и определенной нормированной разности между соседними столами.

2. Разработка модифицированных алгоритмов и методов решения задач целочисленного линейного программирования (ЦЛП) и связанных с ними задач линейного программирования (ЛП).

3. Разработка и реализация программного обеспечения решения задач ЛП и ЦЛП в расширенной постановке.

4. Разработка и реализация комплекса программного обеспечения автоматизации подготовительно-раскройного производства.

Диссертационная работа выполнялась в рамках проекта создания комплексной системы автоматизации производства ОАО "Тверская швейная фабрика". В качестве объекта исследования в диссертационной работе выбран технологический процесс раскроя рулонных тканей подготовительно-раскройного производства на ОАО "Тверская швейная фабрика".

Методы исследования. Работа базируется на комплексном подходе к проблемам автоматизации промышленного производства. На каждом этапе работы использованы теория математического программирования, исследования и результаты известных постановок и методов решения задач раскроя, методы системного и логического анализа, методы анализа и проектирования информационных систем масштаба предприятия, теория математического моделирования, математическая теория операций и вычислений с числами с фиксированной точкой и заданной точностью, теория управления, известные методы автоматизации систем АСУП и АСУТП швейного производства.

На защиту выносятся:

1. Формализация задачи оптимального раскроя рулонных тканей на ОАО "ТШФ", учитывающая особенности технологии раскроя.

2. Алгоритмы модифицированных симплекс-метода и метода "ветвей и границ" с применением процедур предварительной обработки и анализа;

3. Результаты внедрения разработанного комплекса программных средств системы автоматизации подготовительно-раскройного производства.

Научная новизна работы состоит в следующем:

1. Выполнена формализация задачи оптимального раскроя рулонных тканей с учетом технологических особенностей - обеспечение равномерности настила, определенной разности высот соседних столов, сквозных полотен, учет "красных" полотен.

2. Разработаны модифицированные алгоритмы решения задач линейного и целочисленного линейного программирования с учетом ограничений типа "не больше", "равно" и "не меньше" и двусторонних ограничений на переменные, с применением известных специальных процедур предварительной обработки и анализа, сокращенной симплекс-таблицы, дополнительной процедуры перехода и использованием комбинации современных процедур ветвления, выбора переменной ветвления и возврата по дереву ветвлений для повышения сходимости алгоритмов.

3. Разработан алгоритм решения формализированных задач оптимального раскроя рулонных тканей на ОАО "ТШФ" на базе модифицированных алгоритмов решения задач линейного и целочисленного линейного программирования, позволяющий сократить длину концевых остатков, что существенно повышает степень использования материалов.

Практическая значимость результатов диссертационной работы заключается следующем:

1. Использование разработанных модифицированных алгоритмов решения задач ЛП и ЦЛП для решения широкого класса аналогичных задач;

2. Применение подхода проектирования и создания программных средств автоматизации подготовительно-раскройного производства;

3. Использование разработанного комплекса программных средств на других предприятих швейной промышленности;

4. Разработанный комплекс программных средств позволяет повысить коэффициент использования материала на 5-10% и сократить количество и длины концевых остатков, результатом чего является снижение отходов производства на 3-7%;

5. Разработанный комплекс программных средств позволяет быстро и эффективно строить карты расчета и раскроя материала с предоставлением различных вариантов;

6. Разработанный комплекс программных средств поддерживает интеграцию в уже существующие системы автоматизации и за счет своей модульности обладает гибкостью и масштабируемостью внедрения.

Апробация результатов работы. Основные результаты работы докладывались и обсуждались на международной научно-технической конференции "Компьютерные технологии в управлении, диагностике и образовании" (Тверь, 2002), заседаниях и семинарах кафедры "Автоматизации технологических процессов и производств" Тверского Государственного Технического Университета.

Публикации. По теме диссертационной работы опубликованы пять печатных работ.

Структура и объем диссертации. Данная диссертация состоит из введения, пяти глав, заключения и приложения, включающих табличные результаты, краткое техническое задание. Работа изложена на 142 страницах машинописного текста, кроме того, содержит 39 рисунков и 15 таблиц. Библиографический список включает 111 наименования и занимает 8 страниц.

Заключение диссертации по теме «Автоматизация и управление технологическими процессами и производствами (по отраслям)», Мазанов, Павел Георгиевич

ЗАКЛЮЧЕНИЕ

Актуальность рассмотренной в диссертационной работе задачи подтверждается не только многочисленными источниками, но полученными практическими результатами.

Выполнена математическая постановка задач оптимального раскроя рулонных тканей на примере ОАО "Тверская швейная фабрика" с учетом технологических особенностей процесса настилания и раскроя - требование к наличию сквозных полотен, учет пороков ткани по длине и ширине, обеспечение необходимой разности высот полотен между соседними столами, а также требуемой высоты на каждом столе, - для всех рулонов тканей, для каждого рулона, для каждого отреза рулона ткани. Поставленные задачи оптимального раскроя рулонных тканей состоят в нахождении суммарных минимальных потерь по длине с учетом вышеперечисленных условий и выполнении плана на производства.

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

Данные модифицированные алгоритмы позволяют решать не только задачи оптимального раскроя рулонных тканей, но задачи ЛП и ЦЛП общего вида с ограничений типа " <", " =" и " >" и верхних и нижних границ на переменные.

Применение процедур предварительной обработки и анализа на предварительном этапе решения задач ЛП и ЦЛП позволило значительно сократить количество итераций для нахождения допустимого решения. В ряде случаев с помощью процедур предварительной обработки и анализа было установлено неразрешимость поставленной задачи или недопустимость системы ограничений.

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

Применение расширенных правил выбора ведущего элемента симплекс-преобразование решает проблему неоднозначности выбора, зацикливания симплекс-метода и обеспечивает правильное движение по симплексу.

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

Результаты программных средств, реализующих разработанные модифицированные алгоритмы симплекс-метода и метода "ветвей и границ" показали свою эффективность, заключающуюся в решении более широко спектра задач ЛП и ЦЛП, в сокращении времени и количестве итераций для установления решения задачи, устойчивость к зацикливанию симплекс-метода и неоднозначности выбора переменной как в качестве базисной, так для ветвления.

Базируясь на разработанной библиотеки решения задач ЛП и ЦЛП "OptimLib", было разработано эффективное программное средство расчета оптимального раскроя рулонных тканей "OptimCut".

В свою программное средство "OptimCut" является модулем разработанного комплекса программных средств "Оптимальный раскрой", которое автоматизировало информационные потоки и процессы подготовительно-раскройного производства на ОАО "Тверская швейная фабрика", объединила информационные системы управления (бухгалтерия, инженерные службы ИТР) "Турбо-Бухгалтер" и АСУ ТП "Investronica".

Решение выше перечисленных задач обеспечило достижение поставленной цели -решение задачи оптимального раскроя рулонных тканей на примере ОАО "Тверское швейная фабрика". Результаты испытаний и применения разработанных программных средств позволяют сделать вывод о том, что данный комплекс программных средств может приняться на аналогичных швейных производствах, обеспечивая до 5-7% экономии ткани по длине при ее расчете в настилы.

Список литературы диссертационного исследования кандидат технических наук Мазанов, Павел Георгиевич, 2006 год

1. Акулич И. JI. Математическое программирование в примерах и задачах. М. Высшая школа, 1986.

2. Аравинд Кореа, Стивен Фрейзер и др. Visual С++.NET: пособие для разработчиков С++. М.: из-во "ЛОРИ", 2003 г.

3. Банди Б. Основы линейного программирования. Пер. с англ. М. Радио и связь, 1989.

4. Бошемин Боб., Основы ADO.NET. М.: изд. д. "Вильяме", 2003г.

5. Буч УГ- Объектно-оринетированный анализ и проектирование м примерами приложений на С++, 2-е изд., Спб., М.: изд-во "Невский диалект", "Бином", 1999г.

6. Валеева А.Ф., Гареев И.Р., Мухачева Э.А. Задача одномерной упаковки: рандомизированный метод динамического перебора и метод перебора с усечением. Информационные технологии. Приложение, 2003г., №2, с.2-3.

7. Вентцель Е.С. Исследование операций. М. "Советское радио", 1972.

8. Вилдермьюс Шон. Практическое использование ADO.NET. Доступ к данным в Internet., М.: изд. д. "Вильяме", 2003г.

9. Еремеев А.В., Заозерская Л.А., Колоколов А.А. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования. INTAS проект 96-0820, ФМЦ "Интеграция".

10. Золотых Н.Ю. Нахождение вершин выпуклой оболочки целочисленных точек полиэдра. 22 марта 2001, http://www.nic.nnov.ru/~zny.

11. Золотых Н.Ю. О числе крайних точек в задачах целочисленного линейного программирования. НГУ им. Н.И. Лобачевского, 1997, http://www.nic.nnov.ru/~zny.

12. Канторович Л.В., Залгаллер В.А. Расчет рационального раскрой материала. Лениздат. 1951.

13. Канторович Л.В., Залгаллер В.А. Рациональный раскрой промышленных материалов. Новосибирск: Наука. СО, 1971. 299 с.

14. Коммерсант Власть, №44, 6 ноября 2001 г., http://www.inno.ru/projects/show/?id=761.

15. Комплексная система BestCut оптимальный раскрой листовых материалов. http://www.vrsoft.msk.ru/.

16. Кочетов Ю.А., Глебов Н.И., Плясунов А.В. Методы оптимизации. Новосибирск, Новосибирский Государственный Университет, 2000, http://www2.sscc.ru/Publikacii/kvpparalI.htm.

17. Кочетов Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации. Институт математики им. С.Л. Соболева СО РАН, Новосибирск.

18. Круглински Д., Уингоу С., Шеферд Дж. Программирование на Microsoft Visual С++ 6.0 для профессионалов., М.: изд-во "Русская редакция", 2001г.

19. Лейнекер Р. Энциклопедия Visual С++, Спб. изд-во "Питер", 1999г.

20. Мамаев Е., Шкарина Л. Microsoft SQL Server 2000 для профессионалов, Спб., Питер, 2001г.

21. Муртаф Б. Современное линейное программирование. Пер. с. англ. М. Мир, 1984.

22. Т 23. Мухачев а Э. А.,. Ермаченко А. И, Сиразетдинов Т. М., Жукова Т. Ю. Комплексалгоритмов и программ расчета гильотинного раскроя. Информационные технологии, 2004г., №8, с.18-25.

23. Мухачева А.С. Алгоритмы плотной упаковки прямоугольных объектов на базе аппроксимации линейным раскроем, г.Уфа, УГАТУ, 2001г.

24. Мухачева А.С. Генетический алгоритм поиска минимума в задачах двумерного гильотинного раскроя. Информационные технологии, 2001г., № 3, с.27-31.

25. Мухачева Э.А. Математическое обеспечение расчетов линейного и прямоуголного раскроя, м-лы всесоюз. семинара., г.Уфв, УФАИ, 1981г.

26. Мухачева Э.А. Методы локального поиска в дискретных задачах оптимального распределения ресурса. М-во образования РФ, УГАТУ, 2001г.

27. Мухачева Э.А. Рациональный раскрой промышленных материалов: применение АСУ., г. Москва, Машиностроение, 1984 г.

28. Мухачева Э.А., Валееева А.Ф., Картак В.М., Мухачева А.С. Модели и методы решения задач ортогонального раскроя и упаковки: аналитический обзор и новая технология блочных структур. Информационные технологии. 2004г. №5, приложение №5, с.2.

29. Мухачева Э.А., Верхотуров М.А., Мартынов В.В. Модели и методы рачета раскроя-упаковки геометрических объектов, г.Уфа, УГАТУ, 1998г.

30. Мухачева Э.А., Принятие решений в условиях неопределенности: межвуз. науч. сб., М-во общ. и проф. образ. РФ, г.Уфа, УГАТУ, 1999г.

31. Мухачева Э.А., Рубенштейн Г.Ш. Математическое программирование, АН СССР, Сиб. отд. Ин-т математики, г.Новосибирск, Наука, 1987г.

32. Мюллер Дж. Технология СОМ+: библиотека программиста, Спб., Питер, 2002 г.1. Г'

33. Новикова Н.М. Основы оптимизации: курс лекций. Москва, ВМиК МГУ, РФФИ No. 96-1-00786, 1998.

34. Оберг Роберт Дж., Технология СОМ+. Соновы и программирование. М.: "Вильяме", 2000г.

35. Оберг Роберт Дж., Торстейнсон, Архитектура .NET и программирование с помощью Visual С++, М.: изд. д. "Вильяме", 2002г.

36. Пол А. Объектно-ориентированное пограммировагие на С++, 2-е изд, Спб., М.: изд-во "Невский диалект", "Бином", 1999г.

37. Рихтер Дж., Кларк Дж. Программирование серверных приложений для Microsoft Windows 2000, Спб, питер, М. "Русская редакция", 2001г.

38. Родженсон Д. Основы СОМ, М.: из-во "Русская редакция", 2000г.

39. Романовский И.В. Алгоритмы решения экстремальных задач. Москва, Наука, 1977г.

40. Страуструп Б. Язык программирования С++. М. Binom, 1999г.

41. Хендерсон К. Профессиональное руководство по SQL Server: хранимые процедуры, XML, HTML, Спб, Питер, 2005г.

42. Хендерсон К. Профессиональное руководство по Transact-SQL, Спб, Питер, 2005г.

43. Шайтхауер Г. Планирование одноиерного раскроя материала различной длинны на базе непрервыной релаксации и метода отсекающих плоскостей. Информационные технологии, 2004г., №1, с. 16-26

44. Шаммас Н.К. Основы С++ и объектно-ориентированного программирования., Киев, Диалектика, 1996г.

45. Эш Рофейл, Яссер Щохауд. СОМ и СОМ+. Полное руководство, К.: НТИ, М.: Энтроп, 2000г.

46. A. de Bruin, G.A.P. Kindervater, H.W.J.M. Trienekens. Asynchronous Parallel Branch and Bound and Anomalies. Erasmus University, Department of Computer Science, Rotterdam, The Netherlands, September, 1995.

47. Andersen E.D., Andersen K.D. Presolving in linear programming, Mathematical Programming # 71/2,1995, c.221-245.

48. Barbara M. Smith, Sally C. Brailsford, Peter M. Hubbard. The Progressive Party Problem: Integer Linear Programming and Constraint Programming Compared. Division of Artificial Intelligence. University of Leeds, University of Southampton.I-г

49. Branch and Bound. NEOS Guide Branch and Bound. http://www-fp.rncs.anl.gov/otc/Guide/OptWeb/discrete/integerprog/section2 1 1 .html.

50. Brian Borchers. Improved Branch and Bound Algorithm for Integer Programming. Faculty of Rensselaer Polytechnic Institute, Troy, NY, June 1992.

51. Dr. Ivan Oh. Linear Programming and Extensions. Bohazici University.

52. Dyckhoff H. A typology of cutting and packing problems. F.R. Germany, 1991r.

53. E. Balas, S. Cerria, G. Cornuejols, N. Natraj. Gomory Cuts Revisited. CGIA, Carnegie Mellon University, Graduate school of Business, Columbia University, US West Technologies, Bounlder, August 9,1994, revised April 16,1995.

54. E. Levitin, R. Tichatschke. A Branch-and-Bound Approach for Solving a Class of Generalized Semi-Infinite Programming Problems. Institute of System Analysis, Russian Academy of Science, Department of Mathematics, University of Tier.

55. Erling D. Andersen. Linear Optimization: Theory, Methods, and extensions. Department of Management, Odense University, Denmark, January 13, 1998.

56. Gabrielle Assunta Grun. Improving Integer Programming Branch and Bound Node Selection Techniques through Artificial Intelligence Methods. School of Computing Science, Simon Fraser University, Burnaby, March 14,2001.-r—''

57. H. Marchand, Alexander Martin, Robert Weismantel, Laurence Wolsey. Cutting Planes in Integer and Mixed Integer Programming. Department of Operational Research of London Scholl of Economics, Konrad-Zuse-Zentrum, October, 1999.

58. H. Marchand, Laurence A. Wolsey. Aggregation and Mixed Integer Rounding to Solve MIPs. June, 1998.

59. Harvey J. Greenberg. An Example of Cycling in the Simplex Method. University of Colorado at Denver, December 18,1998, http://www.cudenver.edu/~hgreenbe.

60. Herbert S. Wilf. Algorithm and Complexity. University of Pennsylvania, Philadelphia, Internet Edition, summer, 1994, http://www.cis.upenn.edu/wilf.

61. ILOG CPLEX Optimization Suite, White Paper, ILOG, May 2001, http://www.cplex.com. ■j 65] Integer Programming. NEOS Guide Integer Programming. http://wwwfp.mcs. anl.gov/otc/Guide/SoftwareGuide/Categories/intprog.html.1-у1. Г'

62. Istvan Maros. A General Pricing Scheme for the Simplex Method. Department of Computing Imperial College, London, ISSN 1469-4174, Department Technical Report 2001/3, March 2001.

63. Istvan Maros. A Generalized Dual Phase-2 Simplex Algorithm. Department of Computing Imperial College, London, ISSN 1469-4174, Department Technical Report 2001/2. January, 2001.

64. J. Balasubramanian, L.E. Grossmann. A Novell Branch and Bound Algorithm for Scheduling Flowshop Plants with Uncertain Processing Times. Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, January 2001 /August 2001.

65. J. Gondzio, R. Sarkissain and J.-Ph. Vial. Parallel implementation of a central decomposition method for solving large-scale planning problems. НЕС Technical Report 98.1 January 19,1998, revised August 12,1999.

66. J.T. Linderoth, M.W.P. Savelsbergh. A Computing Study of Search Strategies for Mixed Integer Programming. School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, October, 1997.

67. Jean-Pierre Goux, Sven Leyffer. Solving Large MINLPs on Computational Grids. Department of Mathematics, University of Dundee, 24 May, 2000.

68. Jens Clausen. Branch and Bounds Algorithm Principles and Examples. Department of Computer Science, University of Copenhagen, March 12, 1999.

69. John E. Mitchell, Eva K. Lee. Branch-and-bound methods for integer programming, in the Encyclopedia of Optimization, Kluwer Academic Publishers, August 2001, http ://www. rpi. edu/~m i tchj/papers .htm 1.

70. John E. Mitchell, Kartik Krishnan. A linear programming approach to semi definite programming problems, May 2001.

71. John Е. Mitchell. Branch-and-cut algorithms for integer programming, in the Encyclopedia of Optimization. Kluwer Academic Publishers, August 2001, http://www.rpi.edu/~mitchj/papers.html.

72. John E. Mitchell. Branch-and-cut methods for combinatorial optimization problems, in the Handbook of Applied Optimization, Oxford University Press, 2002, http://www.rpi.edu/~mitchj/papers.html.

73. John E. Mitchell. Cutting plane algorithms for integer programming, in the Encyclopedia of Optimization. Kluwer Academic Publishers, August 2001, http://www.rpi.edu/~mitchj/papers.html.

74. John E. Mitchell. Polynomial interior point cutting plane methods. Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY, July 16, 2001, http://www.rpi.edu/~mitchj/papers.html

75. John W. Chinneck. Practical Optimization: a Gentle Introduction. Carleton University, http://www.sce.carleton.ca/faculty/chinneck/po.html.

76. Jonathan Bard. Summary of Branch and Bound Methodology using LP Relaxation. The University of Texas, November 17,2001.

77. Karen Aardal, Stan van Hoesel. Polyhedral Techniques in Combinatorial Optimization I: Theory. Department of Computer Science, Utrecht University, Department of Quantitative Economics, Limburg University.

78. Katta G. Murty, Feig-Tien Yu. Linear Complementarity, Linear and Nonlinear Programming. Internet Edition. Department of Industrial and Operations Engineering, University of Michigan, 1997, http://www.personal.engin.umich.edu/~murty.

79. Katta G. Murty. Integer Programming and Combinatorial Optimization. IOE 614, http://www.personal.engin.umich.edu/~murtLP Theory, Cambridge University, http://www.statslab.cam.ac.uk/~rrwl/mor.

80. Katta G. Murty. Operations Research. IOE 510, http://www.personal.engin.umich.edu/~murty.

81. Lieven Vandenbergh, Stephen Boy, Mehrdad Nouralishahi. Robust Linear Programming and Optimal Control. Electrical Engineering Department, UCLA, Electrical Engineering Department, Stanford University.

82. Linear Programming Frequently Asked Questions (FAQ). Optimization Technology Center of Northwestern University and Argonne National Laboratory. http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html

83. LP Book, Princeton University. http://www.princeton.edu/~rvdb/LPbook/probs/index.html.

84. M.W.P. Savelsbergh. Preprocessing and Probing Techniques for Mixed Integer Programming Problems. School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta.

85. NEOS Guide CPLEX. http://www-fp.mcs.anl.gov/otc/Guide/SoftwareGuide/Blurbs/cplex.html.

86. Notes in Applied Integer Programming, April 12,2002.

87. OR-Notes J. E. Beasley. Integer programming formulation examples. http://mscmga.ms.ic.ac.uk/ieb/or/moreip.html.

88. OR-Notes J. E. Beasley. Integer programming, http://mscmga.ms.ic.ac.uk/jeb/or/ip.html.

89. Qun Chen, Michael C. Ferris. FATCOP: A Fault Tolerant Condor-PVM Mixed Integer Program Solver. Department of Industrial Engineering, Department of Computer Sciences, University of Wisconsin-Madison. March 17, 1999.

90. Robert E. Bixby, Mary Fenelon, Ronald Wunderling. Linear & Integer Programming: A Decade of Computation.

91. Robert E. Bixby. MIP: Theory and Practice Closing the Gap. ILOG CPLEX Division, Department of Computational and Applied Mathematics, Rice University, Houston, Mary Fenelon, ILOG CPLEX Division and etc.

92. Robert J. Vanderbei. Linear Programming: Foundation and Extensions. Department of Operations Research and Financial Engineering, Princeton University.

93. Robert J. Vanderbei. ORF 307. Operations Research and Financial Engineering, Princeton University, February 5,2002 http://www.princeton.edu/~rvdb/307/lectures.html.

94. Robert M. Freud, Shinji Mizuno. Interior Point Methods: Current Status and Future Directions. The Institute of Statistical Mathematics, Tokyo, October 1, 1996, revised December 5,1997.

95. S. Ceria, C. Cordier, H. Marchand, L.A. Wolsey. Cutting Planes for Integer Programs with General Integer Variables. Graduate school of Business, Columbia University, December 23,1995.

96. Sourour Elloumi, Martine Labbe, Yves Pochet. New Formulation and Resolution of Method for the p-Center Problem. December, 2001.

97. Stan Lao, Srinivas Devadas. Solving Covering Problems Using LRP-Based Lower Bounds. Advanced Technology Group, Synopsys Inc., Department of EECS, MIT.

98. Steve Hurder. Overview of the simplex method.

99. Ted Ralphs. IE316 Course Advanced Operations Research Techniques. http://www.lehigh.edu/~tkr2.

100. Ted Ralphs. IE418 Course Discrete Optimization, http://www.lehigh.edu/~tkr2.

101. Terno J., Linderman R., Scheithauer G. Zuschinitprobleme und ihre praktische Losung. Leipzig, 1987.

102. Xin Huang. Preprocessing and Postprocessing in Linear Optimiztion. McMaster University, June 2004.r