A global optimization using linear relaxation for generalized geometric programming

Many local optimal solution methods have been developed for solving generalized geometric programming (GGP). But up to now, less work has been devoted to solving global optimization of (GGP) problem due to the inherent difficulty. This paper considers the global minimum of (GGP) problems. By utilizing an exponential variable transformation and the inherent property of the exponential function and some other techniques the initial nonlinear and nonconvex (GGP) problem is reduced to a sequence of linear programming problems. The proposed algorithm is proven that it is convergent to the global minimum through the solutions of a series of linear programming problems. Test results indicate that the proposed algorithm is extremely robust and can be used successfully to solve the global minimum of (GGP) on a microcomputer.     

On generalized geometric programming problems with non-positive variables

Generalized geometric programming (GGP) problems occur frequently in engineering design and management. Some exponential-based decomposition methods have been developed for solving global optimization of GGP problems. However, the use of logarithmic/exponential transformations restricts these methods to handle the problems with strictly positive variables. This paper proposes a technique for treating non-positive variables with integer powers in GGP problems. By means of variable transformation, the GGP problem with non-positive variables can be equivalently solved with another one having positive variables. In addition, we present some computationally efficient convexification rules for signomial terms to enhance the efficiency of the optimization approach. Numerical examples are presented to demonstrate the usefulness of the proposed method in GGP problems with non-positive variables.     

A practicable branch-and-bound algorithm for globally solving linear multiplicative programming

To globally solve linear multiplicative programming problem (LMP), this paper presents a practicable branch-and-bound method based on the framework of branch-and-bound algorithm. In this method, a new linear relaxation technique is proposed firstly. Then, the branch-and-bound algorithm is developed for solving problem LMP. The proposed algorithm is proven that it is convergent to the global minimum by means of the subsequent solutions of a series of linear programming problems. Some experiments are reported to show the feasibility and efficiency of this algorithm.     

Global Optimization Algorithm for the Nonlinear Sum of Ratios Problem

This article presents a branch-and-bound algorithm for globally solving the nonlinear sum of ratios problem (P). The algorithm economizes the required computations by conducting the branch-and-bound search in ^p, rather than in ⁿ, where p is the number of ratios in the objective function of problem (P) and n is the number of decision variables in problem (P). To implement the algorithm, the main computations involve solving a sequence of convex programming problems for which standard algorithms are available.     

Global Maximization of a Generalized Concave Multiplicative Function

This article presents a branch-and-bound algorithm for globally solving the problem (P) of maximizing a generalized concave multiplicative function over a compact convex set. Since problem (P) does not seem to have been studied previously, the algorithm is apparently the first algorithm to be proposed for solving this problem. It works by globally solving a problem (P1) equivalent to problem (P). The branch-and-bound search undertaken by the algorithm uses rectangular partitioning and takes place in a space which typically has a much smaller dimension than the space to which the decision variables of problem (P) belong. Convergence of the algorithm is shown; computational considerations and benefits for users of the algorithm are given. A sample problem is also solved.     

Branch-and-Bound Outer Approximation Algorithm for Sum-of-Ratios Fractional Programs

In this article, a branch and-bound outer approximation algorithm is presented for globally solving a sum-of-ratios fractional programming problem. To solve this problem, the algorithm instead solves an equivalent problem that involves minimizing an indefinite quadratic function over a nonempty, compact convex set. This problem is globally solved by a branch-and-bound outer approximation approach that can create several closed-form linear inequality cuts per iteration. In contrast to pure outer approximation techniques, the algorithm does not require computing the new vertices that are created as these cuts are added. Computationally, the main work of the algorithm involves solving a sequence of convex programming problems whose feasible regions are identical to one another except for certain linear constraints. As a result, to solve these problems, an optimal solution to one problem can potentially be used to good effect as a starting solution for the next problem.     

An Efficient Algorithm for Quadratic Sum-of-Ratios Fractional Programs Problem

The quadratic sum-of-ratios fractional program problem has a broad range of applications in practical problems. This article will present an e?cient branch-and-bound algorithm for globally solving the quadratic sum-of-ratios fractional program problem. In this algorithm, lower bounds are computed by solving a series of parametric relaxation linear programming problems, which are established by utilizing new parametric linearizing technique. To enhance the computational speed of the proposed algorithm, a rectangle reducing tactic is used to reject a part of the investigated rectangle or the whole rectangle where there does not contain any global optimal solution of the quadratic sum-of-ratios fractional program problem. Compared with the known approaches, the proposed algorithm does not need to introduce new variables and constraints. Therefore, the proposed algorithm is more suitable for application in engineering.     

