A global MINLP approach to symbolic regression

Symbolic regression methods generate expression trees that simultaneously define the functional form of a regression model and the regression parameter values. As a result, the regression problem can search many nonlinear functional forms using only the specification of simple mathematical operators such as addition, subtraction, multiplication, and division, among others. Currently, state-of-the-art symbolic regression methods leverage genetic algorithms and adaptive programming techniques. Genetic algorithms lack optimality certifications and are typically stochastic in nature. In contrast, we propose an optimization formulation for the rigorous deterministic optimization of the symbolic regression problem. We present a mixed-integer nonlinear programming (MINLP) formulation to solve the symbolic regression problem as well as several alternative models to eliminate redundancies and symmetries. We demonstrate this symbolic regression technique using an array of experiments based upon literature instances. We then use a set of 24 MINLPs from symbolic regression to compare the performance of five local and five global MINLP solvers. Finally, we use larger instances to demonstrate that a portfolio of models provides an effective solution mechanism for problems of the size typically addressed in the symbolic regression literature.     

A new global optimization method for univariate constrained twice-differentiable NLP problems

In this paper, a new global optimization method is proposed for an optimization problem with twice-differentiable objective and constraint functions of a single variable. The method employs a difference of convex underestimator and a convex cut function, where the former is a continuous piecewise concave quadratic function, and the latter is a convex quadratic function. The main objectives of this research are to determine a quadratic concave underestimator that does not need an iterative local optimizer to determine the lower bounding value of the objective function and to determine a convex cut function that effectively detects infeasible regions for nonconvex constraints. The proposed method is proven to have a finite ε-convergence to locate the global optimum point. The numerical experiments indicate that the proposed method competes with another covering method, the index branch-and-bound algorithm, which uses the Lipschitz constant.     

Column enumeration based decomposition techniques for a class of non-convex MINLP problems

We propose a decomposition algorithm for a special class of nonconvex mixed integer nonlinear programming problems which have an assignment constraint. If the assignment decisions are decoupled from the remaining constraints of the optimization problem, we propose to use a column enumeration approach. The master problem is a partitioning problem whose objective function coefficients are computed via subproblems. These problems can be linear, mixed integer linear, (non-)convex nonlinear, or mixed integer nonlinear. However, the important property of the subproblems is that we can compute their exact global optimum quickly. The proposed technique will be illustrated solving a cutting problem with optimum nonlinear programming subproblems.     

Necessary and sufficient global optimality conditions for NLP reformulations of linear SDP problems

In this paper we consider the standard linear SDP problem, and its low rank nonlinear programming reformulation, based on a Gramian representation of a positive semidefinite matrix. For this nonconvex quadratic problem with quadratic equality constraints, we give necessary and sufficient conditions of global optimality expressed in terms of the Lagrangian function.     

A novel clustering approach and prediction of optimal number of clusters: global optimum search with enhanced positioning

Cluster analysis of genome-wide expression data from DNA microarray hybridization studies is a useful tool for identifying biologically relevant gene groupings (DeRisi et al. 1997; Weiler et al. 1997). It is hence important to apply a rigorous yet intuitive clustering algorithm to uncover these genomic relationships. In this study, we describe a novel clustering algorithm framework based on a variant of the Generalized Benders Decomposition, denoted as the Global Optimum Search (Floudas et al. 1989; Floudas 1995), which includes a procedure to determine the optimal number of clusters to be used. The approach involves a pre-clustering of data points to define an initial number of clusters and the iterative solution of a Linear Programming problem (the primal problem) and a Mixed-Integer Linear Programming problem (the master problem), that are derived from a Mixed Integer Nonlinear Programming problem formulation. Badly placed data points are removed to form new clusters, thus ensuring tight groupings amongst the data points and incrementing the number of clusters until the optimum number is reached. We apply the proposed clustering algorithm to experimental DNA microarray data centered on the Ras signaling pathway in the yeast Saccharomyces cerevisiae and compare the results to that obtained with some commonly used clustering algorithms. Our algorithm compares favorably against these algorithms in the aspects of intra-cluster similarity and inter-cluster dissimilarity, often considered two key tenets of clustering. Furthermore, our algorithm can predict the optimal number of clusters, and the biological coherence of the predicted clusters is analyzed through gene ontology.     

A self-adaptive global best harmony search algorithm for continuous optimization problems

