共查询到20条相似文献,搜索用时 15 毫秒
1.
Graph partition is used in the telecommunication industry to subdivide a transmission network into small clusters. We consider
both linear and semidefinite relaxations for the equipartition problem and present numerical results on real data from France
Telecom networks with up 900 nodes, and also on randomly generated problems.
Received: August 8, 2001 / Accepted: November 9, 2001 Published online: December 9, 2002
RID="★★"
ID="★★" This research was carried out while this author was working at France Telecom R & D, 38–40 rue du Général Leclerc,
F-92794 Issy-Les-Moulineaux Cedex 9, France.
RID="★"
ID="★" This author greatfully acknowledges financial support from the Austrian Science Foundation FWF Project P12660-MAT.
Key words. graph partitioning – semidefinite programming 相似文献
2.
Yasuhiro Nakagawa 《Mathematische Annalen》2003,325(1):31-53
The Bando-Calabi-Futaki character of a compact K?hler manifold is an obstruction to the existence of K?hler metrics with
constant scalar curvature, which is a generalization of the Futaki character of a Fano manifold. In this paper, we shall establish
an interpretation of the Bando-Calabi-Futaki character as a secondary characteristic class. By using this interpretation,
we shall also prove that the Bando-Calabi-Futaki character can be lifted to a group character.
Received: 26 October 2000 / Revised version: 25 October 2001 / Published online: 16 October 2002
RID="★"
ID="★" Partly supported by the Grant-in-Aid for Encouragement of Young Scientists (No. 09740047), The Ministry of Education,
Science, Sports and Culture, Japan
Mathematics Subject Classification (2000): 32Q20, 32Q15, 32M05, 57R30 相似文献
3.
We study a special case of a structured mixed integer programming model that arises in production planning. For the most
general case of the model, called PI, we have earlier identified families of facet–defining valid inequalities: (l, S) inequalities (introduced for the uncapacitated lot–sizing problem by Barany, Van Roy, and Wolsey), cover inequalities, and
reverse cover inequalities. PI is 𝒩𝒫–hard; in this paper we focus on a special case, called PIC. We describe a polynomial
algorithm for PIC, and we use this algorithm to derive an extended formulation of polynomial size for PIC. Projecting from
this extended formulation onto the original space of variables, we show that (l, S) inequalities, cover inequalities, and reverse cover inequalities suffice to solve the special case PIC by linear programming.
We also describe fast combinatorial separation algorithms for cover and reverse cover inequalities for PIC. Finally, we discuss
the relationship between our results for PIC and a model studied previously by Goemans.
Received: December 13, 2000 / Accepted: December 13, 2001 Published online: October 9, 2002
RID="★"
ID="★" Some of the results in this paper have appeared in condensed form in Miller et al. (2001).
Key words. mixed integer programming – polyhedral combinatorics – production planning – capacitated lot–sizing – fixed charge network
flow – setup times
This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian
State, Prime Minister's Office, Science Policy Programming. The scientific responsibility is assumed by the authors.
This research was also supported by NSF Grant No. DMI-9700285 and by Philips Electronics North America. 相似文献
4.
Stephen J. Wright 《Mathematical Programming》2003,95(1):137-160
In the vicinity of a solution of a nonlinear programming problem at which both strict complementarity and linear independence
of the active constraints may fail to hold, we describe a technique for distinguishing weakly active from strongly active
constraints. We show that this information can be used to modify the sequential quadratic programming algorithm so that it
exhibits superlinear convergence to the solution under assumptions weaker than those made in previous analyses.
Received: December 18, 2000 / Accepted: January 14, 2002 Published online: September 27, 2002
RID="★"
ID="★" Research supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of
Advanced Scientific Computing Research, U.S. Department of Energy, under Contract W-31-109-Eng-38.
Key words. nonlinear programming problems – degeneracy – active constraint identification – sequential quadratic programming 相似文献
5.
We consider the problem of a travelling merchant who makes money by buying commodities where they are cheap and selling them
in other places where he can make a profit. The merchant ships commodities of his own choice in a van of fixed capacity. Given
the prices of all the commodities in all of the places, and the cost of driving from one place to another, the problem the
merchant faces each day is to select a subset of the cities that he can visit in a day, and to determine the order in which
the cities are visited, such that the total profit is maximised. We call this problem the Merchant Subtour Problem. The MSP models the pricing problem of a rather complex pickup and delivery problem that was given to us by the Dutch logistics
company Van Gend & Loos.
We show that a special case of the MSP has a totally unimodular constraint matrix. This knowledge enables us to develop a
tabu-search algorithm for finding good feasible solutions to the MSP, and a branch-and-price-and-cut algorithm for solving
the MSP to optimality. The relaxations solved in each node of the branch-and-bound tree are strengthened by lifted knapsack
inequalities, lifted cycle inequalities and mod-k cuts. We present computational results on data sets derived from our main instance of the Van Gend & Loos pickup and delivery
problem.
Received: October 25, 2000 / Accepted: January 23, 2002 Published online: September 27, 2002
RID="★"
ID="★" This research was partially supported by EC – Fifth Framework Programme contract IST-1999-14186 (Project ALCOM-FT:
Algorithms and Complexity – Future Technologies). 相似文献
6.
A dynamic knapsack set is a natural generalization of the 0-1 knapsack set with a continuous variable studied recently. For
dynamic knapsack sets a large family of facet-defining inequalities, called dynamic knapsack inequalities, are derived by
fixing variables to one and then lifting. Surprisingly such inequalities have the simultaneous lifting property, and for small
instances provide a significant proportion of all the facet-defining inequalities.
We then consider single-item capacitated lot-sizing problems, and propose the joint study of three related sets. The first
models the discrete lot-sizing problem, the second the continuous lot-sizing problem with Wagner-Whitin costs, and the third
the continuous lot-sizing problem with arbitrary costs. The first set that arises is precisely a dynamic knapsack set, the
second an intersection of dynamic knapsack sets, and the unrestricted problem can be viewed as both a relaxation and a restriction
of the second. It follows that the dynamic knapsack inequalities and their generalizations provide strong valid inequalities
for all three sets.
Some limited computation results are reported as an initial test of the effectiveness of these inequalities on capacitated
lot-sizing problems.
Received: March 28, 2001 / Accepted: November 9, 2001 Published online: September 27, 2002
RID="★"
ID="★" Research carried out with financial support of the project TMR-DONET nr. ERB FMRX–CT98–0202 of the European Union.
Present address: Electrabel, Louvain-la-Neuve, B-1348 Belgium.
Present address: Electrabel, Louvain-la-Neuve, B-1348 Belgium.
Key words. knapsack sets – valid inequalities – simultaneous lifting – lot-sizing – Wagner-Whitin costs 相似文献
7.
The stability number α(G) for a given graph G is the size of a maximum stable set in G. The Lovász theta number provides an upper bound on α(G) and can be computed in polynomial time as the optimal value of the Lovász semidefinite program. In this paper, we show that
restricting the matrix variable in the Lovász semidefinite program to be rank-one and rank-two, respectively, yields a pair
of continuous, nonlinear optimization problems each having the global optimal value α(G). We propose heuristics for obtaining large stable sets in G based on these new formulations and present computational results indicating the effectiveness of the heuristics.
Received: December 13, 2000 / Accepted: September 3, 2002 Published online: December 19, 2002
RID="★"
ID="★" Computational results reported in this paper were obtained on an SGI Origin2000 computer at Rice University acquired
in part with support from NSF Grant DMS-9872009.
Key Words. maximum stable set – maximum clique – minimum vertex cover – semidefinite program – semidefinite relaxation – continuous
optimization heuristics – nonlinear programming
Mathematics Subject Classification (2000): 90C06, 90C27, 90C30 相似文献
8.
In this paper we consider stochastic programming problems where the objective function is given as an expected value of a
convex piecewise linear random function. With an optimal solution of such a problem we associate a condition number which
characterizes well or ill conditioning of the problem. Using theory of Large Deviations we show that the sample size needed
to calculate the optimal solution of such problem with a given probability is approximately proportional to the condition
number.
Received: May 2000 / Accepted: May 2002-07-16 Published online: September 5, 2002
RID="★"
The research of this author was supported, in part, by grant DMS-0073770 from the National Science Foundation
Key Words. stochastic programming – Monte Carlo simulation – large deviations theory – ill-conditioned problems 相似文献
9.
José Niño-Mora 《Mathematical Programming》2002,93(3):361-413
This paper develops a polyhedral approach to the design, analysis, and computation of dynamic allocation indices for scheduling
binary-action (engage/rest) Markovian stochastic projects which can change state when rested (restless bandits (RBs)), based on partial conservation laws (PCLs). This extends previous work by the author [J. Ni?o-Mora (2001): Restless bandits, partial conservation laws and indexability.
Adv. Appl. Probab. 33, 76–98], where PCLs were shown to imply the optimality of index policies with a postulated structure in stochastic scheduling problems, under admissible linear objectives, and they were deployed to obtain simple sufficient conditions for the existence of Whittle's (1988) RB index (indexability), along with an adaptive-greedy index algorithm. The new contributions include: (i) we develop the polyhedral foundation
of the PCL framework, based on the structural and algorithmic properties of a new polytope associated with an accessible set system -extended polymatroid}); (ii) we present new dynamic allocation indices for RBs, motivated by an admission control model,
which extend Whittle's and have a significantly increased scope; (iii) we deploy PCLs to obtain both sufficient conditions
for the existence of the new indices (PCL-indexability), and a new adaptive-greedy index algorithm; (iv) we interpret PCL-indexability as a form of the classic economics law of
diminishing marginal returns, and characterize the index as an optimal marginal cost rate; we further solve a related optimal constrained control problem; (v) we carry out a PCL-indexability analysis of the motivating admission control model, under time-discounted
and long-run average criteria; this gives, under mild conditions, a new index characterization of optimal threshold policies;
and (vi) we apply the latter to present new heuristic index policies for two hard queueing control problems: admission control
and routing to parallel queues; and scheduling a multiclass make-to-stock queue with lost sales, both under state-dependent
holding cost rates and birth-death dynamics.
Received: April 2000 / Accepted: October 2002 Published online: December 9, 2002
RID="★"
ID="★" Work partly supported by the Spanish Ministry of Science and Technology (grant BEC2000-1027), NATO (Collaborative
Linkage Grant PST.CLG.976568), and the Joint Spanish-US (Fulbright) Commission for Scientific and Technical Exchange (project
2000-20132)
Key words. Markov decision process – restless bandits – polyhedral combinatorics – extended polymatroid – adaptive-greedy algorithm
– dynamic allocation index – stochastic scheduling – threshold policy – index policy – Gittins index – Klimov index – Whittle
index – control of queues – admission control – routing – make-to-stock – multiclass queue – finite buffers – conservation
laws – achievable performance
Mathematics Subject Classification (1991): (AMS 2000 Subject Classification): 90B36, 90B22, 90C40, 90C57, 90C08 相似文献
10.
A feasible semismooth asymptotically Newton method for mixed complementarity problems 总被引:2,自引:0,他引:2
Semismooth Newton methods constitute a major research area for solving mixed complementarity problems (MCPs). Early research
on semismooth Newton methods is mainly on infeasible methods. However, some MCPs are not well defined outside the feasible
region or the equivalent unconstrained reformulations of other MCPs contain local minimizers outside the feasible region.
As both these problems could make the corresponding infeasible methods fail, more recent attention is on feasible methods.
In this paper we propose a new feasible semismooth method for MCPs, in which the search direction asymptotically converges
to the Newton direction. The new method overcomes the possible non-convergence of the projected semismooth Newton method,
which is widely used in various numerical implementations, by minimizing a one-dimensional quadratic convex problem prior
to doing (curved) line searches.
As with other semismooth Newton methods, the proposed method only solves one linear system of equations at each iteration.
The sparsity of the Jacobian of the reformulated system can be exploited, often reducing the size of the system that must
be solved. The reason for this is that the projection onto the feasible set increases the likelihood of components of iterates
being active. The global and superlinear/quadratic convergence of the proposed method is proved under mild conditions. Numerical
results are reported on all problems from the MCPLIB collection [8].
Received: December 1999 / Accepted: March 2002 Published online: September 5, 2002
RID="★"
ID="★" This work was supported in part by the Australian Research Council.
Key Words. mixed complementarity problems – semismooth equations – projected Newton method – convergence
AMS subject classifications. 90C33, 90C30, 65H10 相似文献
11.
A class of affine-scaling interior-point methods for bound constrained optimization problems is introduced which are locally
q–superlinear or q–quadratic convergent. It is assumed that the strong second order sufficient optimality conditions at the
solution are satisfied, but strict complementarity is not required. The methods are modifications of the affine-scaling interior-point
Newton methods introduced by T. F. Coleman and Y. Li (Math. Programming, 67, 189–224, 1994). There are two modifications. One is a modification of the scaling matrix, the other one is the use of a
projection of the step to maintain strict feasibility rather than a simple scaling of the step. A comprehensive local convergence
analysis is given. A simple example is presented to illustrate the pitfalls of the original approach by Coleman and Li in
the degenerate case and to demonstrate the performance of the fast converging modifications developed in this paper.
Received October 2, 1998 / Revised version received April 7, 1999?Published online July 19, 1999 相似文献
12.
Many results of classical Potential Theory are extended to sub-Laplacians ▵𝔾 on Carnot groups 𝔾. Some characterizations of ▵𝔾-subharmonicity, representation formulas of Poisson-Jensen's kind and Nevanlinna-type theorems are proved. We also characterize
the Riesz-measure related to bounded-above ▵𝔾-subharmonic functions in ℝ
N
.
Received: 21 June 2000 / Revised version: 12 March 2002 / Published online: 2 December 2002
RID="★"
ID="★" Investigation supported by University of Bologna. Funds for selected research topics.
Mathematics Subject Classification (2000): 31B05, 35J70, 35H20 相似文献
13.
This note investigates the boundary between polynomially-solvable Max Cut and NP Hard Max Cut instances when they are classified
only on the basis of the sign pattern of the objective function coefficients, i.e., of the orthant containing the objective
function vector. It turns out that the matching number of the subgraph induced by the positive edges is the key parameter
that allows us to differentiate between polynomially-solvable and hard instances of the problem. We give some applications
of the polynomially solvable cases.
Received: November 29, 2000 / Accepted: August 17, 2001 Published online: December 9, 2002
RID="★"
ID="★" The research of this author was partially supported by an NSERC Research Grant. 相似文献
14.
We investigate the NP–hard label number maximization problem (LNM): Given a set of rectangular labels Λ, each of which belongs to a point feature
in the plane, the task is to find a labeling for a largest subset Λ
P
of Λ. A labeling is a placement such that none of the labels overlap and each λΛ
P
is placed according to a labeling model: In the discrete models, the label must be placed so that the labeled point coincides with an element of a predefined subset of corners of the rectangular
label, in the continuous or slider models, the point must lie on a subset of boundaries of the label. Obviously, the slider models allow a continuous movement of a
label around its point feature, leading to a significantly higher number of labels that can be placed.
We present exact algorithms for this problem that are based on a pair of so-called constraint graphs that code horizontal
and vertical positioning relations. The key idea is to link the two graphs by a set of additional constraints, thus characterizing
all feasible solutions of LNM. This enables us to formulate a zero-one integer linear program whose solution leads to an optimal
labeling.
We can express LNM in both the discrete and the slider labeling models. To our knowledge, we present the first algorithm that
computes provably optimal solutions in the slider models. We find it remarkable that our approach is independent of the labeling
model and results in a discrete algorithm even if the problem is of continuous nature as in the slider models. Extensive experimental
results on both real-world instances and point sets created by a widely used benchmark generator show that the new approach
- although being an exponential time algorithm - is applicable in practice.
Received: November 20, 2000 / Accepted: April 9, 2002 Published online: September 5, 2002
RID="★"
ID="★" This work is partially supported by the German Bundesministerium für Bildung, Wissenschaft, Forschung und Technologie
(No. 03-MU7MP1-4).
Key words. map labeling – point feature map labeling – constraint graphs – combinatorial optimization – integer programming 相似文献
15.
V. P. Il'in 《Journal of Mathematical Sciences》1996,78(2):142-180
An anisotropic Sobolev and Nikol'skii-Besov space on a domain G is determined by its integro-differential (shortly, ID) parameters.
On the other hand, the geometry of G is characterized by the set Λ(G) of all vectors λ=(λ1,..., λn) such that G satisfies the λ-horn condition. We study the dependence of the totality of possible embeddings upon the set
Λ(G) and theID-parameters of the space. We consider only embeddings with q≥pi, where pi are the integral parameters of the space and q is the integral embedding parameter. For a given space, we introduce its initial
matrix A0 determined by theID-parameters. A0 turns out to be a Z-matrix. On the basis of a natural classification of Z-matrices, a classification of anisotropic spaces
is introduced. This classification allows one to restate the existence of an embedding with q≥pi in terms of certain specific properties of A0. Let A0 be a nondegenerate M-matrix. Any vector λ∈Λ(G) gives rise to a certain set of admissible values of the embedding parameters.
We call λ optimal if this set is the largest possible. It turns out that the optimal vector λ
G
*
is determined by Λ(G) and A0, and may be found by a linear optimization procedure. The following cases are possible: a)
, b)
, c) λ
G
*
does not exist. In case a) the set of admissible values of the embedding parameters is the biggest, while in case c) no embeddings
with q≥pi exist. In case b) the so-called saturation phenomenon occurs, i.e., certain variations of some differential parameters of
the space do not change the set of admissible values of the embedding parameters. The latter fact has some applications to
the problem of extension of all functions belonging to the given space from G to En. Bibliography: 20 titles.
Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 201, 1992, pp. 22–94.
Translated by A. A. Mekler. 相似文献
16.
Marie-Hélène Mourgues 《Archive for Mathematical Logic》2002,41(7):631-642
We extend the notion of absolute convergence for real series in several variables to a notion of convergence for series in
a power series field ℝ((t
Γ)) with coefficients in ℝ. Subsequently, we define a natural notion of analytic function at a point of ℝ((t
Γ))m. Then, given a real function f analytic on a open box I of ℝ
m
, we extend f to a function f
★ which is analytic on a subset of ℝ((t
Γ))
m
containing I. We prove that the functions f
★ share with real analytic functions certain basic properties: they are , they have usual Taylor development, they satisfy the inverse function theorem and the implicit function theorem.
Received: 5 October 2000 / Revised version: 19 June 2001 / Published online: 12 July 2002 相似文献
17.
With “hat” denoting the Banach envelope (of a quasi-Banach space) we prove that
if 0<p<1, 0<q<1, ℝ, while
if 0<p<1, 1≤q<+∞, ∝, and
if 1≤p<+∞, 0<q<1, ℝ.
Applications to questions regarding the global interior regularity of solutions to Poisson type problems for the three-dimensional
Lamé system in Lipschitz domains are presented. 相似文献
18.
Non-Interior continuation methods for solving semidefinite complementarity problems 总被引:13,自引:0,他引:13
There recently has been much interest in non-interior continuation/smoothing methods for solving linear/nonlinear complementarity
problems. We describe extensions of such methods to complementarity problems defined over the cone of block-diagonal symmetric
positive semidefinite real matrices. These extensions involve the Chen-Mangasarian class of smoothing functions and the smoothed
Fischer-Burmeister function. Issues such as existence of Newton directions, boundedness of iterates, global convergence, and
local superlinear convergence will be studied. Preliminary numerical experience on semidefinite linear programs is also reported.
Received: October 1999 / Accepted: April 2002 Published online: December 19, 2002
RID="⋆"
ID="⋆" This research is supported by National Science Foundation Grant CCR-9731273.
Key words. semidefinite complementarity problem – smoothing function – non-interior continuation – global convergence – local superlinear
convergence 相似文献
19.
V. N. Kublanovskaya 《Journal of Mathematical Sciences》2000,101(4):3300-3314
This paper considers the solution of a system of m nonlinear equations in q>02 variables (SNAE-q). A method for finding all
of the finite zero-dimensional roots of a given SNAE-q, which extends the method suggested previously for q=2 and q=3 to the
case q≥2, is developed and theoretically justified. This method is based on the algorithm of the ΔW-q factorization of a polynomial
q-parameter matrix and on the algorithm of relative factorization of a scalar polynomial in q variables. Bibliography: 7 titles.
Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 248, 1998, pp. 124–146.
Translated by V. N. Kublanovskaya. 相似文献
20.
We discuss convex optimization problems in which some of the variables are constrained to be finite autocorrelation sequences.
Problems of this form arise in signal processing and communications, and we describe applications in filter design and system
identification. Autocorrelation constraints in optimization problems are often approximated by sampling the corresponding
power spectral density, which results in a set of linear inequalities. They can also be cast as linear matrix inequalities
via the Kalman-Yakubovich-Popov lemma. The linear matrix inequality formulation is exact, and results in convex optimization
problems that can be solved using interior-point methods for semidefinite programming. However, it has an important drawback:
to represent an autocorrelation sequence of length $n$, it requires the introduction of a large number ($n(n+1)/2$) of auxiliary
variables. This results in a high computational cost when general-purpose semidefinite programming solvers are used. We present
a more efficient implementation based on duality and on interior-point methods for convex problems with generalized linear
inequalities.
Received: August 20, 2001 / Accepted: July 16, 2002 Published online: September 27, 2002
RID="★"
ID="★" This material is based upon work supported by the National Science Foundation under Grant No. ECS-9733450. 相似文献