Integrating SQP and Branch-and-Bound for Mixed Integer Nonlinear Programming

This paper considers the solution of Mixed Integer Nonlinear Programming (MINLP) problems. Classical methods for the solution of MINLP problems decompose the problem by separating the nonlinear part from the integer part. This approach is largely due to the existence of packaged software for solving Nonlinear Programming (NLP) and Mixed Integer Linear Programming problems.In contrast, an integrated approach to solving MINLP problems is considered here. This new algorithm is based on branch-and-bound, but does not require the NLP problem at each node to be solved to optimality. Instead, branching is allowed after each iteration of the NLP solver. In this way, the nonlinear part of the MINLP problem is solved whilst searching the tree. The nonlinear solver that is considered in this paper is a Sequential Quadratic Programming solver.A numerical comparison of the new method with nonlinear branch-and-bound is presented and a factor of up to 3 improvement over branch-and-bound is observed.     

Two linear approximation algorithms for convex mixed integer nonlinear programming

We present two new algorithms for convex Mixed Integer Nonlinear Programming (MINLP), both based on the well known Extended Cutting Plane (ECP) algorithm proposed by Weterlund and Petersson. Our first algorithm, Refined Extended Cutting Plane (RECP), incorporates additional cuts to the MILP relaxation of the original problem, obtained by solving linear relaxations of NLP problems considered in the Outer Approximation algorithm. Our second algorithm, Linear Programming based Branch-and-Bound (LP-BB), applies the strategy of generating cuts that is used in RECP, to the linear approximation scheme used by the LP/NLP based Branch-and-Bound algorithm. Our computational results show that RECP and LP-BB are highly competitive with the most popular MINLP algorithms from the literature, while keeping the nice and desirable characteristic of ECP, of being a first-order method.

     

A hybrid Granular Tabu Search algorithm for the Multi-Depot Vehicle Routing Problem

In this paper, we propose a hybrid Granular Tabu Search algorithm to solve the Multi-Depot Vehicle Routing Problem (MDVRP). We are given on input a set of identical vehicles (each having a capacity and a maximum duration), a set of depots, and a set of customers with deterministic demands and service times. The problem consists of determining the routes to be performed to fulfill the demand of the customers by satisfying, for each route, the associated capacity and maximum duration constraints. The objective is to minimize the sum of the traveling costs related to the performed routes. The proposed algorithm is based on a heuristic framework previously introduced by the authors for the solution of the Capacitated Location Routing Problem (CLRP). The algorithm applies a hybrid Granular Tabu Search procedure, which considers different neighborhoods and diversification strategies, to improve the initial solution obtained by a hybrid procedure. Computational experiments on benchmark instances from the literature show that the proposed algorithm is able to produce, within short computing time, several best solutions obtained by the previously published methods and new best solutions.     

Linearization-based algorithms for mixed-integer nonlinear programs with convex continuous relaxation

We present two linearization-based algorithms for mixed-integer nonlinear programs (MINLPs) having a convex continuous relaxation. The key feature of these algorithms is that, in contrast to most existing linearization-based algorithms for convex MINLPs, they do not require the continuous relaxation to be defined by convex nonlinear functions. For example, these algorithms can solve to global optimality MINLPs with constraints defined by quasiconvex functions. The first algorithm is a slightly modified version of the LP/NLP-based branch-and-bouund \((\text{ LP/NLP-BB })\) algorithm of Quesada and Grossmann, and is closely related to an algorithm recently proposed by Bonami et al. (Math Program 119:331–352, 2009). The second algorithm is a hybrid between this algorithm and nonlinear programming based branch-and-bound. Computational experiments indicate that the modified LP/NLP-BB method has comparable performance to LP/NLP-BB on instances defined by convex functions. Thus, this algorithm has the potential to solve a wider class of MINLP instances without sacrificing performance.     

Global solution of optimization problems with signomial parts

In this paper a new approach for the global solution of nonconvex MINLP (Mixed Integer NonLinear Programming) problems that contain signomial (generalized geometric) expressions is proposed and illustrated. By applying different variable transformation techniques and a discretization scheme a lower bounding convex MINLP problem can be derived. The convexified MINLP problem can be solved with standard methods. The key element in this approach is that all transformations are applied termwise. In this way all convex parts of the problem are left unaffected by the transformations. The method is illustrated by four example problems.     

Piece-wise linear approximation of functions of two variables