This paper presents a self-adaptive global best harmony search (SGHS) algorithm for solving continuous optimization problems. In the proposed SGHS algorithm, a new improvisation scheme is developed so that the good information captured in the current global best solution can be well utilized to generate new harmonies. The harmony memory consideration rate (HMCR) and pitch adjustment rate (PAR) are dynamically adapted by the learning mechanisms proposed. The distance bandwidth (BW) is dynamically adjusted to favor exploration in the early stages and exploitation during the final stages of the search process. Extensive computational simulations and comparisons are carried out by employing a set of 16 benchmark problems from literature. The computational results show that the proposed SGHS algorithm is more effective in finding better solutions than the state-of-the-art harmony search (HS) variants.     

A formal approach to subgrammar extraction for NLP

The problem of subgrammar extraction is precisely defined in the following way: Given a grammar $G$ and a set of words $W$, find a smallest subgrammar of $G$ that accepts the same set of sentences from $W^1$ as $G$, and for each of them produces the same parse trees. In practical Natural Language Processing applications, the set of words $W$ is obtained from the text unit. There are practical motivations for doing this operation “just-in-time”, i.e. just before processing the text; hence it is required that this operation be done in an automatic and efficient way. After defining the problem in the general framework, we discuss the problem for context-free grammars (CFG), and give an efficient algorithm for it. We prove that finding the smallest subgrammar for HPSGs is an NP-hard problem, and give an efficient algorithm that solves an easier, approximate version of the problem. We also discuss how the algorithm can be efficiently implemented.     

A heuristic approach to find the global optimum of function

This paper presents the modified ant colony optimization (MACO) based algorithm to find global optimum. Algorithm is based on that solution space of problem is restricted by the best solution of the previous iteration. Furthermore, the proposed algorithm is that variables of problem are optimized concurrently. This algorithm was tested on some standard test functions, and successful results were obtained. Its performance was compared with the other algorithms, and observed to be better.     

A hybrid LP/NLP paradigm for global optimization relaxations

Polyhedral relaxations have been incorporated in a variety of solvers for the global 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.     

A new technique for inconsistent QP problems in the SQP method

Successful treatment of inconsistent QP problems is of major importance in the SQP method, since such occur quite often even for well behaved nonlinear programming problems. This paper presents a new technique for regularizing inconsistent QP problems, which compromises in its properties between the simple technique of Pantoja and Mayne [36] and the highly successful, but expensive one of Tone [47]. Global convergence of a corresponding algorithm is shown under reasonable weak conditions. Numerical results are reported which show that this technique, combined with a special method for the case of regular subproblems, is quite competitive to highly appreciated established ones.     

A vector linear programming approach for certain global optimization problems

A large part of the European natural gas imports originates from unstable regions exposed to the risk of supply failure due to economical and political reasons. This has increased the concerns on the security of supply in the European natural gas market. In this paper, we analyze the security of external supply of the Italian gas market that mainly relies on natural gas imports to cover its internal demand. To this aim, we develop an optimization problem that describes the equilibrium state of a gas supply chain where producers, mid-streamers, and final consumers exchange natural gas and liquefied natural gas. Both long-term contracts (LTCs) and spot pricing systems are considered. Mid-streamers are assumed to be exposed to the external supply risk, which is estimated with indicators that we develop starting from those already existing in the literature. In addition, we investigate different degrees of mid-streamers’ flexibility by comparing a situation where mid-streamers fully satisfy the LTC volume clause (“No FLEX” assumption) to a case where the fulfillment of this volume clause is not compulsory (“FLEX” assumption). Our analysis shows that, in the “No FLEX” case, mid-streamers do not significantly change their supplying choices even when the external supply risk is considered. Under this assumption, they face significant profit losses that, instead, disappear in the “FLEX” case when mid-streamers are more flexible and can modify their supply mix. However, the “FLEX” strategy limits the gas availability in the supply chain leading to a curtailment of the social welfare.     

A sequential cutting plane algorithm for solving convex NLP problems

In this paper we look at a new algorithm for solving convex nonlinear programming optimization problems. The algorithm is a cutting plane-based method, where the sizes of the subproblems remain fixed, thus avoiding the issue with constantly growing subproblems we have for the classical Kelley’s cutting plane algorithm. Initial numerical experiments indicate that the algorithm is considerably faster than Kelley’s cutting plane algorithm and also competitive with existing nonlinear programming algorithms.     

