Combined bound-grid-factor constraints for enhancing RLT relaxations for polynomial programs

This paper studies the global optimization of polynomial programming problems using Reformulation-Linearization Technique (RLT)-based linear programming (LP) relaxations. We introduce a new class of bound-grid-factor constraints that can be judiciously used to augment the basic RLT relaxations in order to improve the quality of lower bounds and enhance the performance of global branch-and-bound algorithms. Certain theoretical properties are established that shed light on the effect of these valid inequalities in driving the discrepancies between RLT variables and their associated nonlinear products to zero. To preserve computational expediency while promoting efficiency, we propose certain concurrent and sequential cut generation routines and various grid-factor selection rules. The results indicate a significant tightening of lower bounds, which yields an overall reduction in computational effort for solving a test-bed of polynomial programming problems to global optimality in comparison with the basic RLT procedure as well as the commercial software BARON.     

Theory of convex cones in multicriteria decision making

We develop the theory of convex polyhedral cones in the objective-function space of a multicriteria decision problem. The convex cones are obtained from the decision-maker's pairwise judgments of decision alternatives and are applicable to any quasiconcave utility function. Therefore, the cones can be used in any progressively articulated solution procedure that employs pairwise comparisons. The cones represent convex sets of solutions that are inferior to known solutions to a multicriteria problem. Therefore, these convex sets can be eliminated from consideration while solving the problem. We develop the underlying theory and a framework for representing knowledge about the decision-maker's preference structure using convex cones. This framework can be adopted in the interactive solution of any multicriteria problem after taking into account the characteristics of the problem and the solution procedure. Our computational experience with different multicriteria problems shows that this approach is both viable and efficient in solving practical problems of moderate size.     

GloMIQO: Global mixed-integer quadratic optimizer

This paper introduces the global mixed-integer quadratic optimizer, GloMIQO, a numerical solver addressing mixed-integer quadratically-constrained quadratic programs to ${\varepsilon}$ -global optimality. The algorithmic components are presented for: reformulating user input, detecting special structure including convexity and edge-concavity, generating tight convex relaxations, partitioning the search space, bounding the variables, and finding good feasible solutions. To demonstrate the capacity of GloMIQO, we extensively tested its performance on a test suite of 399 problems of diverse size and structure. The test cases are taken from process networks applications, computational geometry problems, GLOBALLib, MINLPLib, and the Bonmin test set. We compare the performance of GloMIQO with respect to four state-of-the-art global optimization solvers: BARON 10.1.2, Couenne 0.4, LindoGLOBAL 6.1.1.588, and SCIP 2.1.0.     

Computational experience using an edge search algorithm for linear reverse convex programs

This paper presents computational experience with a rather straight forward implementation of an edge search algorithm for obtaining the globally optimal solution for linear programs with an additional reverse convex constraint. The paper's purpose is to provide a collection of problems, with known optimal solutions, and performance information for an edge search implementation so that researchers may have some benchmarks with which to compare new methods for reverse convex programs or concave minimization problems. There appears to be nothing in the literature that provides computational experience with a basic edge search procedure. The edge search implementation uses a depth first strategy. As such, this paper's implementation of the edge search algorithm is a modification of Hillestad's algorithm [11]. A variety of test problems is generated by using a modification of the method of Sung and Rosen [20], as well as a new method that is presented in this paper. Test problems presented may be obtained at ftp://newton.ee.ucla.edu/nonconvex/pub/.     

Construction of Test Problems for Concave Minimization Under Linear and Nonlinear Constraints

This paper presents a method for constructing test problems with known global solutions for concave minimization under linear constraints with an additional convex constraint and for reverse convex programs with an additional convex constraint. The importance of such a construction can be realized from the fact that the well known d.c. programming problem can be formulated in this form. Then, the method is further extended to generate test problems with more than one convex constraint, tight or untight at the global solution.     

Bounds tightening based on optimality conditions for nonconvex box-constrained optimization

First-order optimality conditions have been extensively studied for the development of algorithms for identifying locally optimal solutions. In this work, we propose two novel methods that directly exploit these conditions to expedite the solution of box-constrained global optimization problems. These methods carry out domain reduction by application of bounds tightening methods on optimality conditions. This scheme is implicit and avoids explicit generation of optimality conditions through symbolic differentation, which can be memory and time intensive. The proposed bounds tightening methods are implemented in the global solver BARON. Computational results on a test library of 327 problems demonstrate the value of our proposed approach in reducing the computational time and number of nodes required to solve these problems to global optimality.     

