Back to search

University of Patras

Νέες τεχνικές ανίχνευσης δεσμευτικών περιορισμών σε προβλήματα γραμμικού προγραμματισμού και εφαρμογές

Abstract

dc:description

In 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

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/57291

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Tsarmpopoulos, Dimitrios; Τσαρμπόπουλος, Δημήτριος. Νέες τεχνικές ανίχνευσης δεσμευτικών περιορισμών σε προβλήματα γραμμικού προγραμματισμού και εφαρμογές. University of Patras, 2024. http://hdl.handle.net/10442/hedi/57291