A global approach to fully nonlinear parabolic problems

We consider the general initial-boundary value problem

(1)        
(2)        
(3)        
where is a bounded open set in with sufficiently smooth boundary.  The problem (1)-(3) is first reduced to the analogous problem in the space with zero initial condition and

The resulting problem is then reduced to the problem where the operator satisfies Condition  This reduction is based on a priori estimates which are developed herein for linear parabolic operators with coefficients in Sobolev spaces.  The local and global solvability of the operator equation are achieved via topological methods developed by I. V. Skrypnik. Further applications are also given involving relevant coercive problems, as well as Galerkin approximations.

     

A breakpoint search approach for convex resource allocation problems with bounded variables

We present an efficient approach to solve resource allocation problems with a single resource, a convex separable objective function, a convex separable resource-usage constraint, and variables that are bounded below and above. Through a combination of function evaluations and median searches, information on whether or not the upper- and lowerbounds are binding is obtained. Once this information is available for all upper and lower bounds, it remains to determine the optimum of a smaller problem with unbounded variables. This can be done through a multiplier search procedure. The information gathered allows for alternative approaches for the multiplier search which can reduce the complexity of this procedure.     

A decomposition approach for optimal control problems with integer innerpoint state constraints

A large class of optimal control problems for hybrid dynamic systems can be formulated as mixed‐integer optimal control problems (MIOCPs). A decomposition approach is suggested to solve a special subclass of MIOCPs with mixed integer inner point state constraints. It is the intrinsic combinatorial complexity of the discrete variables in addition to the high nonlinearity of the continuous optimal control problem that forms the challenges in the theoretical and numerical solution of MIOCPs. During the solution procedure the problem is decomposed at the inner time points into a multiphase problem with mixed integer boundary constraints and phase transitions at unknown switching points. Due to a discretization of the state space at the switching points the problem can be decoupled into a family of continuous optimal control problems (OCPs) and a problem similar to the asymmetric group traveling salesman problem (AGTSP). The OCPs are transcribed by direct collocation to large‐scale nonlinear programming problems, which are solved efficiently by an advanced SQP method. The results are used as weights for the edges of the graph of the corresponding TSP‐like problem, which is solved by a Branch‐and‐Cut‐and‐Price (BCP) algorithm. The proposed approach is applied to a hybrid optimal control benchmark problem for a motorized traveling salesman. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A global optimization approach for solving three-dimensional open dimension rectangular packing problems

The three-dimensional open dimension rectangular packing problem (3D-ODRPP) aims to pack a set of given rectangular boxes into a large rectangular container of minimal volume. This problem is an important issue in the shipping and moving industries. All the boxes can be any rectangular stackable objects with different sizes and may be freely rotated. The 3D-ODRPP is usually formulated as a mixed-integer non-linear programming problem. Most existing packing optimization methods cannot guarantee to find a globally optimal solution or are computationally inefficient. Therefore, this paper proposes an efficient global optimization method that transforms a 3D-ODRPP as a mixed-integer linear program using fewer extra 0–1 variables and constraints compared to existing deterministic approaches. The reformulated model can be solved to obtain a global optimum. Experimental results demonstrate the computational efficiency of the proposed approach in globally solving 3D-ODRPPs drawn from the literature and the practical applications.     

A geodesic approach to calculating the information sets in dynamic search problems

A new method for calculating the information sets in dynamic search problems is proposed. Representation of the sets is based on the concept of distance fields and operations on these fields, on calculating the geodesic distances via finding a viscous solution to the Hamilton-Jacobi equation. The method is applied to solving the search problems on surfaces in a 3D space.     

A local search method for continuous global optimization

A large number of algorithms introduced in the literature to find the global minimum of a real function rely on iterative executions of searches of a local minimum. Multistart, tunneling and some versions of simulated annealing are methods that produce well-known procedures. A crucial point of these algorithms is to decide whether to perform or not a new local search. In this paper we look for the optimal probability value to be set at each iteration so that by moving from a local minimum to a new one, the average number of function evaluations evals is minimal. We find that this probability has to be 0 or 1 depending on the number of function evaluations required by the local search and by the size of the level set at the current point. An implementation based on the above result is introduced. The values required to calculate evals are estimated from the history of the algorithm at running time. The algorithm has been tested both for sample problems constructed by the GKLS package and for problems often used in the literature. The outcome is compared with recent results.