共查询到20条相似文献,搜索用时 46 毫秒
1.
In this paper, we consider a special class of nonconvex programming problems for which the objective function and constraints
are defined in terms of general nonconvex factorable functions. We propose a branch-and-bound approach based on linear programming
relaxations generated through various approximation schemes that utilize, for example, the Mean-Value Theorem and Chebyshev
interpolation polynomials coordinated with a Reformulation-Linearization Technique (RLT). A suitable partitioning process
is proposed that induces convergence to a global optimum. The algorithm has been implemented in C++ and some preliminary computational
results are reported on a set of fifteen engineering process control and design test problems from various sources in the
literature. The results indicate that the proposed procedure generates tight relaxations, even via the initial node linear
program itself. Furthermore, for nine of these fifteen problems, the application of a local search method that is initialized
at the LP relaxation solution produced the actual global optimum at the initial node of the enumeration tree. Moreover, for
two test cases, the global optimum found improves upon the solutions previously reported in the source literature.
Received: January 14, 1998 / Accepted: June 7, 1999?Published online December 15, 2000 相似文献
2.
In this paper, we propose two sets of theoretically filtered bound-factor constraints for constructing reformulation-linearization technique (RLT)-based linear programming (LP) relaxations for solving polynomial programming problems. We establish related theoretical results for convergence to a global optimum for these reduced sized relaxations, and provide insights into their relative sizes and tightness. Extensive computational results are provided to demonstrate the relative effectiveness of the proposed theoretical filtering strategies in comparison to the standard RLT and a prior heuristic filtering technique using problems from the literature as well as randomly generated test cases. 相似文献
3.
This paper studies the global optimization of polynomial programming problems using Reformulation-Linearization Technique
(RLT)-based linear programming (LP) relaxations. We introduce a new class of bound-grid-factor constraints that can be judiciously used to augment the basic RLT relaxations in order to improve the quality of lower bounds
and enhance the performance of global branch-and-bound algorithms. Certain theoretical properties are established that shed
light on the effect of these valid inequalities in driving the discrepancies between RLT variables and their associated nonlinear
products to zero. To preserve computational expediency while promoting efficiency, we propose certain concurrent and sequential
cut generation routines and various grid-factor selection rules. The results indicate a significant tightening of lower bounds,
which yields an overall reduction in computational effort for solving a test-bed of polynomial programming problems to global
optimality in comparison with the basic RLT procedure as well as the commercial software BARON. 相似文献
4.
5.
P. Boyvalenkov 《Discrete and Computational Geometry》1995,14(1):167-183
We investigate two extremal problems for polynomials giving upper bounds for spherical codes and for polynomials giving lower
bounds for spherical designs, respectively. We consider two basic properties of the solutions of these problems. Namely, we
estimate from below the number of double zeros and find zero Gegenbauer coefficients of extremal polynomials. Our results
allow us to search effectively for such solutions using a computer. The best polynomials we have obtained give substantial
improvements in some cases on the previously known bounds for spherical codes and designs. Some examples are given in Section
6.
This research was partially supported by the Bulgarian NSF under Contract I-35/1994. 相似文献
6.
In this paper, we present a Dantzig-Wolfe reformulation for the Minimum Cost Hop-and-root Constrained Forest Problem and discuss a Column Generation (CG) method to evaluate its Linear Programming (LP) bounds. For solving one of two types of pricing problems that arise in CG, we compared two solution strategies: Dynamic Programming and a Branch-and-cut (BC) algorithm. In general, CG performed much better when BC was used. Not only the LP bounds implied by the proposed reformulation are much stronger than the multi-commodity flow bounds from the literature, but also could be evaluated with less computational time. A Column Generation Heuristic was discussed and implemented, providing upper bounds that are, on average, within 2.3% of optimality. 相似文献
7.
Akshay Gupte Shabbir Ahmed Santanu S. Dey Myun Seok Cheon 《Journal of Global Optimization》2017,67(3):631-669
The pooling problem is a folklore NP-hard global optimization problem that finds applications in industries such as petrochemical refining, wastewater treatment and mining. This paper assimilates the vast literature on this problem that is dispersed over different areas and gives new insights on prevalent techniques. We also present new ideas for computing dual bounds on the global optimum by solving high-dimensional linear programs. Finally, we propose discretization methods for inner approximating the feasible region and obtaining good primal bounds. Valid inequalities are derived for the discretized models, which are formulated as mixed integer linear programs. The strength of our relaxations and usefulness of our discretizations is empirically validated on random test instances. We report best known primal bounds on some of the large-scale instances. 相似文献
8.
A Klose 《The Journal of the Operational Research Society》1999,50(2):157-166
In this paper, a linear programming based heuristic is considered for a two-stage capacitated facility location problem with single source constraints. The problem is to find the optimal locations of depots from a set of possible depot sites in order to serve customers with a given demand, the optimal assignments of customers to depots and the optimal product flow from plants to depots. Good lower and upper bounds can be obtained for this problem in short computation times by adopting a linear programming approach. To this end, the LP formulation is iteratively refined using valid inequalities and facets which have been described in the literature for various relaxations of the problem. After each reoptimisation step, that is the recalculation of the LP solution after the addition of valid inequalities, feasible solutions are obtained from the current LP solution by applying simple heuristics. The results of extensive computational experiments are given. 相似文献
9.
10.
CHENZHIPING C.A.J.HURKENS J.L.DEJONG 《高校应用数学学报(英文版)》1997,12(2):215-224
After giving a suitable model for the cutting strips problem, we present a branch-and-price algorithm for it by combining the column generation technique and the branch-and-hound method with LP relaxations. Some theoretical issues and implementation details about the algorithm are discussed, including the solution of the pricing subproblem, the quality of LP relaxations, the branching scheme as well as the column management. Finally, preliminary computarional experience is reported. 相似文献
11.
In this work we present a global optimization algorithm for solving a class of large-scale nonconvex optimization models that
have a decomposable structure. Such models, which are very expensive to solve to global optimality, are frequently encountered
in two-stage stochastic programming problems, engineering design, and also in planning and scheduling. A generic formulation
and reformulation of the decomposable models is given. We propose a specialized deterministic branch-and-cut algorithm to
solve these models to global optimality, wherein bounds on the global optimum are obtained by solving convex relaxations of
these models with certain cuts added to them in order to tighten the relaxations. These cuts are based on the solutions of
the sub-problems obtained by applying Lagrangean decomposition to the original nonconvex model. Numerical examples are presented
to illustrate the effectiveness of the proposed method compared to available commercial global optimization solvers that are
based on branch and bound methods. 相似文献
12.
In this paper, we develop methods for establishing improved bounds on the moduli of the zeros of complex and real polynomials. Specific (lacunary) as well as arbitrary polynomials are considered. The methods are applied to specific polynomials by way of example. Finally, we evaluate the quality of some bounds numerically. 相似文献
13.
Quadratic assignment problems (QAPs) are known to be among the hardest discrete optimization problems. Recent study shows
that even obtaining a strong lower bound for QAPs is a computational challenge. In this paper, we first discuss how to construct
new simple convex relaxations of QAPs based on various matrix splitting schemes. Then we introduce the so-called symmetric
mappings that can be used to derive strong cuts for the proposed relaxation model. We show that the bounds based on the new
models are comparable to some strong bounds in the literature. Promising experimental results based on the new relaxations
are reported. 相似文献
14.
P.Sz. Turchányi 《European Journal of Operational Research》1982,11(2):196-197
In this paper we present two lower bounds for the p-median problem, the problem of locating p facilities (medians) on a network. These bounds are based on two separate lagrangean relaxations of a zero-one formulation of the problem with subgradient optimisation being used to maximise these bounds. Penalty tests based on these lower bounds and a heuristically determined upper bound to the problem are developed and shown to result in a large reduction in problem size. The incorporation of the lower bounds and the penalty tests into a tree search procedure is described and computational results are given for problems with an arbitrary number of medians and having up to 200 vertices. A comparison is also made between these algorithms and the dual-based algorithm of Erlenkotter. 相似文献
15.
Edwin R. van Dam 《Journal of Algebraic Combinatorics》1998,7(3):321-332
We give a bound on the sizes of two sets of vertices at a given minimum distance in a graph in terms of polynomials and the Laplace spectrum of the graph. We obtain explicit bounds on the number of vertices at maximal distance and distance two from a given vertex, and on the size of two equally large sets at maximal distance. For graphs with four eigenvalues we find bounds on the number of vertices that are not adjacent to a given vertex and that have µ common neighbours with that vertex. Furthermore we find that the regular graphs for which the bounds are tight come from association schemes. 相似文献
16.
We study a discrete optimization problem introduced by Babai, Frankl, Kutin, and Štefankovi? (2001), which provides bounds on degrees of polynomials with p-adically controlled behavior. Such polynomials are of particular interest because they furnish bounds on the size of set systems satisfying Frankl-Wilson-type conditions modulo prime powers, with lower degree polynomials providing better bounds. We elucidate the asymptotic structure of solutions to the optimization problem, and we also provide an improved method for finding solutions in certain circumstances. 相似文献
17.
In this paper, we prove some relaxations of Hedetniemi’s conjecture in terms of altermatic number and strong altermatic number of graphs, two combinatorial parameters introduced by the present authors Alishahi and Hajiabolhassan (2015) providing two sharp lower bounds for the chromatic number of graphs. In terms of these parameters, we also introduce some sharp lower bounds for the chromatic number of the categorical product of two graphs. Using these lower bounds, we present some new families of graphs supporting Hedetniemi’s conjecture. 相似文献
18.
This paper considers the Optimum Communication Spanning Tree Problem. An integer programming formulation that yields tight
LP bounds is proposed. Given that the computational effort required to obtain the LP bounds considerably increases with the
size of the instances when using commercial solvers, we propose a Lagrangean relaxation that exploits the structure of the
formulation. Since feasible solutions to the Lagrangean function are spanning trees, upper bounds are also obtained. These
bounds are later improved with a simple local search. Computational experiments have been run on several benchmark instances
from the literature. The results confirm the interest of the proposal since tight lower and upper bounds are obtained, for
instances up to 100 nodes, in competitive computational times. 相似文献
19.
20.
The goal of this article is to obtain bounds on the coefficients of modular and integral flow and tension polynomials of graphs.
To this end we use the fact that these polynomials can be realized as Ehrhart polynomials of inside-out polytopes. Inside-out
polytopes come with an associated relative polytopal complex and, for a wide class of inside-out polytopes, we show that this
complex has a convex ear decomposition. This leads to the desired bounds on the coefficients of these polynomials. 相似文献