共查询到20条相似文献,搜索用时 15 毫秒
1.
Point-to-Multipoint systems are a kind of radio systems supplying wireless access to voice/data communication networks. Such
systems have to be run using a certain frequency spectrum, which typically causes capacity problems. Hence it is, on the one
hand, necessary to reuse frequencies but, on the other hand, no interference must be caused thereby. This leads to a combinatorial
optimization problem, the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems
are NP-hard and it is known that, for these problems, there exist no polynomial time algorithms with a fixed approximation
ratio. Algorithms based on cutting planes have shown to be successful for many other combinatorial optimization problems.
In order to apply such methods, knowledge on the associated polytopes is required. The present paper contributes to this issue,
exploring basic properties of chromatic scheduling polytopes and several classes of facet-defining inequalities.
J. L. Marenco: This work supported by UBACYT Grant X036, CONICET Grant 644/98 and ANPCYT Grant 11-09112.
A. K. Wagler: This work supported by the Deutsche Forschungsgemeinschaft (Gr 883/9–1). 相似文献
2.
3.
《Operations Research Letters》2019,47(5):353-357
The most effective software packages for solving mixed 0–1linear programs use strong valid linear inequalities derived from polyhedral theory. We introduce a new procedure which enables one to take known valid inequalities for the knapsack polytope, and convert them into valid inequalities for the fixed-charge and single-node flow polytopes. The resulting inequalities are very different from the previously known inequalities (such as flow cover and flow pack inequalities), and define facets under certain conditions. 相似文献
4.
5.
Teobaldo Bulhões Artur Pessoa Fábio Protti Eduardo Uchoa 《Operations Research Letters》2018,46(4):389-392
This paper studies two polytopes: the complete set packing and set partitioning polytopes, which are both associated with a binary -row matrix having all possible columns. Cuts of rank 1 for the latter polytope play a central role in recent exact algorithms for many combinatorial problems, such as vehicle routing. We show the precise relation between the two polytopes studied, characterize the multipliers that induce rank 1 clique facets and give several families of multipliers that yield other facets. 相似文献
6.
Shmuel Onn 《Discrete Mathematics》2009,309(9):2934-2936
The convex hull ψn,n of certain (n!)2 tensors was considered recently in connection with graph isomorphism. We consider the convex hull ψn of the n! diagonals among these tensors. We show: 1. The polytope ψn is a face of ψn,n. 2. Deciding if a graph G has a subgraph isomorphic to H reduces to optimization over ψn. 3. Optimization over ψn reduces to optimization over ψn,n. In particular, this implies that the subgraph isomorphism problem reduces to optimization over ψn,n. 相似文献
8.
Néstor E. Aguilera 《Discrete Applied Mathematics》2010,158(12):1343-1356
Building on work by G. Cornuéjols and B. Novick and by L. Trotter, we give different characterizations of contractions of consecutive ones circulant clutters that give back consecutive ones circulant clutters. Based on a recent result by G. Argiroffo and S. Bianchi, we then arrive at characterizations of the vertices of the fractional set covering polyhedron of these clutters. We obtain similar characterizations for the fractional set packing polyhedron using a result by F.B. Shepherd, and relate our findings with similar ones obtained by A. Wagler for the clique relaxation of the stable set polytope of webs. Finally, we show how our results can be used to obtain some old and new results on the corresponding fractional set covering polyhedron using properties of Farey series. Our results do not depend on Lehman’s work or blocker/antiblocker duality, as is traditional in the field. 相似文献
9.
A branch-and-cut algorithm for scheduling of projects with variable-intensity activities 总被引:4,自引:0,他引:4
Tamás Kis 《Mathematical Programming》2005,103(3):515-539
10.
In polyhedral combinatorics one often has to analyze the facial structure of less than full dimensional polyhedra. The presence
of implicit or explicit equations in the linear system defining such a polyhedron leads to technical difficulties when analyzing
its facial structure. It is therefore customary to approach the study of such a polytopeP through the study of one of its (full dimensional) relaxations (monotonizations) known as the submissive and the dominant
ofP. Finding sufficient conditions for an inequality that induces a facet of the submissive or the dominant of a polyhedron to
also induce a facet of the polyhedron itself has been posed in the literature as an important research problem. Our paper
goes a long way towards solving this problem. We address the problem in the framework of a generalized monotonization of a
polyhedronP, g-mon(P), that subsumes both the submissive and the dominant, and give a sufficient condition for an inequality that defines a facet
of g-mon(P) to define a facet ofP. For the important cases of the traveling salesman (TS) polytope in both its symmetric and asymmetric variants, and of the
linear ordering polytope, we give sufficient conditions trivially easy to verify, for a facet of the monotone completion to
define a facet of the original polytope itself.
Research supported by grant DMI-9201340 of the National Science Foundation and contract N00014-89-J-1063 of the Office of
Naval Research.
Research supported by MURST, Italy. 相似文献
11.
Matthias Reitzner 《Advances in Mathematics》2005,191(1):178-208
Choose n random points in , let Pn be their convex hull, and denote by fi(Pn) the number of i-dimensional faces of Pn. A general method for computing the expectation of fi(Pn), i=0,…,d−1, is presented. This generalizes classical results of Efron (in the case i=0) and Rényi and Sulanke (in the case i=d−1) to arbitrary i. For random points chosen in a smooth convex body a limit law for fi(Pn) is proved as n→∞. For random points chosen in a polytope the expectation of fi(Pn) is determined as n→∞. This implies an extremal property for random points chosen in a simplex. 相似文献
12.
Since 1782, when Euler addressed the question of existence of a pair of orthogonal Latin squares (OLS) by stating his famous conjecture, these structures have remained an active area of research. In this paper, we examine the polyhedral aspects of OLS. In particular, we establish the dimension of the OLS polytope, describe all cliques of the underlying intersection graph and categorize them into three classes. Two of these classes are shown to induce facet-defining inequalities of Chvátal rank two. For each such class, we provide a polynomial separation algorithm of the lowest possible complexity. 相似文献
13.
14.
Doklady Mathematics - 相似文献
15.
16.
17.
The Graphical Traveling Salesman Polyhedron (GTSP) has been proposed by Naddef and Rinaldi to be viewed as a relaxation of
the Symmetric Traveling Salesman Polytope (STSP). It has also been employed by Applegate, Bixby, Chvátal, and Cook for solving
the latter to optimality by the branch-and-cut method. There is a close natural connection between the two polyhedra. Until
now, it was not known whether there are facets in TT-form of the GTSP polyhedron which are not facets of the STSP polytope
as well. In this paper we give an affirmative answer to this question for n ≥ 9. We provide a general method for proving the existence of such facets, at the core of which lies the construction of
a continuous curve on a polyhedron. This curve starts in a vertex, walks along edges, and ends in a vertex not adjacent to
the starting vertex. Thus there must have been a third vertex on the way.
相似文献
18.
We disprove the longstanding conjecture that every combinatorial automorphism of the boundary complex of a convex polytope
in euclidean spaceE
d
can be realised by an affine transformation ofE
d
. 相似文献
19.
20.
Pablo E. Coll 《Discrete Applied Mathematics》2006,154(5):770-801
We consider the problem of scheduling a set of tasks related by precedence constraints to a set of processors, so as to minimize their makespan. Each task has to be assigned to a unique processor and no preemption is allowed. A new integer programming formulation of the problem is given and strong valid inequalities are derived. A subset of the inequalities in this formulation has a strong combinatorial structure, which we use to define the polytope of partitions into linear orders. The facial structure of this polytope is investigated and facet defining inequalities are presented which may be helpful to tighten the integer programming formulation of other variants of multiprocessor scheduling problems. Numerical results on real-life problems are presented. 相似文献