线性分式规划问题的多项式时间近似算法

本文针对线性比式和分式规划问题,提出一种求其全局最优解的完全多项式时间近似算法,并从理论上证明该算法的收敛性和计算复杂性,数值算例也说明了算法是可行的.     

Optimization of Polynomial Fractional Functions

A new approach is proposed for optimizing a polynomial fractional function under polynomial constraints, or more generally, a synomial fractional function under synomial constraints. The approach is based on reformulating the problem as the optimization of an increasing function under monotonic constraints.     

A note on the Lasserre hierarchy for different formulations of the maximum independent set problem

In this note, we consider several polynomial optimization formulations of the maximum independent set problem and the use of the Lasserre hierarchy with these different formulations. We demonstrate using computational experiments that the choice of formulation may have a significant impact on the resulting bounds. We also provide theoretical justifications for the observed behavior.     

Global Optimization of Nonconvex Polynomial Programming Problems Having Rational Exponents

This paper considers the solution of nonconvex polynomial programming problems that arise in various engineering design, network distribution, and location-allocation contexts. These problems generally have nonconvex polynomial objective functions and constraints, involving terms of mixed-sign coefficients (as in signomial geometric programs) that have rational exponents on variables. For such problems, we develop an extension of the Reformulation-Linearization Technique (RLT) to generate linear programming relaxations that are embedded within a branch-and-bound algorithm. Suitable branching or partitioning strategies are designed for which convergence to a global optimal solution is established. The procedure is illustrated using a numerical example, and several possible extensions and algorithmic enhancements are discussed.     

Improving an Upper Bound on the Stability Number of a Graph

In previous works an upper bound on the stability number of a graph based on quadratic programming was introduced and several of its properties were given. The graphs for which this bound is attained has been known as graphs with convex-QP stability number. This paper proposes a new upper bound on the stability number whose determination is also done by quadratic programming. It is proved that the new bound improves the above mentioned bound and several computational tests asserting its interest for large graphs are presented. In addition a necessary and sufficient condition for a graph to attain the new bound is proved. As a consequence a graph with convex-QP stability number also attains the new bound. On the other hand it is shown the existence of graphs attaining the new bound that do not belong to the class of graphs with convex-QP stability number. This allows to assert that the class of graphs with convex-QP stability number is strictly included in the class of graphs that attain the introduced bound. Some conclusions and lines for future work finalize the paper.     

求广义线性比试和问题全局解的新方法

为确定广义线性比式和规划问题(GFP)的全局最优解,提出一个新的分支定界方法.在算法中,分支过程采用单纯形对分规则,且界的估计通过一些线性规划问题的求解完成.给出算法的收敛性证明.数值试验结果显示算法是有效可行的.     

On the Fractional Intersection Number of a Graph

 An intersection representation of a graph G is a function f:V(G)→2^S (where S is any set) with the property that uv∈E(G) if and only if f(u)∩f(v)≠∅. The size of the representation is |S|. The intersection number of G is the smallest size of an intersection representation of G. The intersection number can be expressed as an integer program, and the value of the linear relaxation of that program gives the fractional intersection number. This is in consonance with fractional versions of other graph invariants such as matching number, chromatic number, edge chromatic number, etc.  We examine cases where the fractional and ordinary intersection numbers are the same (interval and chordal graphs), as well as cases where they are wildly different (complete multipartite graphs). We find the fractional intersection number of almost all graphs by considering random graphs. Received: July 1, 1996 Revised: August 11, 1997     

An Exact Method for Fractional Goal Programming

Goal Programming with fractional objectives can be reduced to mathematical programming with a linear objective under linear and quadratic constraints, thus optimal solutions can be obtained by using existing Global Optimization techniques. However, only heuristic procedures are suggested in the literature on the field. In this note we explore the practical applicability of a recent algorithm for nonconvex quadratic programming with quadratic constraints for this problem. Encouraging computational experiences for randomly generated instances with up to 14 fractional objectives are presented.     

On the Construction of Convex and Concave Envelope Formulas for Bilinear and Fractional Functions on Quadrilaterals

Convex and concave envelopes play important roles in various types of optimization problems. In this article, we present a result that gives general guidelines for constructing convex and concave envelopes of functions of two variables on bounded quadrilaterals. We show how one can use this result to construct convex and concave envelopes of bilinear and fractional functions on rectangles, parallelograms and trapezoids. Applications of these results to global optimization are indicated.     

A Combined Algorithm for Fractional Programming

In this paper, we present an outer approximation algorithm for solving the following problem: max _xS {f(x)/g(x)}, where f(x)0 and g(x)>0 are d.c. (difference of convex) functions over a convex compact subset S of R ⁿ . Let ()=max _xS (f(x)–g(x)), then the problem is equivalent to finding out a solution of the equation ()=0. Though the monotonicity of () is well known, it is very time-consuming to solve the previous equation, because that maximizing (f(x)–g(x)) is very hard due to that maximizing a convex function over a convex set is NP-hard. To avoid such tactics, we give a transformation under which both the objective and the feasible region turn to be d.c. After discussing some properties, we propose a global optimization approach to find an optimal solution for the encountered problem.     

