Refine
Document Type
- Article (5)
Language
- English (5)
Has Fulltext
- yes (5)
Keywords
- Software (4)
- Theoretical Computer Science (4)
The computation of an initial basis is of great importance for simplex algorithms since it determines to a large extent the number of iterations and the computational effort needed to solve linear programs. We propose three algorithms that aim to construct an initial basis that is sparse and will reduce the fill-in and computational effort during LU factorization and updates that are utilized in modern simplex implementations. The algorithms rely on triangulation and fill-reducing ordering techniques that are invoked prior to LU factorization. We compare the performance of the CPLEX 12.6.1 primal and dual simplex algorithms using the proposed starting bases against CPLEX using its default crash procedure over a set of 95 large benchmarks (NETLIB, Kennington, Mészáros, Mittelmann). The best proposed algorithm utilizes METIS (Karypis and Kumar in SIAM J Sci Comput 20:359–392, 1998), produces remarkably sparse starting bases, and results in 5% reduction of the geometric mean of the execution time of CPLEX’s primal simplex algorithm. Although the proposed algorithm improves CPLEX’s primal simplex algorithm across all problem types studied in this paper, it performs better on hard problems, i.e., the instances for which the CPLEX default requires over 1000 s. For these problems, the proposed algorithm results in 37% reduction of the geometric mean of the execution time of CPLEX’s primal simplex algorithm. The proposed algorithm also reduces the execution time of CPLEX’s dual simplex on hard instances by 10%. For the instances that are most difficult for CPLEX, and for which CPLEX experiences numerical difficulties as it approaches the optimal solution, the best proposed algorithm speeds up CPLEX by more than 10 times. Finally, the proposed algorithms lead to a natural way to parallelize CPLEX with speedups over CPLEX’s dual simplex of 1.2 and 1.3 on two and four cores, respectively.
Polyhedral relaxations have been incorporated in a variety of solvers for theglobal optimization of mixed-integer nonlinear programs. Currently, these relaxations constitute the dominant approach in global optimization practice. In this paper, we introduce a new relaxation paradigm for global optimization. The proposed framework combines polyhedral and convex nonlinear relaxations, along with fail-safe techniques, convexity identification at each node of the branch-and-bound tree, and learning strategies for automatically selecting and switching between polyhedral and nonlinear relaxations and among different local search algorithms in different parts of the search tree. We report computational experiments with the proposed methodology on widely-used test problem collections from the literature, including 369 problems from GlobalLib, 250 problems from MINLPLib, 980 problems from PrincetonLib, and 142 problems from IBMLib. Results show that incorporating the proposed techniques in the BARON software leads to significant reductions in execution time, and increases by 30% the number of problems that are solvable to global optimality within 500 s on a standard workstation.
This paper describes a new instance library for quadratic programming (QP), i.e., the family of continuous and (mixed)-integer optimization problems where the objective function and/or the constraints are quadratic. QP is a very diverse class of problems, comprising sub-classes ranging from trivial to undecidable. This diversity is reflected in the variety of QP solution methods, ranging from entirely combinatorial approaches to completely continuous algorithms, including many methods for which both aspects are fundamental. Selecting a set of instances of QP that is at the same time not overwhelmingly onerous but sufficiently challenging for the different, interested communities is therefore important. We propose a simple taxonomy for QP instances leading to a systematic problem selection mechanism. We then briefly survey the field of QP, giving an overview of theory, methods and solvers. Finally, we describe how the library was put together, and detail its final contents.
We consider global optimization of nonconvex problems whose factorable reformulations contain a collection of multilinear equations of the form ze=∏v∈ezv, e∈E, where E denotes a set of subsets of cardinality at least two of a ground set. Important special cases include multilinear and polynomial optimization problems. The multilinear polytope is the convex hull of the set of binary points z satisfying the system of multilinear equations given above. Recently Del Pia and Khajavirad introduced running intersection inequalities, a family of facet-defining inequalities for the multilinear polytope. In this paper we address the separation problem for this class of inequalities. We first prove that separating flower inequalities, a subclass of running intersection inequalities, is NP-hard. Subsequently, for multilinear polytopes of fixed degree, we devise an efficient polynomial-time algorithm for separating running intersection inequalities and embed the proposed cutting-plane generation scheme at every node of the branch-and-reduce global solver BARON. To evaluate the effectiveness of the proposed method we consider two test sets: randomly generated multilinear and polynomial optimization problems of degree three and four, and computer vision instances from an image restoration problem Results show that running intersection cuts significantly improve the performance of BARON and lead to an average CPU time reduction of 50% for the random test set and of 63% for the image restoration test set.
We consider global optimization of nonconvex problems containing mul- tilinear functions. It is well known that the convex hull of a multilinear function over a box is polyhedral, and the facets of this polyhedron can be obtained by solving a linear optimization problem (LP). When used as cutting planes, these facets can sig- nificantly enhance the quality of conventional relaxations in general-purpose global solvers. However, in general, the size of this LP grows exponentially with the number of variables in the multilinear function. To cope with this growth, we propose a graph decomposition scheme that exploits the structure of a multilinear function to decom- pose it to lower-dimensional components, for which the aforementioned LP can be solved very efficiently by employing a customized simplex algorithm. We embed this cutting plane generation strategy at every node of the branch-and-reduce global solver BARON, and carry out an extensive computational study on quadratically constrained quadratic problems, multilinear problems, and polynomial optimization problems. Results show that the proposed multilinear cuts enable BARON to solve many more problems to global optimality and lead to an average 60 % CPU time reduction.