The goal of increasing computational efficiency is one of the fundamental challenges of both theoretical and applied research in mathematical modeling. The pursuit of this goal has lead to wide diversity of efforts to transform a specific mathematical problem into one that can be solved efficiently. Recent years have seen the emergence of highly efficient methods and software for solving Mixed Integer Programming Problems, such as those embodied in the packages CPLEX, MINTO, XPRESS-MP. The paper presents a method to develop a piece-wise linear approximation of an any desired accuracy to an arbitrary continuous function of two variables. The approximation generalizes the widely known model for approximating single variable functions, and significantly expands the set of nonlinear problems that can be efficiently solved by reducing them to Mixed Integer Programming Problems. By our development, any nonlinear programming problem, including non-convex ones, with an objective function (and/or constraints) that can be expressed as sums of component nonlinear functions of no more than two variables, can be efficiently approximated by a corresponding Mixed Integer Programming Problem.     

Approximation by Linear Combinations of Complex Phillips Operators in Compact Disks

In the present article we find direct quantitative estimate for approximation of complex valued functions by linear combinations of the complex Phillips operators. Here we extend the recent results of Gal and Gupta (Mathematics without boundaries; Surveys in Interdisciplinary Research, 2014). We have been able to achieve the better approximation for the complex Phillips operators.     

Analytic Propagation for Nonlinear Weakly Hyperbolic Systems

