Dual bounding procedures lead to convergent Branch–and–Bound algorithms

Branch–and–Bound methods with dual bounding procedures have recently been used to solve several continuous global optimization problems. We improve results on their convergence theory and give a condition that enables us to detect infeasible partition sets from the dual optimal value. Received: May 5, 1999 / Accepted: April 19, 2001?Published online September 17, 2001     

Deterministic global optimization with partition sets whose feasibility is not known: Application to concave minimization,reverse convex constraints,DC-programming,and Lipschitzian optimization

A crucial problem for many global optimization methods is how to handle partition sets whose feasibility is not known. This problem is solved for broad classes of feasible sets including convex sets, sets defined by finitely many convex and reverse convex constraints, and sets defined by Lipschitzian inequalities. Moreover, a fairly general theory of bounding is presented and applied to concave objective functions, to functions representable as differences of two convex functions, and to Lipschitzian functions. The resulting algorithms allow one to solve any global optimization problem whose objective function is of one of these forms and whose feasible set belongs to one of the above classes. In this way, several new fields of optimization are opened to the application of global methods.     

A simplicial branch-and-bound algorithm conscious of special structures in concave minimization problems

In this paper, we develop a simplicial branch-and-bound algorithm for generating globally optimal solutions to concave minimization problems with low rank nonconvex structures. We propose to remove all additional constraints imposed on the usual linear programming relaxed problem. Therefore, in each bounding operation, we solve a linear programming problem whose constraints are exactly the same as the target problem. Although the lower bound worsens as a natural consequence, we offset this weakness by using an inexpensive bound tightening procedure based on Lagrangian relaxation. After giving a proof of the convergence, we report a numerical comparison with existing algorithms. T. Kuno was partially supported by the Grand-in-Aid for Scientific Research (C) 17560050 from the Japan Society for the Promotion of Sciences.     

A relaxation method for nonconvex quadratically constrained quadratic programs

We present an algorithm for finding approximate global solutions to quadratically constrained quadratic programming problems. The method is based on outer approximation (linearization) and branch and bound with linear programming subproblems. When the feasible set is non-convex, the infinite process can be terminated with an approximate (possibly infeasible) optimal solution. We provide error bounds that can be used to ensure stopping within a prespecified feasibility tolerance. A numerical example illustrates the procedure. Computational experiments with an implementation of the procedure are reported on bilinearly constrained test problems with up to sixteen decision variables and eight constraints.This research was supported in part by National Science Foundation Grant DDM-91-14489.     

A Global Optimization Method,QBB, for Twice-Differentiable Nonconvex Optimization Problem

A global optimization method, QBB, for twice-differentiable NLPs (Non-Linear Programming) is developed to operate within a branch-and-bound framework and require the construction of a relaxed convex problem on the basis of the quadratic lower bounding functions for the generic nonconvex structures. Within an exhaustive simplicial division of the constrained region, the rigorous quadratic underestimation function is constructed for the generic nonconvex function structure by virtue of the maximal eigenvalue analysis of the interval Hessian matrix. Each valid lower bound of the NLP problem with the division progress is computed by the convex programming of the relaxed optimization problem obtained by preserving the convex or linear terms, replacing the concave term with linear convex envelope, underestimating the special terms and the generic terms by using their customized tight convex lower bounding functions or the valid quadratic lower bounding functions, respectively. The standard convergence properties of the QBB algorithm for nonconvex global optimization problems are guaranteed. The preliminary computation studies are presented in order to evaluate the algorithmic efficiency of the proposed QBB approach.     

一种求解约束优化问题的改进差分进化算法

针对在处理约束优化问题时约束条件难以处理的问题,提出了一种求解约束优化问题的改进差分进化算法.即在每代进化前将群体分为可行个体和不可行个体两类,对不可行个体,用差量法将其逐个转化为可行个体,并保持种群规模不变,经过一序列的进化后,计算所有可行个体的适应度并找到问题的最优解.对5个经典函数进行了优化测试,测试结果表明提出的算法对求解约束优化问题是有效的.     

Contributions to the quadratic assignment problem

Tree search procedures for solving the Koopmans Beckmann quadratic assignment problem (QAP) are unable to solve any reasonable size QAP's mainly because good quality lower bounds for this problem cannot be computed.The purpose of this paper is to propose a bounding technique based on the extraction from the QAP formulation, of a large linear assignment problem (which can then be solved optimally), leaving as a residual problem as ‘small’ a QAP as possible. The solution of this residual QAP can then be bounded by a separate procedure. This 2-step method produces improved bounds as compared with those produced by the direct application of the bounding algorithms to the original QAP. In addition, a procedure is described for the a priori fixing of variables in the QAP formulation, thus reducing the number of variables in the problem.     

