解带有二次约束非凸二次规划问题的一个分枝缩减方法

在这篇论文里,有机地把外逼近方法与分枝定界技术结合起来,提出了解带有二次约束非凸二次规划问题的一个分枝缩减方法;给出了原问题的一个新的线性规划松弛,以便确定它在超矩形上全局最优值的一个下界;利用超矩形的一个深度二级剖分方法,以及超矩形的缩减和删除技术,提高算法的收敛速度;证明了在知道原问题可行点的条件下,该算法在有限步里就可以获得原问题的一个全局最优化解,并且用一个例子说明了该算法是有效的.     

Cutting circles and polygons from area-minimizing rectangles

A set of circles, rectangles, and convex polygons are to be cut from rectangular design plates to be produced, or from a set of stocked rectangles of known geometric dimensions. The objective is to minimize the area of the design rectangles. The design plates are subject to lower and upper bounds of their widths and lengths. The objects are free of any orientation restrictions. If all nested objects fit into one design or stocked plate the problem is formulated and solved as a nonconvex nonlinear programming problem. If the number of objects cannot be cut from a single plate, additional integer variables are needed to represent the allocation problem leading to a nonconvex mixed integer nonlinear optimization problem. This is the first time that circles and arbitrary convex polygons are treated simultaneously in this context. We present exact mathematical programming solutions to both the design and allocation problem. For small number of objects to be cut we compute globally optimal solutions. One key idea in the developed NLP and MINLP models is to use separating hyperplanes to ensure that rectangles and polygons do not overlap with each other or with the circles. Another important idea used when dealing with several resource rectangles is to develop a model formulation which connects the binary variables only to the variables representing the center of the circles or the vertices of the polytopes but not to the non-overlap or shape constraints. We support the solution process by symmetry breaking constraints. In addition we compute lower bounds, which are constructed by a relaxed model in which each polygon is replaced by the largest circle fitting into that polygon. We have successfully applied several solution techniques to solve this problem among them the Branch&Reduce Optimization Navigator (BARON) and the LindoGlobal solver called from GAMS, and, as described in Rebennack et al. [21], a column enumeration approach in which the columns represent the assignments. Good feasible solutions are computed within seconds or minutes usually during preprocessing. In most cases they turn out to be globally optimal. For up to 10 circles, we prove global optimality up to a gap of the order of 10^?8 in short time. Cases with a modest number of objects, for instance, 6 circles and 3 rectangles, are also solved in short time to global optimality. For test instances involving non-rectangular polygons it is difficult to obtain small gaps. In such cases we are content to obtain gaps of the order of 10%.     

Optimizing acyclic traffic signal switching sequences through an Extended Linear Complementarity Problem formulation

In this paper we first show how the Extended Linear Complementarity Problem, which is a mathematical programming problem, can be used to design optimal switching schemes for a class of switched systems with linear dynamics subject to saturation. More specifically, we consider the determination of the optimal switching time instants (the switching sequences are acyclic, but the phase sequence is pre-fixed). Although this method yields globally optimal switching time sequences, it is not feasible in practice due to its computational complexity. Therefore, we also discuss some approximations that lead to suboptimal switching time sequences that can be computed very efficiently and for which the value of the objective function is close to the global optimum. Finally we use these results to design optimal switching time sequences for a traffic signal controlled intersection so as to minimize criteria such as average queue length, worst case queue length, average waiting time, and so on.     

Packing ellipsoids into volume-minimizing rectangular boxes

A set of tri-axial ellipsoids, with given semi-axes, is to be packed into a rectangular box; its widths, lengths and height are subject to lower and upper bounds. We want to minimize the volume of this box and seek an overlap-free placement of the ellipsoids which can take any orientation. We present closed non-convex NLP formulations for this ellipsoid packing problem based on purely algebraic approaches to represent rotated and shifted ellipsoids. We consider the elements of the rotation matrix as variables. Separating hyperplanes are constructed to ensure that the ellipsoids do not overlap with each other. For up to 100 ellipsoids we compute feasible points with the global solvers available in GAMS. Only for special cases of two ellipsoids we are able to reach gaps smaller than \(10^{-4}\).     

