REPORT A PROBLEMicon

Fields marked with an asterisk are required
*
*
*
*
captcha
I hereby confirm that I have read and accept regulations and privacy policies *

LINKS

Resource link (portal)

Resource link (repository)

https://id.e-science.pl/records/21569

Resource type: thesis

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

View

Resource metadata

Title Efektywność metody płaszczyzn odcinających w programowaniu całkowitoliczbowym
Title variant: On efficiency of the cutting plane method in integer programming
Persons Authors: Ignacy Stanisław Kaliszewski
Partner: Systems Research Institute Polish Academy of Sciences, Warsaw
Description 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. (Polish)
Description in another language: 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. (English)
Keywords "modelowanie matematyczne"@pl, "programowanie całkowitoliczbowe"@pl, "metoda odcięć"@pl, "powłoka wypukła"@pl
Classification Resource type: thesis
Scientific discipline: dziedzina nauk technicznych / automatyka i robotyka (2011)
Destination group: scientists, students, entrepreneurs
Harmful content: No
Characteristics Place of creation: Warszawa
Creation time: 1979
Number of pages: 192
Supervisor: Stanisław Walukiewicz
Resource language: Polish
Location: Warszawa
License CC BY-SA 4.0
Technical information Submitter: Justyna Kupczak
Availability date: 16-10-2018
Collections Kolekcja Instytutu Badań Systemowych PAN w Warszawie, Kolekcja e-Biblio IBS PAN

Citation

Copied

Ignacy Stanisław Kaliszewski. Efektywność metody płaszczyzn odcinających w programowaniu całkowitoliczbowym. [thesis] Available in Atlas of Open Science Resources, . License: CC BY-SA 4.0, https://creativecommons.org/licenses/by-sa/4.0/legalcode.pl. Date of access: DD.MM.RRRR.

Similar resources

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

Jakub Gutenbaum, article, chapter, Systems Research Institute Polish Academy of Sciences, Warsaw, 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, article, chapter, Systems Research Institute Polish Academy of Sciences, Warsaw, Dziedzina nauk społecznych / ekonomia i finanse (2018)

Water treatment technology: principles and modeling

Wojciech Adamski, Małgorzata Szlachta, book, Wrocław University of Science and Technology, 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, thesis, Systems Research Institute Polish Academy of Sciences, Warsaw, dziedzina nauk technicznych / informatyka (2011)

See more