|
|
Interval linear programming
Garajová, Elif ; Hladík, Milan (advisor) ; Kearfott, Ralph Baker (referee) ; Bartl, David (referee)
Interval linear programming provides a modern approach for handling optimization problems affected by various sources of interval-valued uncertainty. Given lower and upper bounds on the inexact data, the model represents a set of linear programs with coefficients that can be independently perturbed within the respective ranges. The thesis forms a systematic study of the optimality properties of interval linear programs and their solutions. Building on the existing research, we present a compilation of results published by the author, which fill in some of the gaps in the state-of-the-art literature on interval programming. We first examine the effects of standard transformations used in linear programming on the optimal solutions and optimal values of interval programs. Then, we characterize the properties of feasibility, optimality and (un)boundedness in the weak and in the strong sense (i.e. whether a property holds for some or for each scenario) and we analyze computational complexity of the associated decision problems. Further, we focus on the optimal solutions and prove that several related decision problems are (co)NP-hard even for interval programs with a fixed constraint matrix. We also show an integer programming reformulation useful in computing the optimal value range and discuss other concepts...
|
|
|
Interval solver for nonlinear constraints
Garajová, Elif ; Hladík, Milan (advisor) ; Pergel, Martin (referee)
The thesis is focused on the Sivia algorithm (Set Inverter via Interval Ana- lysis) designed for solving a continuous constraint satisfaction problem using interval methods and propagation techniques. Basic properties of the algorithm are derived, including the correction of its presented complexity bound. Some improvements concerning the testing of constraint satisfaction and optimiza- tion of the number of interval boxes describing the solution are proposed. The thesis also introduces contractors used to enhance the effectivity of the Sivia algorithm by reducing the interval boxes processed. Presented algorithms were implemented in a solver for nonlinear constraints with a simple visualization of the result using the Matlab language. A comparison of basic contractors on specific examples is given.
|
|
|
Polygon map navigation
Navrátil, Šimon ; Pangrác, Ondřej (advisor) ; Garajová, Elif (referee)
Finding the shortest path is a well-researched area for discrete problems. However, not all problems can be directly described by a graph, and in orienteering the runner can choose the path whichever way he wants, but he has to choose the fastest one just from the map. This is made more complicated by the different speed in different areas between the control points. In order to find the optimal path, a continuous solution has to be found. This work describes how to get a polygonal representation of a map from a map file and how to search the fastest path in it using two different approaches. 1
|
|
|
The optimal solution set of interval linear programming problems
Garajová, Elif ; Hladík, Milan (advisor) ; Zimmermann, Karel (referee)
Determining the set of all optimal solutions of a linear program with interval data is one of the main problems discussed in interval optimization. We review two methods based on duality in linear programming, which are used to approximate the optimal set. Additionally, another decomposition method based on complementary slackness is proposed. This method provides the exact description of the optimal set for problems with a fixed coefficient matrix. The second part of the thesis is focused on studying the topological and geometric properties of the optimal set. We examine sufficient conditions for closedness, boundedness, connectedness and convexity. We also prove that testing boundedness is co- NP-hard for inequality-constrained problems with free variables. Stronger results are derived for some special classes of interval linear programs, such as problems with a fixed coefficient matrix. Furthermore, we study the effect of transformations commonly used in linear programming on interval problems, which allows for a direct generalization of some results to different types of interval linear programs. Powered by TCPDF (www.tcpdf.org)
|
|
|
Interval solver for nonlinear constraints
Garajová, Elif ; Hladík, Milan (advisor) ; Pergel, Martin (referee)
The thesis is focused on the Sivia algorithm (Set Inverter via Interval Ana- lysis) designed for solving a continuous constraint satisfaction problem using interval methods and propagation techniques. Basic properties of the algorithm are derived, including the correction of its presented complexity bound. Some improvements concerning the testing of constraint satisfaction and optimiza- tion of the number of interval boxes describing the solution are proposed. The thesis also introduces contractors used to enhance the effectivity of the Sivia algorithm by reducing the interval boxes processed. Presented algorithms were implemented in a solver for nonlinear constraints with a simple visualization of the result using the Matlab language. A comparison of basic contractors on specific examples is given.
|
guest ::
