|
|
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 ::