A new global optimization approach for convex multiplicative programming

In this paper, by solving the relaxed quasiconcave programming problem in outcome space, a new global optimization algorithm for convex multiplicative programming is presented. Two kinds of techniques are employed to establish the algorithm. The first one is outer approximation technique which is applied to shrink relaxation area of quasiconcave programming problem and to compute appropriate feasible points and to raise the capacity of bounding. And the other one is branch and bound technique which is used to guarantee global optimization. Some numerical results are presented to demonstrate the effectiveness and feasibility of the proposed algorithm.     

The final NETLIB-LP results

With standard linear programming solvers there is always some uncertainty about the precise values of the optimal solutions. We implemented a program using exact rational arithmetic to compute proofs for the feasibility and optimality of an LP solution. This paper reports the exact optimal objective values for all NETLIB problems.     

A robust algorithm for generalized geometric programming

Most existing methods of global optimization for generalized geometric programming (GGP) actually compute an approximate optimal solution of a linear or convex relaxation of the original problem. However, these approaches may sometimes provide an infeasible solution, or far from the true optimum. To overcome these limitations, a robust solution algorithm is proposed for global optimization of (GGP) problem. This algorithm guarantees adequately to obtain a robust optimal solution, which is feasible and close to the actual optimal solution, and is also stable under small perturbations of the constraints.     

一种求解二次约束二次规划问题的自适应全局优化算法

为了更好地解决二次约束二次规划问题(QCQP), 本文基于分支定界算法框架提出了自适应线性松弛技术, 在理论上证明了这种新的定界技术对于解决(QCQP)是可观的。文中分支操作采用条件二分法便于对矩形进行有效剖分; 通过缩减技术删除不包含全局最优解的部分区域, 以加快算法的收敛速度。最后, 通过数值结果表明提出的算法是有效可行的。     

一种求解二次约束二次规划问题的自适应全局优化算法

为了更好地解决二次约束二次规划问题(QCQP), 本文基于分支定界算法框架提出了自适应线性松弛技术, 在理论上证明了这种新的定界技术对于解决(QCQP)是可观的。文中分支操作采用条件二分法便于对矩形进行有效剖分; 通过缩减技术删除不包含全局最优解的部分区域, 以加快算法的收敛速度。最后, 通过数值结果表明提出的算法是有效可行的。     

Solving Planning and Design Problems in the Process Industry Using Mixed Integer and Global Optimization

This contribution gives an overview on the state-of-the-art and recent advances in mixed integer optimization to solve planning and design problems in the process industry. In some case studies specific aspects are stressed and the typical difficulties of real world problems are addressed. Mixed integer linear optimization is widely used to solve supply chain planning problems. Some of the complicating features such as origin tracing and shelf life constraints are discussed in more detail. If properly done the planning models can also be used to do product and customer portfolio analysis. We also stress the importance of multi-criteria optimization and correct modeling for optimization under uncertainty. Stochastic programming for continuous LP problems is now part of most optimization packages, and there is encouraging progress in the field of stochastic MILP and robust MILP. Process and network design problems often lead to nonconvex mixed integer nonlinear programming models. If the time to compute the solution is not bounded, there are already a commercial solvers available which can compute the global optima of such problems within hours. If time is more restricted, then tailored solution techniques are required.     

Polylithic modeling and solution approaches using algebraic modeling systems