The propagation of analyticity for sufficiently smooth solutions to either strictly hyperbolic, or smoothly symmetrizable nonlinear systems, dates back to Lax [14 Lax , P.D. ( 1953 ). Nonlinear hyperbolic equations . Comm. Pure Appl. Math. 6 : 231 – 258 . [Google Scholar]] and Alinhac and Métivier [2 Alinhac , S. , Métivier G. ( 1984 ). Propagation de l'analyticité des solutions de systèmes hyperboliques nonlinéaires [Propagation of analyticity for solutions of nonlinear hyperbolic systems]. Invent. Math. 75, 189–204 . [Google Scholar]]. Here we consider the general case of a system with real, possibly multiple, characteristics, and we ask which regularity should be a priori required of a given solution in order that it enjoys the propagation of analyticity. By using the technique of the quasi-symmetrizer of a hyperbolic matrix, we prove, in the one-dimensional case, the propagation of analyticity for those solutions which are Gevrey functions of order s for some s < m/(m ? 1), m being the maximum multiplicity of the characteristics.     

An Application of Darbo Fixed-Point Theorem to a Class of Functional Integral Equations

In this article, using Darbo's fixed-point theorem associated with the measure of noncompactness, we prove a theorem on the existence of the solutions of some nonlinear functional integral equations in the space of continuous functions on interval [0, a]. Our existence results include several existence results obtained earlier by Maleknejad et al. [7 K. Maleknejad , K. Nouri , and R. Mollapourasl ( 2009 ). Investigation on the existence of solutions for some nonlinear functional-integral equations . Nonlinear Anal. 71 : 1575 – 1578 .[Crossref], [Web of Science ®] , [Google Scholar]] and Özdemir et al. [8 ?. Özdemir , Ü. Çakan , and B. ?lhan ( 2013 ). On the existence of the solutions for some nonlinear Volterra integral equations . Abstr. Appl. Anal. Article ID 689234.  [Google Scholar]] as special cases under some weaker conditions. We give also some examples which show that our results are applicable.     

On Global Attractor for 2D Kirchhoff–Boussinesq Model with Supercritical Nonlinearity

Dynamics for a class of nonlinear 2D Kirchhoff–Boussinesq models is studied. These nonlinear plate models are characterized by the presence of a nonlinear source that alone leads to finite-time blow up of solutions. In order to counteract, restorative forces are introduced, which however are of a supercritical nature. This raises natural questions such as: (i) wellposedness of finite energy (weak) solutions, (ii) their regularity, and (iii) long time behavior of both weak and strong solutions. It is shown that finite energy solutions do exist globally, are unique and satisfy Hadamard wellposedness criterium. In addition, weak solutions corresponding to “strong” initial data (i.e., strong solutions) enjoy, likewise, the full Hadamard wellposedness. The proof is based on logarithmic control of the lack of Sobolev's embedding. In addition to wellposedness, long time behavior is analyzed. Viscous damping added to the model controls long time behaviour of solutions. It is shown that both weak and (resp. strong) solutions admit compact global attractors in the finite energy norm, (resp. strong topology of strong solutions). The proof of long time behavior is based on Ball's method [2 Ball , J. ( 2004 ). Global attractors for semilinear wave equations . Discr. Cont. Dyn. Sys. 10 : 31 – 52 .[Crossref], [Web of Science ®] , [Google Scholar]] and on recent asymptotic quasi-stability inequalities established in [11 Chueshov , I. , Lasiecka , I. ( 2008 ). Long-Time Behavior of Second Order Evolution Equations with Nonlinear Damping . Memoirs of the American Mathematical Society, Vol. 912 . Providence , RI : American Mathematical Society .[Crossref] , [Google Scholar]]. These inequalities enable to prove that strong attractors are finite-dimensional and the corresponding trajectories can exhibit C ^∞ smoothness.     

Oscillation Criteria for Certain Fourth-Order Nonlinear Delay Differential Equations

In this article, we establish some new criteria for the oscillation of fourth-order nonlinear delay differential equations of the form

$$(r_2(t)(r_1(t)(y''(t))^\alpha)')' + p(t)(y''(t))^\alpha + q(t)f(y(g(t))) = 0$$

provided that the second-order equation

$$(r_2(t)z'(t))') + \frac{p(t)}{r_1(t)}z(t) = 0$$

is nonoscillatory or oscillatory.

     

Discretization orders for protein side chains

Proteins are important molecules that are widely studied in biology. Since their three-dimensional conformations can give clues about their function, an optimal methodology for the identification of such conformations has been researched for many years. Experiments of Nuclear Magnetic Resonance (NMR) are able to estimate distances between some pairs of atoms forming the protein, and the problem of identifying the possible conformations satisfying the available distance constraints is known in the scientific literature as the Molecular Distance Geometry Problem (MDGP). When some particular assumptions are satisfied, MDGP instances can be discretized, and solved by employing an ad-hoc algorithm, named the interval Branch & Prune. When dealing with molecules such as proteins, whose chemical structure is known, a priori information can be exploited for generating atomic orderings that allow for the discretization. In previous publications, we presented a handcrafted order for the protein backbones. In this work, we propose 20 new orders for the 20 side chains that can be present in proteins. Computational experiments on artificial and real instances from NMR show the usefulness of the proposed orders.     

An Affine Scaling Interior Point Filter Line-Search Algorithm for Linear Inequality Constrained Minimization

We propose and analyze a new affine scaling interior point method in association with line-search filter technique for solving the linear inequality constrained optimization. We extend an existing filter of Wächter and Biegler [9 A. Wächter and L. Biegler ( 2005 ). Line search filter methods for nonlinear programming: Motivation and global convergence . SIAM J. Comput. 16 : 1 – 31 .[Web of Science ®] , [Google Scholar]] for nonlinear equality constrained problems to linear inequality constraint problems. The two main ingredients of the method are a filter-line-search algorithm which is used to determine step size and an affine-scaling interior point Newton method which is used to generate a search direction. The global convergence of the proposed algorithm is established under some reasonable conditions. Further, the method is shown to be locally Q-superlinearly convergent under the strong second order sufficiency condition. Numerical tests are presented that confirm the robustness and efficiency of the approach.     

Generalized Convex Disjunctive Programming: Nonlinear Convex Hull Relaxation

Generalized Disjunctive Programming (GDP) has been introduced recently as an alternative to mixed-integer programming for representing discrete/continuous optimization problems. The basic idea of GDP consists of representing these problems in terms of sets of disjunctions in the continuous space, and logic propositions in terms of Boolean variables. In this paper we consider GDP problems involving convex nonlinear inequalities in the disjunctions. Based on the work by Stubbs and Mehrotra [21] and Ceria and Soares [6], we propose a convex nonlinear relaxation of the nonlinear convex GDP problem that relies on the convex hull of each of the disjunctions that is obtained by variable disaggregation and reformulation of the inequalities. The proposed nonlinear relaxation is used to formulate the GDP problem as a Mixed-Integer Nonlinear Programming (MINLP) problem that is shown to be tighter than the conventional big-M formulation. A disjunctive branch and bound method is also presented, and numerical results are given for a set of test problems.     

On a numerical method for constructing a positive solution of the two-point boundary-value problem for a second-order nonlinear differential equation

An iterative method is proposed for finding an approximation to the positive solution of the two-point boundary-value problem $y'' + c(x)y^m = 0,0 < x < 1,y(0) = y(1) = 0,$ where m = const > 1 and c(x) is a continuous nonnegative function on [0, 1]. The convergence of this method is proved. An error estimate is also obtained.     

An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance

We consider the design of semidefinite programming(SDP) based approximation algorithm for the problem Max Hypergraph Cut with Limited Unbalance(MHC-LU): Find a partition of the vertices of a weighted hypergraph H =(V, E) into two subsets V1, V2 with ‖V2|- |V1‖ u for some given u and maximizing the total weight of the edges meeting both V1 and V2. The problem MHC-LU generalizes several other combinatorial optimization problems including Max Cut, Max Cut with Limited Unbalance(MC-LU), Max Set Splitting,Max Ek-Set Splitting and Max Hypergraph Bisection. By generalizing several earlier ideas, we present an SDP randomized approximation algorithm for MHC-LU with guaranteed worst-case performance ratios for various unbalance parameters τ = u/|V|. We also give the worst-case performance ratio of the SDP-algorithm for approximating MHC-LU regardless of the value of τ. Our strengthened SDP relaxation and rounding method improve a result of Ageev and Sviridenko(2000) on Max Hypergraph Bisection(MHC-LU with u = 0), and results of Andersson and Engebretsen(1999), Gaur and Krishnamurti(2001) and Zhang et al.(2004) on Max Set Splitting(MHC-LU with u = |V|). Furthermore, our new formula for the performance ratio by a tighter analysis compared with that in Galbiati and Maffioli(2007) is responsible for the improvement of a result of Galbiati and Maffioli(2007) on MC-LU for some range of τ.     

On the Local Convergence of a Penalty-Function-Free SQP Method

In this article, we propose a nonmonotone linesearch sequential quadratic programming method for general constrained optimization problems without a penalty function or a filter. The algorithm proposed here is a development of the algorithm in Xue et al. [17 W. Xue , C. Shen , and D. Pu ( 2009 ). A penalty-function-free line search SQP method for nonlinear programming . Journal of Computational and Applied Mathematics 228 ( 1 ): 313 – 325 .[Crossref], [Web of Science ®] , [Google Scholar]]. Compared with the former, the novelty of the method we propose is that the new algorithm will achieve the local convergence under weaker assumptions. In order to avoid the Maratos effect, we use the second-order correction in this method, which need not be computed at each iteration. In other words, after a certain number of iterations, there is no need to compute the second-order correction step any more. The global convergence and the locally superlinear convergence of our method are proved under some suitable conditions.     

Energy decay rates for solutions of the wave equation with boundary damping and source term

In this paper, we consider the wave equation $$u'' - \Delta u = |u|^\rho u$$ with the following nonlinear boundary condition $$\frac{\partial u}{\partial \nu} + \int\limits^t_0 k(t-s,x)u'(s){\rm d}s + a(x)g(u') = 0.$$ We show energy decay rates for solutions of the wave equation in bounded domain with nonlinear boundary damping and source term.     

Design and analysis of two discrete-time ZD algorithms for time-varying nonlinear minimization

Nonlinear minimization, as a subcase of nonlinear optimization, is an important issue in the research of various intelligent systems. Recently, Zhang et al. developed the continuous-time and discrete-time forms of Zhang dynamics (ZD) for time-varying nonlinear minimization. Based on this previous work, another two discrete-time ZD (DTZD) algorithms are proposed and investigated in this paper. Specifically, the resultant DTZD algorithms are developed for time-varying nonlinear minimization by utilizing two different types of Taylor-type difference rules. Theoretically, each steady-state residual error in the DTZD algorithm changes in an O(τ ³) manner with τ being the sampling gap. Comparative numerical results are presented to further substantiate the efficacy and superiority of the proposed DTZD algorithms for time-varying nonlinear minimization.     

Experiments in Solving Mixed Integer Programming Problems on a Small Array of Transputers

The time-consuming process of solving large-scale Mixed Integer Programming problems using the branch-and-bound technique can be speeded up by introducing a degree of parallelism into the basic algorithm. This paper describes the development and implementation of a parallel branch-and-bound algorithm created by adapting a commercial MIP solver. Inherent in the design of this software are certain ad hoc methods, the use of which are necessary in the effective solution of real problems. The extent to which these ad hoc methods can successfully be transferred to a parallel environment, in this case an array of at most nine transputers, is discussed. Computational results on a variety of real integer programming problems are reported.