共查询到20条相似文献,搜索用时 703 毫秒
1.
Satoru Fujishige 《Mathematical Programming》2000,88(1):217-220
U. Faigle and W. Kern have recently extended the work of their earlier paper and of M. Queyranne, F. Spieksma and F. Tardella
and have shown that a dual greedy algorithm works for a system of linear inequalities with {:0,1}-coefficients defined in
terms of antichains of an underlying poset and a submodular function on the set of ideals of the poset under some additional
condition on the submodular function.?In this note we show that Faigle and Kern’s dual greedy polyhedra belong to a class
of submodular flow polyhedra, i.e., Faigle and Kern’s problem is a special case of the submodular flow problem that can easily
be solved by their greedy algorithm.
Received: February 1999 / Accepted: December 1999?Published online February 23, 2000 相似文献
2.
The concepts of L-convex function and M-convex function have recently been introduced by Murota as generalizations of submodular
function and base polyhedron, respectively, and discrete separation theorems are established for L-convex/concave functions
and for M-convex/concave functions as generalizations of Frank’s discrete separation theorem for submodular/supermodular set
functions and Edmonds’ matroid intersection theorem. This paper shows the equivalence between Murota’s L-convex functions
and Favati and Tardella’s submodular integrally convex functions, and also gives alternative proofs of the separation theorems
that provide a geometric insight by relating them to the ordinary separation theorem in convex analysis.
Received: November 27, 1997 / Accepted: December 16, 1999?Published online May 12, 2000 相似文献
3.
Submodular flow problems, introduced by Edmonds and Giles [2], generalize network flow problems. Many algorithms for solving
network flow problems have been generalized to submodular flow problems (cf. references in Fujishige [4]), e.g. the cycle
canceling method of Klein [9]. For network flow problems, the choice of minimum-mean cycles in Goldberg and Tarjan [6], and
the choice of minimum-ratio cycles in Wallacher [12] lead to polynomial cycle canceling methods. For submodular flow problems,
Cui and Fujishige [1] show finiteness for the minimum-mean cycle method while Zimmermann [16] develops a pseudo-polynomial
minimum ratio cycle method. Here, we prove pseudo-polynomiality of a larger class of the minimum-ratio variants and, by combining
both methods, we develop a polynomial cycle canceling algorithm for submodular flow problems.
Received July 22, 1994 / Revised version received July 18, 1997? Published online May 28, 1999 相似文献
4.
We describe an O(n
4
hmin{logU,n
2logn}) capacity scaling algorithm for the minimum cost submodular flow problem. Our algorithm modifies and extends the Edmonds–Karp
capacity scaling algorithm for minimum cost flow to solve the minimum cost submodular flow problem. The modification entails
scaling a relaxation parameter δ. Capacities are relaxed by attaching a complete directed graph with uniform arc capacity
δ in each scaling phase. We then modify a feasible submodular flow by relaxing the submodular constraints, so that complementary
slackness is satisfied. This creates discrepancies between the boundary of the flow and the base polyhedron of a relaxed submodular
function. To reduce these discrepancies, we use a variant of the successive shortest path algorithm that augments flow along
minimum cost paths of residual capacity at least δ. The shortest augmenting path subroutine we use is a variant of Dijkstra’s
algorithm modified to handle exchange capacity arcs efficiently. The result is a weakly polynomial time algorithm whose running
time is better than any existing submodular flow algorithm when U is small and C is big. We also show how to use maximum mean cuts to make the algorithm strongly polynomial. The resulting algorithm is the
first capacity scaling algorithm to match the current best strongly polynomial bound for submodular flow.
Received: August 6, 1999 / Accepted: July 2001?Published online October 2, 2001 相似文献
5.
We show a descent method for submodular function minimization based on an oracle for membership in base polyhedra. We assume
that for any submodular function f: ?→R on a distributive lattice ?⊆2
V
with ?,V∈? and f(?)=0 and for any vector x∈R
V
where V is a finite nonempty set, the membership oracle answers whether x belongs to the base polyhedron associated with f and that if the answer is NO, it also gives us a set Z∈? such that x(Z)>f(Z). Given a submodular function f, by invoking the membership oracle O(|V|2) times, the descent method finds a sequence of subsets Z
1,Z
2,···,Z
k
of V such that f(Z
1)>f(Z
2)>···>f(Z
k
)=min{f(Y) | Y∈?}, where k is O(|V|2). The method furnishes an alternative framework for submodular function minimization if combined with possible efficient
membership algorithms.
Received: September 9, 2001 / Accepted: October 15, 2001?Published online December 6, 2001 相似文献
6.
Christian Prins 《Mathematical Methods of Operations Research》2000,52(3):389-411
For more than two machines, and when preemption is forbidden, the computation of minimum makespan schedules for the open-shop
problem is NP-hard. Compared to the flow-shop and the job-shop, the open-shop has free job routes which lead to a much larger
solution space, to smaller gaps between the optimal makespan and the lower bounds, and to disappointing results for the algorithms
based on the disjunctive graph model. For instance, the best existing branch and bound method cannot solve some 7 ×7 hard
instances to optimality, and all published metaheuristics (working by reversing some disjunctions already fixed) do not better
than some greedy or steepest-descent heuristics which need a much smaller computational effort. In this context, the intrinsic
parallelism of genetic algorithms (GAs) seems well adapted, for detecting global optima disseminated among many quasi-optimal
schedules. This paper presents several GAs for the open-shop problem. It is shown that even simple and fast versions can compete
with the best known heuristics and metaheuristics, thanks to two key-features: a population in which each individual has a distinct makespan, and a special procedure which reorders every new chromosome. Using problem-specific heuristics, it is possible to design more powerful GAs which give excellent results, even on the
hardest benchmarks of the literature: for instance, all hard open instances from Taillard are broken, except one for which
the best known solution is improved. 相似文献
7.
The core of a game v on N, which is the set of additive games φ dominating v such that φ(N)=v(N), is a central notion in cooperative game theory, decision making and in combinatorics, where it is related to submodular functions, matroids and the greedy algorithm. In many cases however, the core is empty, and alternative solutions have to be found. We define the k-additive core by replacing additive games by k-additive games in the definition of the core, where k-additive games are those games whose Möbius transform vanishes for subsets of more than k elements. For a sufficiently high value of k, the k-additive core is nonempty, and is a convex closed polyhedron. Our aim is to establish results similar to the classical results of Shapley and Ichiishi on the core of convex games (corresponds to Edmonds’ theorem for the greedy algorithm), which characterize the vertices of the core. 相似文献
8.
A greedy algorithm solves the problem of maximizing a linear objective function over the polyhedron (called the submodular polyhedron) determined by a submodular function on a distributive lattice or a ring family. We generalize the problem by considering a submodular function on a co-intersecting family and give an algorithm for solving it. Here, simple-minded greedy augmentations do not work any more and some complicated augmentations with multiple exchanges are required. We can find an optimal solution by at most 1/2n(n – 1) augmentations, wheren is the number of the variables and we assume a certain oracle for computing multiple exchange capacities. 相似文献
9.
For an edge-weighted graph G with n vertices and m edges, we present a new deterministic algorithm for computing a minimum k-way cut for k=3,4. The algorithm runs in O(n
k-1
F(n,m))=O(mn
k
log(n
2
/m)) time and O(n
2) space for k=3,4, where F(n,m) denotes the time bound required to solve the maximum flow problem in G. The bound for k=3 matches the current best deterministic bound ?(mn
3) for weighted graphs, but improves the bound ?(mn
3) to O(n
2
F(n,m))=O(min{mn
8/3,m
3/2
n
2}) for unweighted graphs. The bound ?(mn
4) for k=4 improves the previous best randomized bound ?(n
6) (for m=o(n
2)). The algorithm is then generalized to the problem of finding a minimum 3-way cut in a symmetric submodular system.
Received: April 1999 / Accepted: February 2000?Published online August 18, 2000 相似文献
10.
Xiaotie Deng Toshihide Ibaraki Hiroshi Nagamochi Wenan Zang 《Mathematical Programming》2000,87(3):441-452
Combinatorial optimization games deal with cooperative games for which the value of every subset of players is obtained by
solving a combinatorial optimization problem on the resources collectively owned by this subset. A solution of the game is
in the core if no subset of players is able to gain advantage by breaking away from this collective decision of all players.
The game is totally balanced if and only if the core is non-empty for every induced subgame of it.?We study the total balancedness
of several combinatorial optimization games in this paper. For a class of the partition game [5], we have a complete characterization
for the total balancedness. For the packing and covering games [3], we completely clarify the relationship between the related
primal/dual linear programs for the corresponding games to be totally balanced. Our work opens up the question of fully characterizing
the combinatorial structures of totally balanced packing and covering games, for which we present some interesting examples:
the totally balanced matching, vertex cover, and minimum coloring games.
Received: November 5, 1998 / Accepted: September 8, 1999?Published online February 23, 2000 相似文献
11.
A stochastic programming model using an endogenously determined worst case risk measure for dynamic asset allocation 总被引:2,自引:0,他引:2
We present a new approach to asset allocation with transaction costs. A multiperiod stochastic linear programming model is
developed where the risk is based on the worst case payoff that is endogenously determined by the model that balances expected
return and risk. Utilizing portfolio protection and dynamic hedging, an investment portfolio similar to an option-like payoff
structure on the initial investment portfolio is characterized. The relative changes in the expected terminal wealth, worst
case payoff, and risk aversion, are studied theoretically and illustrated using a numerical example. This model dominates
a static mean-variance model when the optimal portfolios are evaluated by the Sharpe ratio.
Received: August 15, 1999 / Accepted: October 1, 2000?Published online December 15, 2000 相似文献
12.
Consider the problem of routing the electrical connections among two large terminal sets in circuit layout. A realistic model
for this problem is given by the vertex-disjoint packing of two Steiner trees (2VPST), which is known to be NP-complete. This
work presents an investigation on the 2VPST polyhedra. The main idea is to start from facet-defining inequalities for a vertex-weighted
Steiner tree polyhedra. Some of these inequalities are proven to also define facets for the packing polyhedra, while others
are lifted to derive new important families of inequalities, including proven facets. Separation algorithms are provided.
Branch-and-cut implementation issues are also discussed, including some new practical techniques to improve the performance
of the algorithm. The resulting code is capable of solving problems on grid graphs with up to 10000 vertices and 5000 terminals
in a few minutes.
Received: August 1999 / Accepted: January 2001?Published online April 12, 2001 相似文献
13.
Song Xu 《Mathematical Programming》2000,87(3):501-517
We propose an infeasible non-interior path-following method for nonlinear complementarity problems with uniform P-functions. This method is based on the smoothing techniques introduced by Kanzow. A key to our analysis is the introduction
of a new notion of neighborhood for the central path which is suitable for infeasible non-interior path-following methods.
By restricting the iterates in the neighborhood of the central path, we provide a systematic procedure to update the smoothing
parameter and establish the global linear convergence of this method. Some preliminary computational results are reported.
Received: March 13, 1997 / Accepted: December 17, 1999?Published online February 23, 2000 相似文献
14.
An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints 总被引:12,自引:0,他引:12
Le Thi Hoai An 《Mathematical Programming》2000,87(3):401-426
In this paper we investigate two approaches to minimizing a quadratic form subject to the intersection of finitely many ellipsoids.
The first approach is the d.c. (difference of convex functions) optimization algorithm (abbr. DCA) whose main tools are the
proximal point algorithm and/or the projection subgradient method in convex minimization. The second is a branch-and-bound
scheme using Lagrangian duality for bounding and ellipsoidal bisection in branching. The DCA was first introduced by Pham
Dinh in 1986 for a general d.c. program and later developed by our various work is a local method but, from a good starting
point, it provides often a global solution. This motivates us to combine the DCA and our branch and bound algorithm in order
to obtain a good initial point for the DCA and to prove the globality of the DCA. In both approaches we attempt to use the
ellipsoidal constrained quadratic programs as the main subproblems. The idea is based upon the fact that these programs can
be efficiently solved by some available (polynomial and nonpolynomial time) algorithms, among them the DCA with restarting
procedure recently proposed by Pham Dinh and Le Thi has been shown to be the most robust and fast for large-scale problems.
Several numerical experiments with dimension up to 200 are given which show the effectiveness and the robustness of the DCA
and the combined DCA-branch-and-bound algorithm.
Received: April 22, 1999 / Accepted: November 30, 1999?Published online February 23, 2000 相似文献
15.
Libero Verardi 《Annali di Matematica Pura ed Applicata》2002,180(4):413-428
A suitable equivalence relation is introduced on the set of square matrices with entries of any kind. This allows us to associate
to every equivalence class an infinite family of graphs and determine their topological properties. When a given square matrix
is the multiplication table of a finite groupoid, some connections between algebraic properties of the groupoid and topological
properties of these graphs are proved.
Received: May 4, 1999 Published online: December 19, 2001 相似文献
16.
Nonlinear programming without a penalty function 总被引:57,自引:0,他引:57
In this paper the solution of nonlinear programming problems by a Sequential Quadratic Programming (SQP) trust-region algorithm
is considered. The aim of the present work is to promote global convergence without the need to use a penalty function. Instead,
a new concept of a “filter” is introduced which allows a step to be accepted if it reduces either the objective function or
the constraint violation function. Numerical tests on a wide range of test problems are very encouraging and the new algorithm
compares favourably with LANCELOT and an implementation of Sl1QP.
Received: October 17, 1997 / Accepted: August 17, 2000?Published online September 3, 2001 相似文献
17.
An algebraic model generalizing submodular polytopes is presented, where modular functions on partially ordered sets take over the role of vectors in R
n
. This model unifies various generalizations of combinatorial models in which the greedy algorithm and the Monge algorithm are successful and generalizations of the notions of core and Weber set in cooperative game theory.As a further application, we show that an earlier model of ours as well as the algorithmic model of Queyranne, Spieksma and Tardella for the Monge algorithm can be treated within the framework of usual matroid theory (on unordered ground-sets), which permits also the efficient algorithmic solution of the intersection problem within this model. 相似文献
18.
In a recent paper, the authors have proved results characterizing convexity-preserving maps defined on a subset of a not-necessarily
finite dimensional real vector space as projective maps. The purpose of this note is three-fold. First, we state a theorem
characterizing continuous, injective, convexity-preserving maps from a relatively open, connected subset of an affine subspace
of ℝ
m
into ℝ
n
as projective maps. This result follows from the more general results stated and proved in a coordinate-free manner in the
above paper, and is intended to be more accessible to researchers interested in optimization algorithms. Second, based on
that characterization theorem, we offer a characterization theorem for collinear scalings first introduced by Davidon in 1977
for deriving certain algorithms for nonlinear optimization, and a characterization theorem for projective transformations
used by Karmarkar in 1984 in his linear programming algorithm. These latter two theorems indicate that Davidon’s collinear
scalings and Karmarkar’s projective transformations are the only continuous, injective, convexity-preserving maps possessing
certain features that Davidon and Karmarkar respectively desired in the derivation of their algorithms. The proofs of these
latter two theorems utilize our characterization of continuous, injective, convexity-preserving maps in a way that has implications
to the choice of scalings and transformations in the derivation of optimization algorithms in general. The third purpose of
this note is to point this out.
Received: January 2000 / Accepted: November 2000?Published online January 17, 2001 相似文献
19.
Boolean deductive systems of BL-algebras 总被引:6,自引:0,他引:6
Esko Turunen 《Archive for Mathematical Logic》2001,40(6):467-473
BL-algebras rise as Lindenbaum algebras from many valued logic introduced by Hájek [2]. In this paper Boolean ds and implicative ds of BL-algebras are defined and studied. The following is proved to be equivalent: (i) a ds
D is implicative, (ii) D is Boolean, (iii) L/D is a Boolean algebra. Moreover, a BL-algebra L contains a proper Boolean ds iff L is bipartite. Local BL-algebras, too, are characterized. These results generalize some theorems presented in [4], [5], [6] for MV-algebras which are BL-algebras fulfiling an additional double negation law x = x
**.
Received: 22 June 1998 /?Published online: 18 May 2001 相似文献
20.
A branch and cut algorithm for nonconvex quadratically constrained quadratic programming 总被引:12,自引:0,他引:12
Charles Audet Pierre Hansen Brigitte Jaumard Gilles Savard 《Mathematical Programming》2000,87(1):131-152
We present a branch and cut algorithm that yields in finite time, a globally ε-optimal solution (with respect to feasibility
and optimality) of the nonconvex quadratically constrained quadratic programming problem. The idea is to estimate all quadratic
terms by successive linearizations within a branching tree using Reformulation-Linearization Techniques (RLT). To do so, four
classes of linearizations (cuts), depending on one to three parameters, are detailed. For each class, we show how to select
the best member with respect to a precise criterion. The cuts introduced at any node of the tree are valid in the whole tree,
and not only within the subtree rooted at that node. In order to enhance the computational speed, the structure created at
any node of the tree is flexible enough to be used at other nodes. Computational results are reported that include standard
test problems taken from the literature. Some of these problems are solved for the first time with a proof of global optimality.
Received December 19, 1997 / Revised version received July 26, 1999?Published online November 9, 1999 相似文献