Based on the Greek term monolithos (stone consisting of one single block) Kallrath (Comput Chem Eng 33:1983–1993, 2009) introduced the term polylithic for modeling and solution approaches in which mixed integer or non-convex nonlinear optimization problems are solved by tailor-made methods involving several models and/or algorithmic components, in which the solution of one model is input to another one. This can be exploited to initialize certain variables, or to provide bounds on them (problem-specific preprocessing). Mathematical examples of polylithic approaches are decomposition techniques, or hybrid methods in which constructive heuristics and local search improvement methods are coupled with exact MIP algorithms. Tailor-made polylithic solution approaches with thousands or millions of solve statements are challenges on algebraic modeling languages. Local objects and procedural structures are almost necessary. Warm-start and hot-start techniques can be essential. The effort of developing complex tailor-made polylithic solutions is awarded by enabling us to solve real-world problems far beyond the limits of monolithic approaches and general purpose solvers.     

On solving L-SR1 trust-region subproblems

In this article, we consider solvers for large-scale trust-region subproblems when the quadratic model is defined by a limited-memory symmetric rank-one (L-SR1) quasi-Newton matrix. We propose a solver that exploits the compact representation of L-SR1 matrices. Our approach makes use of both an orthonormal basis for the eigenspace of the L-SR1 matrix and the Sherman–Morrison–Woodbury formula to compute global solutions to trust-region subproblems. To compute the optimal Lagrange multiplier for the trust-region constraint, we use Newton’s method with a judicious initial guess that does not require safeguarding. A crucial property of this solver is that it is able to compute high-accuracy solutions even in the so-called hard case. Additionally, the optimal solution is determined directly by formula, not iteratively. Numerical experiments demonstrate the effectiveness of this solver.     

A global continuation algorithm for solving binary quadratic programming problems

In this paper, we propose a new continuous approach for the unconstrained binary quadratic programming (BQP) problems based on the Fischer-Burmeister NCP function. Unlike existing relaxation methods, the approach reformulates a BQP problem as an equivalent continuous optimization problem, and then seeks its global minimizer via a global continuation algorithm which is developed by a sequence of unconstrained minimization for a global smoothing function. This smoothing function is shown to be strictly convex in the whole domain or in a subset of its domain if the involved barrier or penalty parameter is set to be sufficiently large, and consequently a global optimal solution can be expected. Numerical results are reported for 0-1 quadratic programming problems from the OR-Library, and the optimal values generated are made comparisons with those given by the well-known SBB and BARON solvers. The comparison results indicate that the continuous approach is extremely promising by the quality of the optimal values generated and the computational work involved, if the initial barrier parameter is chosen appropriately. This work is partially supported by the Doctoral Starting-up Foundation (B13B6050640) of GuangDong Province.     

线性半向量二层规划问题的全局优化方法

研究了线性半向量二层规划问题的全局优化方法. 利用下层问题的对偶间隙构造了线性半向量二层规划问题的罚问题, 通过分析原问题的最优解与罚问题可行域顶点之间的关系, 将线性半向量二层规划问题转化为有限个线性规划问题, 从而得到线性半向量二层规划问题的全局最优解. 数值结果表明所设计的全局优化方法对线性半向量二层规划问题是可行的.     

Optimal value range in interval linear programming

We deal with the linear programming problem in which input data can vary in some given real compact intervals. The aim is to compute the exact range of the optimal value function. We present a general approach to the situation the feasible set is described by an arbitrary linear interval system. Moreover, certain dependencies between the constraint matrix coefficients can be involved. As long as we are able to characterize the primal and dual solution set (the set of all possible primal and dual feasible solutions, respectively), the bounds of the objective function result from two nonlinear programming problems. We demonstrate our approach on various cases of the interval linear programming problem (with and without dependencies).     

Optimal module sizing in VLSI floorplanning by nonlinear programming

