Spelling suggestions: "subject:"interiorpoint"" "subject:"interpoint""
11 |
Advanced Interior Point Formulation for the Global Routing ProblemWong, David C. 23 April 2009 (has links)
As the circuit size increases in modern electronics, the design process becomes more complicated. Even though the hardware design process is divided into multiple phases, many of the divided problems are still extremely time consuming to solve. One of these NP-hard problems is the routing problem. As electronics step into the deep submicron era, optimizing the routing becomes increasingly important.
One of the methods to solve global routing is to formulate the problem as an integer programming (IP) problem. This formulation can then be relaxed into a linear programming problem and solved using interior point method. This thesis investigates two new approaches to optimize the speed of solving global routing using Karmarkar’s interior point method, as well as the effect of combining various optimizations with these new approaches. The first proposed approach is to utilize solution stability as the interior point loop converges, and attempt to remove solutions that have already stabilized. This approach reduces the problem size and allows subsequent interior point iterations to proceed faster. The second proposed approach is to solve the inner linear system (projection step) in interior point method in parallel.
Experimental results show that for large routing problems, the performance of the solver is improved by the optimization approaches. The problem reduction stage allows for great speedup in the interior point iterations, without affecting the quality of the solution significantly. Furthermore, the timing required to solve inner linear system in the interior point method is improved by solving the problem in parallel. With these optimizations, solving the routing problem using the IP formation becomes increasingly more efficient. By solving an efficient parallel IP formation rather than a traditional sequential approach, more efficient optimal solutions which incorporate multiple conflicting objectives can be achieved.
|
12 |
Interior-Point Algorithms Based on Primal-Dual EntropyLuo, Shen January 2006 (has links)
We propose a family of search directions based on primal-dual entropy in the context of interior point methods for linear programming. This new family contains previously proposed search directions in the context of primal-dual entropy. We analyze the new family of search directions by studying their primal-dual affine-scaling and constant-gap centering components. We then design primal-dual interior-point algorithms by utilizing our search directions in a homogeneous and self-dual framework. We present iteration complexity analysis of our algorithms and provide the results of computational experiments on NETLIB problems.
|
13 |
Advanced Interior Point Formulation for the Global Routing ProblemWong, David C. 23 April 2009 (has links)
As the circuit size increases in modern electronics, the design process becomes more complicated. Even though the hardware design process is divided into multiple phases, many of the divided problems are still extremely time consuming to solve. One of these NP-hard problems is the routing problem. As electronics step into the deep submicron era, optimizing the routing becomes increasingly important.
One of the methods to solve global routing is to formulate the problem as an integer programming (IP) problem. This formulation can then be relaxed into a linear programming problem and solved using interior point method. This thesis investigates two new approaches to optimize the speed of solving global routing using Karmarkar’s interior point method, as well as the effect of combining various optimizations with these new approaches. The first proposed approach is to utilize solution stability as the interior point loop converges, and attempt to remove solutions that have already stabilized. This approach reduces the problem size and allows subsequent interior point iterations to proceed faster. The second proposed approach is to solve the inner linear system (projection step) in interior point method in parallel.
Experimental results show that for large routing problems, the performance of the solver is improved by the optimization approaches. The problem reduction stage allows for great speedup in the interior point iterations, without affecting the quality of the solution significantly. Furthermore, the timing required to solve inner linear system in the interior point method is improved by solving the problem in parallel. With these optimizations, solving the routing problem using the IP formation becomes increasingly more efficient. By solving an efficient parallel IP formation rather than a traditional sequential approach, more efficient optimal solutions which incorporate multiple conflicting objectives can be achieved.
|
14 |
Interior Point Cutting Plane Methods in Integer ProgrammingNaoum-Sawaya, Joe January 2011 (has links)
This thesis presents novel approaches that use interior point concepts in solving mixed integer programs. Particularly, we use the analytic center cutting plane method to improve three of the main components of the branch-and-bound algorithm: cutting planes, heuristics, and branching.
First, we present an interior point branch-and-cut algorithm for structured integer programs based on Benders decomposition. We explore using Benders decomposition in a branch-and-cut framework where the Benders cuts are generated using the analytic center cutting plane method. The algorithm is tested on two classes of problems: the capacitated facility
location problem and the multicommodity capacitated fixed charge network design
problem. For
the capacitated facility location problem, the proposed approach was on average
2.5 times faster than Benders-branch-and-cut and 11 times faster than classical
Benders decomposition. For the multicommodity capacitated fixed charge network
design problem, the proposed approach was 4 times faster than Benders-branch-and-cut while classical Benders decomposition failed to solve the
majority of the tested instances.
Second, we present a heuristic algorithm for mixed integer programs based on interior points. As integer solutions
are typically in the interior, we use the analytic center cutting plane method to search for integer feasible points within the interior
of the feasible set. The
algorithm searches along two line segments that connect
the weighted analytic center and two extreme points of the linear
programming relaxation. Candidate points are rounded and
tested for feasibility. Cuts aimed to improve the objective function
and restore feasibility are then added to displace the weighted
analytic center until a feasible integer solution is found. The algorithm is composed of three phases. In the first, points along
the two line segments are rounded gradually to find integer feasible
solutions. Then in an attempt to improve the quality of the solutions, the cut related to the bound constraint is updated
and a new weighted analytic center is found. Upon failing to find a
feasible integer solution, a second phase is started where cuts
related to the violated feasibility constraints are added. As a last resort, the
algorithm solves a minimum distance problem in a third phase. For all the tested instances, the algorithm finds good quality feasible solutions in the first two phases and the third phase is never called.
Finally, we present a new approach to generate good general branching constraints based on the shape of the polyhedron. Our approach is based on approximating the polyhedron using an inscribed ellipsoid. We use Dikin's ellipsoid which we calculate using the analytic center. We propose to use the disjunction that has a minimum width on the ellipsoid. We use the fact that the width of the ellipsoid in a given direction has a closed form solution in order to formulate a quadratic problem whose optimal solution is a thin direction of the ellipsoid. While solving a quadratic problem at each node of the branch-and-bound tree is impractical, we use a local search heuristic for its solution. Computational testing conducted on hard integer problems from MIPLIB and CORAL showed that the proposed approach outperforms classical branching.
|
15 |
On inexact Newton directions in interior point methods for linear optimizationAl-Jeiroudi, Ghussoun January 2009 (has links)
In each iteration of the interior point method (IPM) at least one linear system has to be solved. The main computational effort of IPMs consists in the computation of these linear systems. Solving the corresponding linear systems with a direct method becomes very expensive for large scale problems. In this thesis, we have been concerned with using an iterative method for solving the reduced KKT systems arising in IPMs for linear programming. The augmented system form of this linear system has a number of advantages, notably a higher degree of sparsity than the normal equations form. We design a block triangular preconditioner for this system which is constructed by using a nonsingular basis matrix identified from an estimate of the optimal partition in the linear program. We use the preconditioned conjugate gradients (PCG) method to solve the augmented system. Although the augmented system is indefinite, short recurrence iterative methods such as PCG can be applied to indefinite system in certain situations. This approach has been implemented within the HOPDM interior point solver. The KKT system is solved approximately. Therefore, it becomes necessary to study the convergence of IPM for this inexact case. We present the convergence analysis of the inexact infeasible path-following algorithm, prove the global convergence of this method and provide complexity analysis.
|
16 |
Interior Point Cutting Plane Methods in Integer ProgrammingNaoum-Sawaya, Joe January 2011 (has links)
This thesis presents novel approaches that use interior point concepts in solving mixed integer programs. Particularly, we use the analytic center cutting plane method to improve three of the main components of the branch-and-bound algorithm: cutting planes, heuristics, and branching.
First, we present an interior point branch-and-cut algorithm for structured integer programs based on Benders decomposition. We explore using Benders decomposition in a branch-and-cut framework where the Benders cuts are generated using the analytic center cutting plane method. The algorithm is tested on two classes of problems: the capacitated facility
location problem and the multicommodity capacitated fixed charge network design
problem. For
the capacitated facility location problem, the proposed approach was on average
2.5 times faster than Benders-branch-and-cut and 11 times faster than classical
Benders decomposition. For the multicommodity capacitated fixed charge network
design problem, the proposed approach was 4 times faster than Benders-branch-and-cut while classical Benders decomposition failed to solve the
majority of the tested instances.
Second, we present a heuristic algorithm for mixed integer programs based on interior points. As integer solutions
are typically in the interior, we use the analytic center cutting plane method to search for integer feasible points within the interior
of the feasible set. The
algorithm searches along two line segments that connect
the weighted analytic center and two extreme points of the linear
programming relaxation. Candidate points are rounded and
tested for feasibility. Cuts aimed to improve the objective function
and restore feasibility are then added to displace the weighted
analytic center until a feasible integer solution is found. The algorithm is composed of three phases. In the first, points along
the two line segments are rounded gradually to find integer feasible
solutions. Then in an attempt to improve the quality of the solutions, the cut related to the bound constraint is updated
and a new weighted analytic center is found. Upon failing to find a
feasible integer solution, a second phase is started where cuts
related to the violated feasibility constraints are added. As a last resort, the
algorithm solves a minimum distance problem in a third phase. For all the tested instances, the algorithm finds good quality feasible solutions in the first two phases and the third phase is never called.
Finally, we present a new approach to generate good general branching constraints based on the shape of the polyhedron. Our approach is based on approximating the polyhedron using an inscribed ellipsoid. We use Dikin's ellipsoid which we calculate using the analytic center. We propose to use the disjunction that has a minimum width on the ellipsoid. We use the fact that the width of the ellipsoid in a given direction has a closed form solution in order to formulate a quadratic problem whose optimal solution is a thin direction of the ellipsoid. While solving a quadratic problem at each node of the branch-and-bound tree is impractical, we use a local search heuristic for its solution. Computational testing conducted on hard integer problems from MIPLIB and CORAL showed that the proposed approach outperforms classical branching.
|
17 |
Interior point methods for multicommodity network flowsTorres Guardia, Luis Ernesto, Alvez Lima, Gilson 25 September 2017 (has links)
This article studies the linear multicommodity network flow problem. This kind of problem arises in a wide variety of contexts. A numerical implementation of the primal-dual interior-point method is designed to solve the problem. In the interior-point method, at each iteration, the corresponding linear system, expressed as a normal equations system, is solved by using the AINV algorithm combined with a preconditioned conjugate gradient algorithm or by the AINV algorithm for the whole normal equations. Numerical experiments are conducted for networks of different dimensions and numbers of products for the distribution problem. The computational results show the effectiveness of the interior-point method for this class of network problems.
|
18 |
Strategie volby kroku a jeho délky u vybraných metod vnitřního bodu / Interior Point MethodsMatoušová, Hana January 2010 (has links)
In the present work we study Interior Point Algorithm used for solving linear problems
|
19 |
Solving convex programming with simple convex constraintsHou, Liangshao 09 July 2020 (has links)
The problems we studied in this thesis are linearly constrained convex programming (LCCP) and nonnegative matrix factorization (NMF). The resolutions of these two problems are all closely related to convex programming with simple convex constraints. The work can mainly be described in the following three parts. Firstly, an interior point algorithm following a parameterized central path for linearly constrained convex programming is proposed. The convergence and polynomial-time complexity are proved under the assumption that the Hessian of the objective function is locally Lipschitz continuous. Also, an initialization strategy is proposed, and some numerical results are provided to show the efficiency of the proposed algorithm. Secondly, the path following algorithm is promoted for general barrier functions. A class of barrier functions is proposed, and their corresponding paths are proved to be continuous and converge to optimal solutions. Applying the path following algorithm to these paths provide more flexibility to interior point methods. With some adjustments, the initialization method is equipped to validate implementation and convergence. Thirdly, we study the convergence of hierarchical alternating least squares algorithm (HALS) and its fast form (Fast HALS) for nonnegative matrix factorization. The coordinate descend idea for these algorithms is restated. With a precise estimation of objective reduction, some limiting properties are illustrated. The accumulation points are proved to be stationary points, and some adjustments are proposed to improve the implementation and efficiency
|
20 |
An open source object oriented platform for rapid design of high performance path following interior-point methodsChiş, Voicu January 2008 (has links)
<p> Interior point methods (IPMs) is a powerful tool in convex optimization. From
the theoretical point of view, the convex set of feasible solutions is represented
by a so-called barrier functional and the only information required by the
algorithms is the evaluation of the barrier, its gradient and Hessian. As a
result, IPM algorithms can be used for many types of convex problems and
their theoretical performance depends on the properties of the barrier. In
practice, performance depends on how the data structure is exploited at the
linear algebra level. In this thesis, we make use of the object-oriented paradigm
supported by C++ to create a platform where the aforementioned generality
of IPM algorithms is valued and the possibility to exploit the data structure
is available. We will illustrate the power of such an approach on optimization
problems arrising in the field of Radiation Therapy, in particular Intensity
Modulated Radiation Therapy. </p> / Thesis / Master of Science (MSc)
|
Page generated in 0.0764 seconds