Efektywność metody płaszczyzn odcinających w programowaniu całkowitoliczbowym

Widok

Metadane zasobu

Tytuł	Efektywność metody płaszczyzn odcinających w programowaniu całkowitoliczbowym Wariant tytułu: On efficiency of the cutting plane method in integer programming
Osoby	Autorzy: Ignacy Stanisław Kaliszewski Partner: Instytut Badań Systemowych PAN w Warszawie
Opis	Celem rozprawy jest zwiększenie efektywności metody płaszczyzn odcinających poprzez wykorzystanie idei modyfikacji ograniczeń w zastosowaniu do zadań programowania całkowitoliczbowego liniowego. Założeniem roboczym jest przypuszczenie, że zręczne włączenie tej idei w schemat odpowiednio zaprojektowanego algorytmu płaszczyzn odcinających pozwala na zyskanie znacznych oszczędności w czasach rozwiązywania zadań. Szczególną uwagę poświęcono zagadnieniu wyboru metody modyfikacji ograniczeń i jego wpływowi na zbieżność algorytmów. Sformułowano ogólny problem modyfikacji opisu zbioru rozwiązań dopuszczalnych i wykazano, że z praktycznego punktu widzenia jego pełne rozwiązanie nie jest interesujące. W rozprawie przedstawiono i przebadano dwie znane metody modyfikacji pojedynczych ograniczeń (w tym metodę obrotów ograniczeń) oraz zaproponowano metodę nową. Dla metody obrotów ograniczeń zidentyfikowano i udowodniono nieznane dotychczas własności oraz zaproponowano jej istotne algorytmiczne ulepszenie zwiększające efektywność rozwiązywania zadań programowania całkowitoliczbowego liniowego. Pokazano też, w jaki sposób proces obrotu ograniczenia może stanowić źródło informacji o rozwiązaniach dopuszczalnych danego problemu, jak również, że stosowanie metod modyfikacji ograniczeń prowadzi do cząstkowych rozwiązań zagadnienia wrażliwości dla zadań programowania całkowitoliczbowego liniowego. Eksperymenty numeryczne zostały przeprowadzone przy zastosowaniu zaproponowanej metody obrotu ograniczeń i algorytmu płaszczyzn odcinających Gomory’ego. (Polski) Opis w innym języku: The aim of the thesis is to increase efficiency of the cutting plane method by exploiting the idea of constraint modifications in the integer linear programming. The working hypothesis is that coupling this idea into a specially structured cutting plane algorithm results in significant savings in computing time. In the thesis much efforts have been devoted to the problem of selecting the method of constraint modifications and its influence on algorithm convergence. A general problem of modification of the feasible set description is formulated. It is been shown that from the practical point of view its exact solution is not of interest. Two methods of constraint modifications known from the literature (one is the constraint rotation method) are presented and a new method is proposed. For the constraint rotation method new properties are identified and proved, and its significant algorithmic improvements increasing the efficiency of solving integer linear programming problems are proposed. It is also shown that the process of constraint rotation can be a source of information on feasible solutions of a given problem and that the constraint modification methods solve some sensitivity integer linear programming issues. Numerical experiments have been conducted for the proposed constraint rotation method and the cutting plane Gomory algorithm. (Angielski)
Słowa kluczowe	"modelowanie matematyczne"@pl, "programowanie całkowitoliczbowe"@pl, "metoda odcięć"@pl, "powłoka wypukła"@pl
Klasyfikacja	Typ zasobu: praca dyplomowa Dyscyplina naukowa: dziedzina nauk technicznych / automatyka i robotyka (2011) Grupa docelowa: naukowcy, studenci, przedsiębiorcy Szkodliwe treści: Nie
Charakterystyka	Miejsce powstania: Warszawa Czas powstania: 1979 Liczba stron: 192 Promotor: Stanisław Walukiewicz Język zasobu: Polski Lokalizacja: Warszawa
Licencja	CC BY-SA 4.0
Informacje techniczne	Deponujący: Justyna Kupczak Data udostępnienia: 16-10-2018
Kolekcje	Kolekcja Instytutu Badań Systemowych PAN w Warszawie, Kolekcja e-Biblio IBS PAN

Cytowanie

Skopiowano

Ignacy Stanisław Kaliszewski. Efektywność metody płaszczyzn odcinających w programowaniu całkowitoliczbowym. [praca dyplomowa] Dostępny w Atlasie Zasobów Otwartej Nauki, . Licencja: CC BY-SA 4.0, https://creativecommons.org/licenses/by-sa/4.0/legalcode.pl. Data dostępu: DD.MM.RRRR.

Podobne zasoby

Komputerowe wspomaganie decyzji w systemach gospodarki wodno-ściekowej. The use of mathematical models of the wastewater purification process for computer-aided decision making (RB-2000-46-06)

Jan Studziński, artykuł, rozdział, Instytut Badań Systemowych PAN w Warszawie, dziedzina nauk technicznych / inżynieria środowiska (2011)

Co mamy do powiedzenia specjalistom od gospodarki (RB-1994-93)

Jakub Gutenbaum, artykuł, rozdział, Instytut Badań Systemowych PAN w Warszawie, dziedzina nauk ekonomicznych / nauki o zarządzaniu (2011)

Komputerowa realizacja systemu analizy wariantów inwestycyjnych decyzji kredytowych (PN-1986-06)

Ignacy Kaliszewski, Grażyna Grygiel, Leon Słomiński, artykuł, rozdział, Instytut Badań Systemowych PAN w Warszawie, Dziedzina nauk społecznych / ekonomia i finanse (2018)

Water treatment technology: principles and modeling

Wojciech Adamski, Małgorzata Szlachta, książka, Politechnika Wrocławska, dziedzina nauk technicznych / inżynieria środowiska (2011)

Uczenie maszynowe na podstawie przykładów w przypadku błędów w danych

Grażyna Szkatuła, praca dyplomowa, Instytut Badań Systemowych PAN w Warszawie, dziedzina nauk technicznych / informatyka (2011)

Modelowanie matematyczne i eksperymentalna weryfikacja procesu impulsowego zagęszczania mas formierskich

Daniel Nowak, praca dyplomowa, Politechnika Wrocławska, dziedzina nauk technicznych / mechanika (2011)

Zobacz więcej