University of Patras
Νέες τεχνικές ανίχνευσης δεσμευτικών περιορισμών σε προβλήματα γραμμικού προγραμματισμού και εφαρμογές
Abstract
dc:descriptionIn the real world, given the rapidly evolving circumstances that characterize the modern era, in the sectors of life where linear programming problems are met, an endless effort has been conducted by researchers, as well as by scientific organizations and businesses, to resolve them as quickly and as efficiently as possible. More specifically, it has been noticed that only a small part of the initial constraints participates in the optimal solution of the problem. This creates a necessity either to remove the redundant constraints, that do not participate in the optimal solution of those problems from the resolving process, or to locate the binding constraints that contribute to the optimal solution, before the resolution process. Due to the fact though, that the characterization of those constraints may be of increased difficulty, it is possible to use «proximity» techniques which are able to locate the more possible constraints to be classified in each category. Given the increased complexity of these problems, the present thesis focuses on the presentation of five new algorithms. Through the usage of specific prediction criteria, these algorithms are able to characterize the constraints as binding or non-binding, by focusing on the characterization of the binding ones, in order to reduce the dimension of the Linear Programming Problem (LP). This results in speeding up the solving process of the method used, and thus, reduces the resolution cost of the LP problem. Part of the presented algorithms are implemented in randomly created linear programming problems. Another part is implemented in a class of known Netlib problems of the real world, where the number of variables is significantly larger than the number of the constraints. This contrasts with the randomly created linear programming problems, where the opposite applies, while the last part of the remaining algorithms is implemented in the aforementioned cases. For the accomplishment of the classification of the constraints, the presented algorithms make use of a ranking system, which is calculated individually for each algorithm based on a specific criterion, that allows us to «characterize» the constraints as binding or redundant.
Degree
thesis:*- Grantor dc:publisher
- University of Patras
- Year dc:date
- 2024
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Tsarmpopoulos, Dimitrios
- Τσαρμπόπουλος, Δημήτριος
Subjects
dc:subject × 18- Γραμμικός προγραμματισμός
- Δεσμευτικοί περιορισμοί
- Μη-δεσμευτικοί περιορισμοί
- Τεχνική εγγύτητας
- Ταξινόμηση περιορισμών
- Ανίχνευση περιορισμών
- Linear programming
- Binding constraints
- Redundant constraints
- Proximity technique
- Constraint ranking
- Constraint detection
- Οικονομικά και Επιχειρήσεις
- Κοινωνικές Επιστήμες
- Διοικητική Επιστήμη και Επιχειρησιακή Έρευνα
- Economics and Business
- Social Sciences
- Management Science and Operations Research
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/57291