Global optimization of fractional programs

Dinkelbach's global optimization approach for finding the global maximum of the fractional programming problem is discussed. Based on this idea, a modified algorithm is presented which provides both upper and lower bounds at each iteration. The convergence of the lower and upper bounds to the global maximum function value is shown to be superlinear. In addition, the special case of fractional programming when the ratio involves only linear or quadratic terms is considered. In this case, the algorithm is guaranteed to find the global maximum to within any specified tolerance, regardless of the definiteness of the quadratic form.     

On the Broadcast Independence Number of Grid Graph

A broadcast on a nontrivial connected graph G is a function ${f:V \longrightarrow \{0, \ldots,\operatorname{diam}(G)\}}$ such that for every vertex ${v \in V(G)}$ , ${f(v) \leq e(v)}$ , where ${\operatorname{diam}(G)}$ denotes the diameter of G and e(v) denotes the eccentricity of vertex v. The broadcast independence number is the maximum value of ${\sum_{v \in V} f(v)}$ over all broadcasts f that satisfy ${d(u,v) > \max \{f(u), f(v)\}}$ for every pair of distinct vertices u, v with positive values. We determine this invariant for grid graphs ${G_{m,n} = P_m \square P_n}$ , where ${2 \leq m \leq n}$ and □ denotes the Cartesian product. We hereby answer one of the open problems raised by Dunbar et al. in (Discrete Appl Math 154:59–75, 2006).     

Rainbow Connection Number and Independence Number of a Graph

A path in an edge-colored graph is called rainbow if any two edges of the path have distinct colors. An edge-colored graph is called rainbow connected if there exists a rainbow path between every two vertices of the graph. For a connected graph G, the minimum number of colors that are needed to make G rainbow connected is called the rainbow connection number of G, denoted by rc(G). In this paper, we investigate the relation between the rainbow connection number and the independence number of a graph. We show that if G is a connected graph without pendant vertices, then \(\mathrm{rc}(G)\le 2\alpha (G)-1\). An example is given showing that the upper bound \(2\alpha (G)-1\) is equal to the diameter of G, and so the upper bound is sharp since the diameter of G is a lower bound of \(\mathrm{rc}(G)\).     

Conflict-free Connection Number and Independence Number of a Graph

An edge-colored graph G is conflict-free connected if any two of its vertices are connected by a path,which contains a color used on exactly one of its edges.The conflict-free connection number of a connected graph G,denoted by cf c(G),is defined as the minimum number of colors that are required in order to make G conflict-free connected.In this paper,we investigate the relation between the conflict-free connection number and the independence number of a graph.We firstly show that cf c(G)≤α(G)for any connected graph G,and give an example to show that the bound is sharp.With this result,we prove that if T is a tree with?(T)≥(α(T)+2)/2,then cf c(T)=?(T).     

An Extension of the Win Theorem: Counting the Number of Maximum Independent Sets

Win proved a well-known result that the graph G of connectivity κ(G) withα(G) ≤κ(G) + k-1(k ≥ 2) has a spanning k-ended tree, i.e., a spanning tree with at most k leaves. In this paper, the authors extended the Win theorem in case when κ(G) = 1 to the following: Let G be a simple connected graph of order large enough such that α(G) ≤ k + 1(k ≥ 3) and such that the number of maximum independent sets of cardinality k + 1 is at most n-2k-2. Then G has a spanning k-ended tree.     

Finding independent sets in a graph using continuous multivariable polynomial formulations

Two continuous formulations of the maximum independent set problem on a graph G=(V,E) are considered. Both cases involve the maximization of an n-variable polynomial over the n-dimensional hypercube, where n is the number of nodes in G. Two (polynomial) objective functions F(x) and H(x) are considered. Given any solution to x₀ in the hypercube, we propose two polynomial-time algorithms based on these formulations, for finding maximal independent sets with cardinality greater than or equal to F(x₀) and H(x₀), respectively. A relation between the two approaches is studied and a more general statement for dominating sets is proved. Results of preliminary computational experiments for some of the DIMACS clique benchmark graphs are presented.     

Global Minimization of a Multivariate Polynomial using Matrix Methods

The problem of minimizing a polynomial function in several variables over R ⁿ is considered and an algorithm is given. When the polynomial has a minimum the algorithm returns the global minimal value and finds at least one point in every connected component of the set of minimizers. A characterization of such points is given. When the polynomial does not have a minimum the algorithm computes its infimum. No assumption is made on the polynomial.     

A Unified Monotonic Approach to Generalized Linear Fractional Programming

We present an efficient unified method for solving a wide class of generalized linear fractional programming problems. This class includes such problems as: optimizing (minimizing or maximizing) a pointwise maximum or pointwise minimum of a finite number of ratios of linear functions, optimizing a sum or product of such ratios, etc. – over a polytope. Our approach is based on the recently developed theory of monotonic optimization.     

具不变集的平面多项式系统

本文证明了以y＝xm为不变集的平面n次多项式系统（m＞n）不会有极限环，但可以存在奇闭轨．