The following article presents and corroborates an outcome space branch-and-bound algorithm for solving the general linear multiplicative programming problem (GLMPP). In this new algorithm, GLMPP is transformed into i...
详细信息
The following article presents and corroborates an outcome space branch-and-bound algorithm for solving the general linear multiplicative programming problem (GLMPP). In this new algorithm, GLMPP is transformed into its equivalent problem by introducing auxiliary variables. To compute the tight upper bound for the optimal value of GLMPP, the linear relaxation programming problem is assembled by using bound and hull linear approximations. Furthermore, the global convergence and computational complexity of the algorithm are demonstrated. Finally, the soundness and advantage of the proposed algorithm are validated by solving a demonstrative linearmultiplicative problem.
This paper proposes an outer space branch-reduction-bound algorithm by using the second- order cone relaxation technique with regional reduction strategy for solving generalized linear multiplicative programming (GLMP...
详细信息
This paper proposes an outer space branch-reduction-bound algorithm by using the second- order cone relaxation technique with regional reduction strategy for solving generalized linear multiplicative programming (GLMP) problems. Firstly, by introducing additional variables and performing several equivalent transformations, the GLMP problem is converted into an equivalent problem that is easier to solve. Next, the non-convex quadratic constraint in the equivalent problem is handled utilizing the secant approximation method to formulate the second-order cone relaxation problem. Subsequently, we incorporate a regional reduction technique into the algorithm to enhance its computational performance and estimate the worst-case computational complexity, ensuring the attainment of the global optimal solution. Finally, numerical experimental results demonstrate that the proposed algorithm can efficiently search for the global epsilon-optimal solution of the test examples and can successfully solve high-dimensional GLMP problems with a small number of linear functions.
This paper studies a class of linearmultiplicative problems (LMP). To find a global optimal solution of problem (LMP), we first convert problem (LMP) into an equivalent problem (EP) via auxiliary variables, then prob...
详细信息
This paper studies a class of linearmultiplicative problems (LMP). To find a global optimal solution of problem (LMP), we first convert problem (LMP) into an equivalent problem (EP) via auxiliary variables, then problem (EP) is expressed as a two-layer problem (EP1). On the basis of problems (EP) and (EP1), a new bounding technique which integrates two linear relaxation processes is proposed to obtain a valid lower bound for the optimal value of (LMP). Combining the bounding technique with the bisection branching rule, a novel branch and bound algorithm is designed. Also, we establish the global convergence of the proposed algorithm and estimate its computational complexity. Preliminary numerical results verify the feasibility and effectiveness of the presented method.
In this paper, we consider a linear multiplicative programming problem (LMP) that is known to be NP-hard even with one product term. We first introduce the auxiliary variables to obtain an equivalent problem of proble...
详细信息
In this paper, we consider a linear multiplicative programming problem (LMP) that is known to be NP-hard even with one product term. We first introduce the auxiliary variables to obtain an equivalent problem of problem LMP. An outer space branch and bound algorithm is then designed, which integrates some basic operations such as the linear relaxation technique, branching rule and region reduction technique. The global convergence of the proposed algorithm is established by means of the subsequent solutions of a series of linearprogramming problems, and its computational complexity is estimated on the basis of the branching rule. Also, we discuss the relationship between the proposed linear relaxation and existing relaxations for LMP. Finally, preliminary numerical results demonstrate the proposed algorithm can efficiently find the globally optimal solutions for test instances.
The nonconvex problem of minimizing the sum of a linear function and the product of two linear functions over a convex polyhedron is considered. A finite algorithm is proposed which either finds a global optimum or sh...
详细信息
The nonconvex problem of minimizing the sum of a linear function and the product of two linear functions over a convex polyhedron is considered. A finite algorithm is proposed which either finds a global optimum or shows that the objective function is unbounded from below in the feasible region. This is done by means of a sequence of primal and/or dual simplex iterations.
In this paper, a new global algorithm is presented to globally solve the linear multiplicative programming（LMP）. The problem（LMP） is firstly converted into an equivalent programming problem（LMP（H））by introduci...
详细信息
In this paper, a new global algorithm is presented to globally solve the linear multiplicative programming（LMP）. The problem（LMP） is firstly converted into an equivalent programming problem（LMP（H））by introducing p auxiliary variables. Then by exploiting structure of（LMP（H））, a linear relaxation programming（LP（H）） of（LMP（H）） is obtained with a problem（LMP） reduced to a sequence of linearprogramming problems. The algorithm is used to compute the lower bounds called the branch and bound search by solving linear relaxation programming problems（LP（H））. The proposed algorithm is proven that it is convergent to the global minimum through the solutions of a series of linearprogramming problems. Some examples are given to illustrate the feasibility of the proposed algorithm.
On the basis of Soland's rectangular branch-and-bound, we develop an algorithm for minimizing a product of p (greater than or equal to2) affine functions over a polytope. To tighten the lower bound on the value of...
详细信息
On the basis of Soland's rectangular branch-and-bound, we develop an algorithm for minimizing a product of p (greater than or equal to2) affine functions over a polytope. To tighten the lower bound on the value of each subproblem, we install a second-stage bounding procedure, which requires O(p) additional time in each iteration but remarkably reduces the number of branching operations. Computational results indicate that the algorithm is practical if p is less than 15, both in finding an exact optimal solution and an approximate solution.
This article presents a rectangular branch-and-bound algorithm with standard bisection rule for solving linearmultiplicative problem (LMP). In this algorithm, a novel linear relaxation technique is presented for deri...
详细信息
This article presents a rectangular branch-and-bound algorithm with standard bisection rule for solving linearmultiplicative problem (LMP). In this algorithm, a novel linear relaxation technique is presented for deriving the linear relaxation programming of problem LMP, which has separable characteristics and can be used to acquire the upper bound of the optimal value to problem LMP. Thus, to obtain a global optimal solution for problem LMP, the main computational work of the algorithm involves the solutions of a sequence of linearprogramming problems. Moreover, the proof of its convergence property and the numerical result show the feasibility and efficiency of the presented algorithm.
作者：
Matsui, TUNIV TOKYO
FAC ENGNDEPT MATH ENGN & INFORMAT PHYSBUNKYO KUTOKYO 113JAPAN
The linear multiplicative programming problem minimizes a product of two (positive) variables subject to linear inequality constraints. In this paper, we show NP-hardness of linear multiplicative programming problems ...
详细信息
The linear multiplicative programming problem minimizes a product of two (positive) variables subject to linear inequality constraints. In this paper, we show NP-hardness of linear multiplicative programming problems and related problems.
This paper presents an outcome-space finite algorithm for solving linear multiplicative programming, in each iteration of which a convex quadratic programming is only solved. In the paper, we give a global optimizatio...
详细信息
This paper presents an outcome-space finite algorithm for solving linear multiplicative programming, in each iteration of which a convex quadratic programming is only solved. In the paper, we give a global optimization condition on a class of multiplicativeprogramming problems and prove that the proposed algorithm is finite terminative and gain a global optimal solution of the former problem when it stops. It can be shown by the numerical results that the proposed algorithm is effective and the computational results can be gained in short time. (c) 2005 Elsevier Inc. All rights reserved.
暂无评论