A branch-and-reduce approach to global optimization

This paper presents valid inequalities and range contraction techniques that can be used to reduce the size of the search space of global optimization problems. To demonstrate the algorithmic usefulness of these techniques, we incorporate them within the branch-and-bound framework. This results in a branch-and-reduce global optimization algorithm. A detailed discussion of the algorithm components and theoretical properties are provided. Specialized algorithms for polynomial and multiplicative programs are developed. Extensive computational results are presented for engineering design problems, standard global optimization test problems, univariate polynomial programs, linear multiplicative programs, mixed-integer nonlinear programs and concave quadratic programs. For the problems solved, the computer implementation of the proposed algorithm provides very accurate solutions in modest computational time.     

Nonlinear elliptic problems with superlinear reaction and parametric concave boundary condition

We study parametric nonlinear elliptic boundary value problems driven by the p-Laplacian with convex and concave terms. The convex term appears in the reaction and the concave in the boundary condition (source). We study the existence and nonexistence of positive solutions as the parameter λ > 0 varies. For the semilinear problem (p = 2), we prove a bifurcation type result. Finally, we show the existence of nodal (sign changing) solutions.     

Computational comparison of two methods for constrained global optimization

For constrained concave global minimization problems, two very different solution techniques have been investigated. The first such method is a stochastic mulitstart approach which typically finds, with high probability, all local minima for the problem. The second method is deterministic and guarantees a global minimum solution to within any user specified tolerance. It is the purpose of this paper to make a careful comparison of these two methods on a range of test problems using separable concave objectives over compact polyhedral sets, and to investigate in this way the advantages and disadvantages of each method. A direct computational comparison, on the same set of over 140 problems, is presented.     

An objective hyperplane search procedure for solving the general all-integer linear programming (ILP) problem

We describe an objective hyperplane search method for solving a class of integer linear programming (ILP) problems. We formulate the search as a bounded knapsack problem and develop requisite theory for formulating knapsack problems with composite constraints and composite objective functions that facilitate convergence to an ILP solution. A heuristic solution algorithm was developed and used to solve a variety of test problems found in the literature. The method obtains optimal or near-optimal solutions in acceptable ranges of computational effort.     

co-radiant集的等价表示及其在向量优化问题中的应用

作为特殊的抽象凸(凹)集,radiant集和co-radiant集在抽象凸分析和多目标优化问题理论中发挥着重要作用.首先建立radiant集co-radiant集的等价刻画,从而推导出它们的重要性质.然后,将重要性质应用到向量优化问题近似解的刻画中,得到关于近似解集的等价刻画.     

Models and algorithms for the 2-dimensional cell suppression problem in statistical disclosure control

Lagrangean dualization and subgradient optimization techniques are frequently used within the field of computational optimization for finding approximate solutions to large, structured optimization problems. The dual subgradient scheme does not automatically produce primal feasible solutions; there is an abundance of techniques for computing such solutions (via penalty functions, tangential approximation schemes, or the solution of auxiliary primal programs), all of which require a fair amount of computational effort. We consider a subgradient optimization scheme applied to a Lagrangean dual formulation of a convex program, and construct, at minor cost, an ergodic sequence of subproblem solutions which converges to the primal solution set. Numerical experiments performed on a traffic equilibrium assignment problem under road pricing show that the computation of the ergodic sequence results in a considerable improvement in the quality of the primal solutions obtained, compared to those generated in the basic subgradient scheme. Received February 11, 1997 / Revised version received June 19, 1998?Published online June 28, 1999     

Generalized McCormick relaxations

Convex and concave relaxations are used extensively in global optimization algorithms. Among the various techniques available for generating relaxations of a given function, McCormick’s relaxations are attractive due to the recursive nature of their definition, which affords wide applicability and easy implementation computationally. Furthermore, these relaxations are typically stronger than those resulting from convexification or linearization procedures. This article leverages the recursive nature of McCormick’s relaxations to define a generalized form which both affords a new framework within which to analyze the properties of McCormick’s relaxations, and extends the applicability of McCormick’s technique to challenging open problems in global optimization. Specifically, relaxations of the parametric solutions of ordinary differential equations are considered in detail, and prospects for relaxations of the parametric solutions of nonlinear algebraic equations are discussed. For the case of ODEs, a complete computational procedure for evaluating convex and concave relaxations of the parametric solutions is described. Through McCormick’s composition rule, these relaxations may be used to construct relaxations for very general optimal control problems.     