A simplicial branch and bound duality-bounds algorithm for the linear sum-of-ratios problem

In this article, we present and validate a simplicial branch and bound duality-bounds algorithm for globally solving the linear sum-of-ratios fractional program. The algorithm computes the lower bounds called for during the branch and bound search by solving ordinary linear programming problems. These problems are derived by using Lagrangian duality theory. The algorithm applies to a wide class of linear sum-of-ratios fractional programs. Two sample problems are solved, and the potential practical and computational advantages of the algorithm are indicated.     

隐互补问题的极小化变形及其稳定点

1 引言 互补问题在最优化中有着广泛的应用,例如线性规划中的对偶问题,非线性规划中求稳定点的KKT条件以及变分不等式的求解都可以转化为互补问题,另外,某些均衡网络设计问题、信号最优化问题以及交通配置等问题也可利用互补问题来求解.     

Convex relaxations of chance constrained optimization problems

In this paper we develop convex relaxations of chance constrained optimization problems in order to obtain lower bounds on the optimal value. Unlike existing statistical lower bounding techniques, our approach is designed to provide deterministic lower bounds. We show that a version of the proposed scheme leads to a tractable convex relaxation when the chance constraint function is affine with respect to the underlying random vector and the random vector has independent components. We also propose an iterative improvement scheme for refining the bounds.     

带策略约束的区间数双矩阵博弈的双线性规划求解方法

传统区间数双矩阵博弈理论研究局中人支付值为区间数的策略选择问题,但没有考虑局中人策略选择可能受到各种约束.创建一种求解局中人策略选择受约束且支付值为区间数的双矩阵博弈（简称带策略约束的区间数双矩阵博弈）的简单、有效的双线性规划求解方法.首先,将局中人的博弈支付看作支付值区间中数值的函数.通过证明这种函数具有单调性,据此利用支付值区间的上、下界,构造了一对辅助双线性规划模型,可分别用于显式地计算任意带策略约束的区间数双矩阵博弈中局中人区间数博弈支付的上、下界及其相应的最优策略.最后,利用考虑策略约束条件下企业和政府针对发展低碳经济策略问题的算例,通过比较其与不考虑策略约束情形下的结果,说明了提出的模型和方法的有效性、优越性及可应用性.     

Global solution of bilevel programs with a nonconvex inner program

A bounding algorithm for the global solution of nonlinear bilevel programs involving nonconvex functions in both the inner and outer programs is presented. The algorithm is rigorous and terminates finitely to a point that satisfies ε-optimality in the inner and outer programs. For the lower bounding problem, a relaxed program, containing the constraints of the inner and outer programs augmented by a parametric upper bound to the parametric optimal solution function of the inner program, is solved to global optimality. The optional upper bounding problem is based on probing the solution obtained by the lower bounding procedure. For the case that the inner program satisfies a constraint qualification, an algorithmic heuristic for tighter lower bounds is presented based on the KKT necessary conditions of the inner program. The algorithm is extended to include branching, which is not required for convergence but has potential advantages. Two branching heuristics are described and analyzed. Convergence proofs are provided and numerical results for original test problems and for literature examples are presented.     

Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality

The multiconstraint 0–1 knapsack problem is encountered when one has to decide how to use a knapsack with multiple resource constraints. Even though the single constraint version of this problem has received a lot of attention, the multiconstraint knapsack problem has been seldom addressed. This paper deals with developing an effective solution procedure for the multiconstraint knapsack problem. Various relaxation of the problem are suggested and theoretical relations between these relaxations are pointed out. Detailed computational experiments are carried out to compare bounds produced by these relaxations. New algorithms for obtaining surrogate bounds are developed and tested. Rules for reducing problem size are suggested and shown to be effective through computational tests. Different separation, branching and bounding rules are compared using an experimental branch and bound code. An efficient branch and bound procedure is developed, tested and compared with two previously developed optimal algorithms. Solution times with the new procedure are found to be considerably lower. This procedure can also be used as a heuristic for large problems by early termination of the search tree. This scheme was tested and found to be very effective.     

A branch-reduce-cut algorithm for the global optimization of probabilistically constrained linear programs

We consider probabilistically constrained linear programs with general distributions for the uncertain parameters. These problems involve non-convex feasible sets. We develop a branch-and-bound algorithm that searches for a global optimal solution to this problem by successively partitioning the non-convex feasible region and by using bounds on the objective function to fathom inferior partition elements. This basic algorithm is enhanced by domain reduction and cutting plane strategies to reduce the size of the partition elements and hence tighten bounds. The proposed branch-reduce-cut algorithm exploits the monotonicity properties inherent in the problem, and requires solving linear programming subproblems. We provide convergence proofs for the algorithm. Some illustrative numerical results involving problems with discrete distributions are presented.     