Branch-and-Price Algorithms for the One-Dimensional Cutting Stock Problem

We compare two branch-and-price approaches for the cutting stock problem. Each algorithm is based on a different integer programming formulation of the column generation master problem. One formulation results in a master problem with 0–1 integer variables while the other has general integer variables. Both algorithms employ column generation for solving LP relaxations at each node of a branch-and-bound tree to obtain optimal integer solutions. These different formulations yield the same column generation subproblem, but require different branch-and-bound approaches. Computational results for both real and randomly generated test problems are presented.     

Treating Free Variables in Generalized Geometric Global Optimization Programs

Generalized geometric programming (GGP) problems occur frequently in engineering design and management. Recently, some exponential-based decomposition methods [Maranas and Floudas, 1997,Computers and Chemical Engineering 21(4), 351–370; Floudas et al., 1999 , Handbook of Test Problems in Local and Global Optimization, Kluwer Academic Publishers, Boston, pp. 5–105; Floudas, 2000 Deterministic Global Optimizaion: Theory, Methods and Application, Kluwer Academic Publishers, Boston, pp. 257–306] have been developed for GGP problems. These methods can only handle problems with positive variables, and are incapable of solving more general GGP problems. This study proposes a technique for treating free (i.e., positive, zero or negative) variables in GGP problems. Computationally effective convexification rules are also provided for signomial terms with three variables.     

Solving Sum of Ratios Fractional Programs via Concave Minimization

This article presents an algorithm for globally solving a sum of ratios fractional programming problem. To solve this problem, the algorithm globally solves an equivalent concave minimization problem via a branch-and-bound search. The main work of the algorithm involves solving a sequence of convex programming problems that differ only in their objective function coefficients. Therefore, to solve efficiently these convex programming problems, an optimal solution to one problem can potentially be used to good advantage as a starting solution to the next problem.     

Solving the sum-of-ratios problem by a stochastic search algorithm

In spite of the recent progress in fractional programming, the sum-of-ratios problem remains untoward. Freund and Jarre proved that this is an NP-complete problem. Most methods overcome the difficulty using the deterministic type of algorithms, particularly, the branch-and-bound method. In this paper, we propose a new approach by applying the stochastic search algorithm introduced by Birbil, Fang and Sheu to a transformed image space. The algorithm then computes and moves sample particles in the q − 1 dimensional image space according to randomly controlled interacting electromagnetic forces. Numerical experiments on problems up to sum of eight linear ratios with a thousand variables are reported. The results also show that solving the sum-of-ratios problem in the image space as proposed is, in general, preferable to solving it directly in the primal domain.     

基于正弦型光滑打磨函数对0-1规划问题的连续化求解方法

传统的求解0-1规划问题方法大多属于直接离散的解法.现提出一个包含严格转换和近似逼近三个步骤的连续化解法:(1)借助阶跃函数把0-1离散变量转化为[0,1]区间上的连续变量;(2)对目标函数采用逼近折中阶跃函数近光滑打磨函数,约束条件采用线性打磨函数逼近折中阶跃函数,把0-1规划问题由离散问题转化为连续优化模型;(3)利用高阶光滑的解法求解优化模型.该方法打破了特定求解方法仅适用于特定类型0-1规划问题惯例,使求解0-1规划问题的方法更加一般化.在具体求解时,采用正弦型光滑打磨函数来逼近折中阶跃函数,计算效果很好.     

广义几何规划的压缩共轭梯度路径非单调信赖域算法(英文)

In this paper,on the basis of making full use of the characteristics of unconstrained generalized geometric programming（GGP）,we establish a nonmonotonic trust region algorithm via the conjugate path for solving unconstrained GGP problem.A new type of condensation problem is presented,then a particular conjugate path is constructed for the problem,along which we get the approximate solution of the problem by nonmonotonic trust region algorithm,and further prove that the algorithm has global convergence and quadratic convergence properties.     

Scatter Search—Wellsprings and Challenges