Floorplanning is the VLSI design problem of deciding the position and shapes of all modules (e.g., memory or random logic) in order to minimize the chip area and satisfy all constraints. The modules may not be fixed in shape — the ratio of height to width may be modified in order to achieve minimal chip area. In the CADRE (AT&T) and Planar Package Planner (IBM) floorplanning systems, relative positions of the modules are specified by a relative position graph. Given the relative positions, a heuristic attempts to determine the optimal shape of each module, subject to the relative orientations dictated by the graph and also interconnection requirements, to minimize the chip area. In CADRE, the heuristics iterate between improving horizontal and vertical module dimensions; the IBM system uses a Simplex-method based heuristic. These heuristics are not guaranteed to solve the problem exactly. Consequently, it is not known how far the heuristic solution is from optimal, and it is not obvious when to terminate the heuristic. In this paper we show that, given the relative positions, we can compute theprovably optimal shape of each module, by transforming the problem into a convex nonlinear programming problem. Each local minimum of such a problem must also be a global minimum. We illustrate the method by applying it to an example solved by IBM.     

A variable neighborhood search based matheuristic for nurse rostering problems

A practical nurse rostering problem, which arises at a ward of an Italian private hospital, is considered. In this problem, it is required each month to assign shifts to the nursing staff subject to various requirements. A matheuristic approach is introduced, based on a set of neighborhoods iteratively searched by a commercial integer programming solver within a defined global time limit, relying on a starting solution generated by the solver running on the general integer programming formulation of the problem. Generally speaking, a matheuristic algorithm is a heuristic algorithm that uses non trivial optimization and mathematical programming tools to explore the solutions space with the aim of analyzing large scale neighborhoods. Randomly generated instances, based on the considered nurse rostering problem, were solved and solutions computed by the proposed procedure are compared to the solutions achieved by pure solvers within the same time limit. The results show that the proposed solution approach outperforms the solvers in terms of solution quality. The proposed approach has also been tested on the well known Nurse Rostering Competition instances where several new best results were reached.     

An approximately global optimization method for assortment problems

Assortment problems occur when we want to cut a number of small rectangular pieces from a large rectangle to get the minimum area within the rectangle. Recently, Chen et al. proposed a useful model for assortment problems. Although Chen et al.'s model is quite promising to find solutions, there are two inadequacies in their model: firstly, the objective function in their model is a polynomial term, which may not lead to a globally optimal solution; secondly, too many 0–1 variables are used to formulate the non-overlapping constraints. We propose a new method to reformulate an assortment model. Our model is not only able to find the approximately global optimal solution, but involves less 0–1 variables for formulating non-overlapping constraints.     

Globally convergent DC trust-region methods

In this paper, we investigate the use of DC (Difference of Convex functions) models and algorithms in the application of trust-region methods to the solution of a class of nonlinear optimization problems where the constrained set is closed and convex (and, from a practical point of view, where projecting onto the feasible region is computationally affordable). We consider DC local models for the quadratic model of the objective function used to compute the trust-region step, and apply a primal-dual subgradient method to the solution of the corresponding trust-region subproblems. One is able to prove that the resulting scheme is globally convergent to first-order stationary points. The theory requires the use of exact second-order derivatives but, in turn, the computation of the trust-region step asks only for one projection onto the feasible region (in comparison to the calculation of the generalized Cauchy point which may require more). The numerical efficiency and robustness of the proposed new scheme when applied to bound-constrained problems is measured by comparing its performance against some of the current state-of-the-art nonlinear programming solvers on a vast collection of test problems.     

One-level reformulation of the bilevel Knapsack problem using dynamic programming

In this paper, we consider the Bilevel Knapsack Problem (BKP), which is a hierarchical optimization problem in which the feasible set is determined by the set of optimal solutions for a parametric Knapsack Problem. We introduce a new reformulation of the BKP into a one-level integer programming problem using dynamic programming. We propose an algorithm that allows the BKP to be solved exactly in two steps. In the first step, a dynamic programming algorithm is used to compute the set of follower reactions to leader decisions. In the second step, an integer problem that is equivalent to the BKP is solved using a branch-and-bound algorithm. Numerical results are presented to show the performance of our method.