A Branch-and-Price algorithm for the Single Source Capacitated Plant Location Problem

This paper considers the Single Source Capacitated Plant Location Problem (SSCPLP). We propose an exact algorithm in which a column generation procedure for finding upper and lower bounds is incorporated within a Branch-and-Price framework. The bounding procedure exploits the structure of the problem by means of an iterative approach. At each iteration, a two-level optimization problem is considered. The two levels correspond with the two decisions to be taken: first, the selection of a subset of plants to be opened and then, the allocation of clients within the subset of open plants. The second level subproblem is solved using column generation. The algorithm has been tested with different sets of test problems and the obtained results are satisfactory.     

Approximate and exact algorithms for the double-constrained two-dimensional guillotine cutting stock problem

In this paper, we propose approximate and exact algorithms for the double constrained two-dimensional guillotine cutting stock problem (DCTDC). The approximate algorithm is a two-stage procedure. The first stage attempts to produce a starting feasible solution to DCTDC by solving a single constrained two dimensional cutting problem, CDTC. If the solution to CTDC is not feasible to DCTDC, the second stage is used to eliminate non-feasibility. The exact algorithm is a branch-and-bound that uses efficient lower and upper bounding schemes. It starts with a lower bound reached by the approximate two-stage algorithm. At each internal node of the branching tree, a tailored upper bound is obtained by solving (relaxed) knapsack problems. To speed up the branch and bound, we implement, in addition to ordered data structures of lists, symmetry, duplicate, and non-feasibility detection strategies which fathom some unnecessary branches. We evaluate the performance of the algorithm on different problem instances which can become benchmark problems for the cutting and packing literature.     

A smoothing QP-free infeasible method for nonlinear inequality constrained optimization

In this paper,a smoothing QP-free infeasible method is proposed for nonlinear inequality constrained optimization problems.This iterative method is based on the solution of nonlinear equations which is obtained by the multipliers and the smoothing Fisher-Burmeister function for the KKT first-order optimality conditions.Comparing with other QP-free methods, this method does not request the strict feasibility of iteration.In particular,this method is implementable and globally convergent without assuming the strict complementarity condition and the isolatedness of accumulation points.Furthermore,the gradients of active constraints are not requested to be linearly independent.Preliminary numerical results indicate that this smoothing QP-free infeasible method is quite promising.     

A two-phase algorithm for the partial accessibility constrained vehicle routing problem

In the partial accessibility constrained vehicle routing problem, a route can be covered by two types of vehicles, i.e. truck or truck + trailer. Some customers are accessible by both vehicle types, whereas others solely by trucks. After introducing an integer programming formulation for the problem, we describe a two-phase heuristic method which extends a classical vehicle routing algorithm. Since it is necessary to solve a combinatorial problem that has some similarities with the generalized assignment problem, we propose an enumerative procedure in which bounds are obtained from a Lagrangian relaxation. The routine provides very encouraging results on a set of test problems.     

Improved semidefinite bounding procedure for solving Max-Cut problems to optimality

We present an improved algorithm for finding exact solutions to Max-Cut and the related binary quadratic programming problem, both classic problems of combinatorial optimization. The algorithm uses a branch-(and-cut-)and-bound paradigm, using standard valid inequalities and nonstandard semidefinite bounds. More specifically, we add a quadratic regularization term to the strengthened semidefinite relaxation in order to use a quasi-Newton method to compute the bounds. The ratio of the tightness of the bounds to the time required to compute them depends on two real parameters; we show how adjusting these parameters and the set of strengthening inequalities gives us a very efficient bounding procedure. Embedding our bounding procedure in a generic branch-and-bound platform, we get a competitive algorithm: extensive experiments show that our algorithm dominates the best existing method.     

Smart greedy procedure for solving a nOnlinear knapsack class of reliability optimization problems

A new heuristic procedure, which is called Smart Greedy, is proposed for solving a kind of general reliability optimization problems (non-DGR type knapsack problems). Smart Greedy uses Recursive Greedy with multiple greedy functions designated by balance coefficients, generates several solutions and then determines the best solution among them as the smart greedy solution. Recursive Greedy first checks the feasibility of sets of items for a given problem and removes infeasible items from the item sets. Second, the procedure checks the gain ratio of increments of objective function to constraint function and reduces the problem to DGR type problem by invoking LP dominance. Third, the procedure continues to allocate the increments for current items until the constraint is violated. With the current solution, the procedure then repeats the greedy procedure for current items that are added to the items removed by the LP dominance in the previous step.Computational results show that the Smart Greedy is more effective than the previously reported methods.