This article is concerned with two global optimization problems (P1) and (P2). Each of these problems is a fractional programming problem involving the maximization of a ratio of a convex function to a convex function, where at least one of the convex functions is a quadratic form. First, the article presents and validates a number of theoretical properties of these problems. Included among these properties is the result that, under a mild assumption, any globally optimal solution for problem (P1) must belong to the boundary of its feasible region. Also among these properties is a result that shows that problem (P2) can be reformulated as a convex maximization problem. Second, the article presents for the first time an algorithm for globally solving problem (P2). The algorithm is a branch and bound algorithm in which the main computational effort involves solving a sequence of convex programming problems. Convergence properties of the algorithm are presented, and computational issues that arise in implementing the algorithm are discussed. Preliminary indications are that the algorithm can be expected to provide a practical approach for solving problem (P2), provided that the number of variables is not too large.     

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.     

Improved logarithmic linearizing method for optimization problems with free-sign pure discrete signomial terms

Free-sign pure discrete signomial (FPDS) terms are vital to and are frequently observed in many nonlinear programming problems, such as geometric programming, generalized geometric programming, and mixed-integer non-linear programming problems. In this study, all variables in the FPDS term are discrete variables. Any improvement to techniques for linearizing FPDS term contributes significantly to the solving of nonlinear programming problems; therefore, relative techniques have continually been developed. This study develops an improved exact method to linearize a FPDS term into a set of linear programs with minimal logarithmic numbers of zero-one variables and constraints. This method is tighter than current methods. Various numerical experiments demonstrate that the proposed method is significantly more efficient than current methods, especially when the problem scale is large.     

Duality Bound Method for the General Quadratic Programming Problem with Quadratic Constraints

The purpose of this article is to develop a branch-and-bound algorithm using duality bounds for the general quadratically-constrained quadratic programming problem and having the following properties: (i) duality bounds are computed by solving ordinary linear programs; (ii) they are at least as good as the lower bounds obtained by solving relaxed problems, in which each nonconvex function is replaced by its convex envelope; (iii) standard convergence properties of branch-and-bound algorithms for nonconvex global optimization problems are guaranteed. Numerical results of preliminary computational experiments for the case of one quadratic constraint are reported.     

The Computational Implications of Variations in State Variable/State Ratios in Dynamic Programming and Total Enumeration

Dynamic programming computational efficiency rests upon the so-called principle of optimality, where it is possible to decompose combinatorial problems into individual sub-problems (stages). The sub-problems are solved independently and linked together through the use of the state variables which reflect optimal decisions for other (preceding) stages.A class of combinatorial problems which poses a particularly difficult challenge to dynamic programming methods is that which requires that decisions made in a given stage reflect the accumulation of decisions made in multiple preceding stages. It is generally accepted that such an increase in state space dimension is affected by computer storage limitations. In addition, it can be shown that such a problem structure can cause a dynamic-programming methodology to be inferior from the point of view of computation time as well.This phenomenon is demonstrated by varying the number of preceding stages whose decisions affect the pay-off determination for a given stage in five inventory models and solving the problems by both dynamic programming and total enumeration. In addition, a comparison of computational requirements to solve a problem of practical magnitude is presented. Computational results confirm that, owing to the nature of the interaction between overlapping shift schedules, total enumeration was superior to dynamic programming and branch-and-bound integer programming for a bank-clerk scheduling problem.     

Global optimization algorithm for sum of generalized polynomial ratios problem

In this paper, a global optimization algorithm is proposed for solving sum of generalized polynomial ratios problem (P) which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solve the problem (P). For such problems, we present a branch and bound algorithm. In this method, by utilizing exponent transformation and new three-level linear relaxation method, a sequence of linear relaxation programming of the initial nonconvex programming problem (P) are derived which are embedded in a branch and bound algorithm. The proposed method need not introduce new variables and constraints and it is convergent to the global minimum of prime problem by means of the subsequent solutions of a series of linear programming problems. Several numerical examples in the literatures are tested to demonstrate that the proposed algorithm can systematically solve these examples to find the approximate ?-global optimum.     

Links Between Linear Bilevel and Mixed 0–1 Programming Problems

We study links between the linear bilevel and linear mixed 0–1 programming problems. A new reformulation of the linear mixed 0–1 programming problem into a linear bilevel programming one, which does not require the introduction of a large finite constant, is presented. We show that solving a linear mixed 0–1 problem by a classical branch-and-bound algorithm is equivalent in a strong sense to solving its bilevel reformulation by a bilevel branch-and-bound algorithm. The mixed 0–1 algorithm is embedded in the bilevel algorithm through the aforementioned reformulation; i.e., when applied to any mixed 0–1 instance and its bilevel reformulation, they generate sequences of subproblems which are identical via the reformulation.