The prize-collecting generalized minimum spanning tree problem

We introduce the prize-collecting generalized minimum spanning tree problem. In this problem a network of node clusters needs to be connected via a tree architecture using exactly one node per cluster. Nodes in each cluster compete by offering a payment for selection. This problem is NP-hard, and we describe several heuristic strategies, including local search and a genetic algorithm. Further, we present a simple and computationally efficient branch-and-cut algorithm. Our computational study indicates that our branch-and-cut algorithm finds optimal solutions for networks with up to 200 nodes within two hours of CPU time, while the heuristic search procedures rapidly find near-optimal solutions for all of the test instances.     

Preprocessing and cutting for multiple allocation hub location problems

In this paper we consider formulations and solution approaches for multiple allocation hub location problems. We present a number of results, which enable us to develop preprocessing procedures and tightening constraints for existing mixed integer linear programming formulations. We employ flow cover constraints for capacitated problems to improve computation times. We present the results of our computational experience, which show that all of these steps can effectively reduce the computational effort required to obtain optimal solutions.     

On the Use of Exact and Heuristic Cutting Plane Methods for the Quadratic Assignment Problem

This paper uses the formulation of the quadratic assignment problem as that of minimizing a concave quadratic function over the assignment polytope. Cutting plane procedures are investigated for solving this problem. A lower bound derived on the number of cuts needed for termination indicates that conventional cutting plane procedures would require a huge computational effort for the exact solution of the quadratic assignment problems. However, several heuristics which are derived from the cutting planes produce optimal or good quality solutions early on in the search process. An illustrative example and computational results are presented.     

Eponential Decay To Stable States In Phase Transitions Via A Double Log–Transformation

Motivated by various Hamilton–Jacobi–Bellman equations arising in deteministic optimal control we will modify the concept of viscosity solution introduced by Crandall and Lions for convex (or concave) hamiltonians and semicontinuous solutions. We will see that we can dispense with the Crandall–Lions requirement that we touch the solution by test functions from both above and below and require only touching from one side, Which side depends on whether the solution is upper or lower semicontinuous and the hamiltonian is concave. The advantage of testing from only one side is that Semicontinuous solutions can only be touched from one side. It is shown that this is sufficient to characterize the solution.     

Global minimization algorithms for concave quadratic programming problems

Abstract: In this article, we consider the concave quadratic programming problem which is known to be NP hard. Based on the improved global optimality conditions by [Dür, M., Horst, R. and Locatelli, M., 1998, Necessary and sufficient global optimality conditions for convex maximization revisited, Journal of Mathematical Analysis and Applications, 217, 637–649] and [Hiriart-Urruty, J.B. and Ledyav, J.S., 1996, A note in the characterization of the global maxima of a convex function over a convex set, Journal of Convex Analysis, 3, 55–61], we develop a new approach for solving concave quadratic programming problems. The main idea of the algorithms is to generate a sequence of local minimizers either ending at a global optimal solution or at an approximate global optimal solution within a finite number of iterations. At each iteration of the algorithms we solve a number of linear programming problems with the same constraints of the original problem. We also present the convergence properties of the proposed algorithms under some conditions. The efficiency of the algorithms has been demonstrated with some numerical examples.     

Partial convexification cuts for 0–1 mixed-integer programs

In this research, we propose a new cut generation scheme based on constructing a partial convex hull representation for a given 0–1 mixed-integer programming problem by using the reformulation–linearization technique (RLT). We derive a separation problem that projects the extended space of the RLT formulation into the original space, in order to generate a cut that deletes a current fractional solution. Naturally, the success of such a partial convexification based cutting plane scheme depends on the process used to tradeoff the strength of the cut derived and the effort expended. Accordingly, we investigate several variable selection rules for performing this convexification, along with restricted versions of the accompanying separation problems, so as to be able to derive strong cuts within a reasonable effort. We also develop a strengthening procedure that enhances the generated cut by considering the binariness of the remaining unselected 0–1 variables. Finally, we present some promising computational results that provide insights into implementing the proposed cutting plane methodology.