| 1. |
- Bernal, D. E., et al.
(författare)
-
Alternative regularizations for Outer-Approximation algorithms for convex MINLP
- 2022
-
Ingår i: Journal of Global Optimization. - : Springer Nature. - 0925-5001 .- 1573-2916. ; 84:4, s. 807-842
-
Tidskriftsartikel (refereegranskat)abstract
- In this work, we extend the regularization framework from Kronqvist et al. (Math Program 180(1):285–310, 2020) by incorporating several new regularization functions and develop a regularized single-tree search method for solving convex mixed-integer nonlinear programming (MINLP) problems. We propose a set of regularization functions based on distance metrics and Lagrangean approximations, used in the projection problem for finding new integer combinations to be used within the Outer-Approximation (OA) method. The new approach, called Regularized Outer-Approximation (ROA), has been implemented as part of the open-source Mixed-integer nonlinear decomposition toolbox for Pyomo—MindtPy. We compare the OA method with seven regularization function alternatives for ROA. Moreover, we extend the LP/NLP Branch and Bound method proposed by Quesada and Grossmann (Comput Chem Eng 16(10–11):937–947, 1992) to include regularization in an algorithm denoted RLP/NLP. We provide convergence guarantees for both ROA and RLP/NLP. Finally, we perform an extensive computational experiment considering all convex MINLP problems in the benchmark library MINLPLib. The computational results show clear advantages of using regularization combined with the OA method.
|
|
| 2. |
- Burdakov, Oleg, et al.
(författare)
-
Optimal placement of UV-based communications relay nodes
- 2010
-
Ingår i: Journal of Global Optimization. - : Springer. - 0925-5001 .- 1573-2916. ; 48:4, s. 511-531
-
Tidskriftsartikel (refereegranskat)abstract
- We consider a constrained optimization problem with mixed integer and real variables. It models optimal placement of communications relay nodes in the presence of obstacles. This problem is widely encountered, for instance, in robotics, where it is required to survey some target located in one point and convey the gathered information back to a base station located in another point. One or more unmanned aerial or ground vehicles (UAVs or UGVs) can be used for this purpose as communications relays. The decision variables are the number of unmanned vehicles (UVs) and the UV positions. The objective function is assumed to access the placement quality. We suggest one instance of such a function which is more suitable for accessing UAV placement. The constraints are determined by, firstly, a free line of sight requirement for every consecutive pair in the chain and, secondly, a limited communication range. Because of these requirements, our constrained optimization problem is a difficult multi-extremal problem for any fixed number of UVs. Moreover, the feasible set of real variables is typically disjoint. We present an approach that allows us to efficiently find a practically acceptable approximation to a global minimum in the problem of optimal placement of communications relay nodes. It is based on a spatial discretization with a subsequent reduction to a shortest path problem. The case of a restricted number of available UVs is also considered here. We introduce two label correcting algorithms which are able to take advantage of using some peculiarities of the resulting restricted shortest path problem. The algorithms produce a Pareto solution to the two-objective problem of minimizing the path cost and the number of hops. We justify their correctness. The presented results of numerical 3D experiments show that our algorithms are superior to the conventional Bellman-Ford algorithm tailored to solving this problem.
|
|
| 3. |
- Carling, Kenneth, et al.
(författare)
-
Confidence in heuristic solutions?
- 2015
-
Ingår i: Journal of Global Optimization. - : Springer Science and Business Media LLC. - 0925-5001 .- 1573-2916. ; 63:2, s. 381-399
-
Tidskriftsartikel (refereegranskat)abstract
- Solutions to combinatorial optimization problems frequently rely on heuristics to minimize an objective function. The optimum is sought iteratively and pre-setting the number of iterations dominates in operations research applications, which implies that the quality of the solution cannot be ascertained. Deterministic bounds offer a mean of ascertaining the quality, but such bounds are available for only a limited number of heuristics and the length of the interval may be difficult to control in an application. A small, almost dormant, branch of the literature suggests using statistical principles to derive statistical bounds for the optimum. We discuss alternative approaches to derive statistical bounds. We also assess their performance by testing them on 40 test p-median problems on facility location, taken from Beasley’s OR-library, for which the optimum is known. We consider three popular heuristics for solving such location problems; simulated annealing, vertex substitution, and Lagrangian relaxation where only the last offers deterministic bounds. Moreover, we illustrate statistical bounds in the location of 71 regional delivery points of the Swedish Post. We find statistical bounds reliable and much more efficient than deterministic bounds provided that the heuristic solutions are sampled close to the optimum. Statistical bounds are also found computationally affordable.
|
|
| 4. |
- Ding, Xiaosong, et al.
(författare)
-
Accelerating convergence of cutting plane algorithms for disjoint bilinear programming
- 2007
-
Ingår i: Journal of Global Optimization. - : Springer Science and Business Media LLC. - 0925-5001 .- 1573-2916. ; 38:3, s. 421-436
-
Tidskriftsartikel (refereegranskat)abstract
- This paper presents two linear cutting plane algorithms that refine existing methods for solving disjoint bilinear programs. The main idea is to avoid constructing (expensive) disjunctive facial cuts and to accelerate convergence through a tighter bounding scheme. These linear programming based cutting plane methods search the extreme points and cut off each one found until an exhaustive process concludes that the global minimizer is in hand. In this paper, a lower bounding step is proposed that serves to effectively fathom the remaining feasible region as not containing a global solution, thereby accelerating convergence. This is accomplished by minimizing the convex envelope of the bilinear objective over the feasible region remaining after introduction of cuts. Computational experiments demonstrate that augmenting existing methods by this simple linear programming step is surprisingly effective at identifying global solutions early by recognizing that the remaining region cannot contain an optimal solution. Numerical results for test problems from both the literature and an application area are reported.
|
|
| 5. |
- Ernestus, Maximilian, et al.
(författare)
-
Algorithms for art gallery illumination
- 2017
-
Ingår i: Journal of Global Optimization. - : SPRINGER. - 0925-5001 .- 1573-2916. ; 68:1, s. 23-45
-
Tidskriftsartikel (refereegranskat)abstract
- The art gallery problem (AGP) is one of the classical problems in computational geometry. It asks for the minimum number of guards required to achieve visibility coverage of a given polygon. The AGP is well-known to be NP-hard even in restricted cases. In this paper, we consider the AGP with fading (AGPF): A polygonal region is to be illuminated with light sources such that every point is illuminated with at least a global threshold, light intensity decreases over distance, and we seek to minimize the total energy consumption. Choosing fading exponents of zero, one, and two are equivalent to the AGP, laser scanner applications, and natural light, respectively. We present complexity results as well as a negative solvability result. Still, we propose two practical algorithms for AGPF with fixed light positions (e.g. vertex guards) independent of the fading exponent, which we demonstrate to work well in practice. One is based on a discrete approximation, the other on non-linear programming by means of simplex-partitioning strategies. The former approach yields a fully polynomial-time approximation scheme for the AGPF with fixed light positions. The latter approach obtains better results in our experimental evaluation.
|
|
| 6. |
- Gade, Jan-Lucas, 1988-, et al.
(författare)
-
Identification of mechanical properties of arteries with certification of global optimality
- 2022
-
Ingår i: Journal of Global Optimization. - : SPRINGER. - 0925-5001 .- 1573-2916. ; 82:1, s. 195-217
-
Tidskriftsartikel (refereegranskat)abstract
- In this study, we consider identification of parameters in a non-linear continuum-mechanical model of arteries by fitting the models response to clinical data. The fitting of the model is formulated as a constrained non-linear, non-convex least-squares minimization problem. The model parameters are directly related to the underlying physiology of arteries, and correctly identified they can be of great clinical value. The non-convexity of the minimization problem implies that incorrect parameter values, corresponding to local minima or stationary points may be found, however. Therefore, we investigate the feasibility of using a branch-and-bound algorithm to identify the parameters to global optimality. The algorithm is tested on three clinical data sets, in each case using four increasingly larger regions around a candidate global solution in the parameter space. In all cases, the candidate global solution is found already in the initialization phase when solving the original non-convex minimization problem from multiple starting points, and the remaining time is spent on increasing the lower bound on the optimal value. Although the branch-and-bound algorithm is parallelized, the overall procedure is in general very time-consuming.
|
|
| 7. |
- Holmström, Kenneth
(författare)
-
An adaptive radial basis algorithm (ARBF) for expensive black-box global optimization
- 2008
-
Ingår i: Journal of Global Optimization. - : Springer Science and Business Media LLC. - 1573-2916 .- 0925-5001. ; 41:3, s. 447-464
-
Tidskriftsartikel (refereegranskat)abstract
- Powerful response surface methods based on kriging and radial basis function (RBF) interpolation have been developed for expensive, i.e. computationally costly, global nonconvex optimization. We have implemented some of these methods in the solvers rbfSolve and EGO in the TOMLAB Optimization Environment (http://www.tomopt.com/tomlab/). In this paper we study algorithms based on RBF interpolation. The practical performance of the RBF algorithm is sensitive to the initial experimental design, and to the static choice of target values. A new adaptive radial basis interpolation (ARBF) algorithm, suitable for parallel implementation, is presented. The algorithm is described in detail and its efficiency is analyzed on the standard test problem set of Dixon-Szego. Results show that it outperforms the published results of rbfSolve and several other solvers.
|
|
| 8. |
- Kozlov, Vladimir, et al.
(författare)
-
Asymptotic analysis of solutions to parabolic systems
- 2008
-
Ingår i: Journal of Global Optimization. - : Springer Science and Business Media LLC. - 0925-5001 .- 1573-2916. ; 40:01-Mar, s. 369-374
-
Tidskriftsartikel (refereegranskat)abstract
- We study asymptotics as t --> infinity of solutions to a linear, parabolic system of equations with time-dependent coefficients in Omega x (0,infinity), where Omega is a bounded domain. On partial derivative Omega x (0,infinity) we prescribe the homogeneous Dirichlet boundary condition. For large values of t, the coefficients in the elliptic part are close to time-independent coefficients in an integral sense which is described by a certain function kappa(t). This includes in particular situations when the coefficients may take different values on different parts of Omega and the boundaries between them can move with t but stabilize as t --> infinity. The main result is an asymptotic representation of solutions for large t. A consequence is that for kappa is an element of L-1(0,infinity), the solution behaves asymptotically as the solution to a parabolic system with time-independent coefficients.
|
|
| 9. |
- Lauer, Fabien, et al.
(författare)
-
Finding sparse solutions of systems of polynomial equations via group-sparsity optimization
- 2015
-
Ingår i: Journal of Global Optimization. - : Springer Verlag (Germany). - 0925-5001 .- 1573-2916. ; 62:2, s. 319-349
-
Tidskriftsartikel (refereegranskat)abstract
- The paper deals with the problem of finding sparse solutions to systems of polynomial equations possibly perturbed by noise. In particular, we show how these solutions can be recovered from group-sparse solutions of a derived system of linear equations. Then, two approaches are considered to find these group-sparse solutions. The first one is based on a convex relaxation resulting in a second-order cone programming formulation which can benefit from efficient reweighting techniques for sparsity enhancement. For this approach, sufficient conditions for the exact recovery of the sparsest solution to the polynomial system are derived in the noiseless setting, while stable recovery results are obtained for the noisy case. Though lacking a similar analysis, the second approach provides a more computationally efficient algorithm based on a greedy strategy adding the groups one-by-one. With respect to previous work, the proposed methods recover the sparsest solution in a very short computing time while remaining at least as accurate in terms of the probability of success. This probability is empirically analyzed to emphasize the relationship between the ability of the methods to solve the polynomial system and the sparsity of the solution.
|
|
| 10. |
- Lundell, Andreas, et al.
(författare)
-
Polyhedral approximation strategies for nonconvex mixed-integer nonlinear programming in SHOT
- 2022
-
Ingår i: Journal of Global Optimization. - : Springer Nature. - 0925-5001 .- 1573-2916. ; 82:4, s. 863-896
-
Tidskriftsartikel (refereegranskat)abstract
- Different versions of polyhedral outer approximation are used by many algorithms for mixed-integer nonlinear programming (MINLP). While it has been demonstrated that such methods work well for convex MINLP, extending them to solve nonconvex problems has traditionally been challenging. The Supporting Hyperplane Optimization Toolkit (SHOT) is a solver based on polyhedral approximations of the nonlinear feasible set of MINLP problems. SHOT is an open source COIN-OR project, and is currently one of the most efficient global solvers for convex MINLP. In this paper, we discuss some extensions to SHOT that significantly extend its applicability to nonconvex problems. The functionality include utilizing convexity detection for selecting the nonlinearities to linearize, lifting reformulations for special classes of functions, feasibility relaxations for infeasible subproblems and adding objective cuts to force the search for better feasible solutions. This functionality is not unique to SHOT, but can be implemented in other similar methods as well. In addition to discussing the new nonconvex functionality of SHOT, an extensive benchmark of deterministic solvers for nonconvex MINLP is performed that provides a snapshot of the current state of nonconvex MINLP.
|
|
