共查询到20条相似文献,搜索用时 31 毫秒
1.
Chvátal-Gomory cuts are among the most well-known classes of cutting planes for general integer linear programs (ILPs). In
case the constraint multipliers are either 0 or
, such cuts are known as
-cuts. It has been proven by Caprara and Fischetti (Math. Program. 74:221–235, 1996) that separation of
-cuts is
-hard.
In this paper, we study ways to separate
-cuts effectively in practice. We propose a range of preprocessing rules to reduce the size of the separation problem. The
core of the preprocessing builds a Gaussian elimination-like procedure. To separate the most violated
-cut, we formulate the (reduced) problem as integer linear program. Some simple heuristic separation routines complete the
algorithmic framework.
Computational experiments on benchmark instances show that the combination of preprocessing with exact and/or heuristic separation
is a very vital idea to generate strong generic cutting planes for integer linear programs and to reduce the overall computation
times of state-of-the-art ILP-solvers. 相似文献
2.
Jialu Zhang Guojun Wang Mingdi Hu 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2008,12(6):585-591
This paper introduces the concepts of R
0 valuation, R
0 semantic, countable R
0 category , R
0 fuzzy topological category , etc. It is established in a natural way that the fuzzy topology δ and its cut topology on the set Ω
M
consisting of all R
0 valuations of an R
0 algebra M, and some properties of fuzzy topology δ and its cut topology are investigated carefully. Moreover, the representation theorem
for R
0 algebras by means of fuzzy topology is given, that is to say the category is equivalent to the category . By studying the relation between valuations and filters, the Loomis–Sikorski theorem for R
0 algebras is obtained. As an application, K-compactness of the R
0 logic is discussed. 相似文献
3.
4.
5.
The earliest-pseudo-deadline-first (
) Pfair scheduling algorithm is less expensive than some other known Pfair algorithms, but is not optimal for scheduling recurrent
real-time tasks on more than two processors. In prior work, sufficient per-task weight (i.e., utilization) restrictions were established for ensuring that tasks either do not miss their deadlines or have bounded tardiness
when scheduled under
. Implicit in these restrictions is the assumption that the total system utilization may equal the total available processing
capacity (i.e., the total number of processors). This paper considers an orthogonal issue, namely, determining a sufficient restriction
on the total utilization of a task set for it to be schedulable (i.e., a schedulable utilization bound) under
, assuming that there are no per-task weight restrictions. We prove that a task set with total utilization at most
is correctly scheduled under
on M processors, regardless of how large each task’s weight is. At present, we do not know whether this value represents the worst-case
for
, but we do provide a counterexample that shows that it cannot be improved to exceed 86% of the total processing capacity.
The schedulable utilization bound we derive is expressed in terms of the maximum weight of any task, and hence, if this value
is known, may be used to schedule task sets with total utilization greater than
.
相似文献
UmaMaheswari C. DeviEmail: |
6.
Evgeny Dantsin Vladik Kreinovich Alexander Wolpert Gang Xiang 《Reliable Computing》2006,12(4):273-280
In statistical analysis of measurement results, it is often beneficial to compute the range V of the population variance when we only know the intervals of possible values of the xi. In general, this problem is NP-hard; a polynomialtime algorithm is known for the case when the measurements are sufficiently accurate, i.e., when for all In this paper, we show that we can efficiently compute V under a weaker (and more general) condition . 相似文献
7.
Olaf Beyersdorff 《Theory of Computing Systems》2008,43(2):118-135
Disjoint
-pairs are a well studied complexity-theoretic concept with important applications in cryptography and propositional proof
complexity. In this paper we introduce a natural generalization of the notion of disjoint
-pairs to disjoint k-tuples of
-sets for k≥2. We define subclasses of the class of all disjoint k-tuples of
-sets. These subclasses are associated with a propositional proof system and possess complete tuples which are defined from
the proof system.
In our main result we show that complete disjoint
-pairs exist if and only if complete disjoint k-tuples of
-sets exist for all k≥2. Further, this is equivalent to the existence of a propositional proof system in which the disjointness of all k-tuples is shortly provable. We also show that a strengthening of this conditions characterizes the existence of optimal proof
systems.
An extended abstract of this paper appeared in the proceedings of the conference CSR 2006 (Lecture Notes in Computer Science
3967, 80–91, 2006).
Supported by DFG grant KO 1053/5-1. 相似文献
8.
Xueling Ma Jianming Zhan Yang Xu 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2007,11(11):1079-1087
In this paper, we introduce the notions of interval valued -fuzzy filters and interval valued -fuzzy Boolean (implicative) filters in R
0-algebras and investigate some of their related properties. Some characterization theorems of these generalized fuzzy filters
are derived. In particular, we prove that an interval valued fuzzy set F in R
0-algebras is an interval valued -fuzzy Boolean filter if and only if it is an interval valued -fuzzy implicative filter. 相似文献
9.
On Defining Integers And Proving Arithmetic Circuit Lower Bounds 总被引:1,自引:1,他引:0
Peter Bürgisser 《Computational Complexity》2009,18(1):81-103
10.
Tomasz Jurdziński Friedrich Otto František Mráz Martin Plátek 《Theory of Computing Systems》2008,42(4):488-518
The
-automaton is the weakest form of the nondeterministic version of the restarting automaton that was introduced by Jančar et al. to model the so-called analysis by reduction. Here it is shown that the class ℒ(R) of languages that are accepted by
-automata is incomparable under set inclusion to the class
of Church-Rosser languages and to the class
of growing context-sensitive languages. In fact this already holds for the class
of languages that are accepted by 2-monotone
-automata. In addition, we prove that already the latter class contains
-complete languages, showing that already the 2-monotone
-automaton has a surprisingly large expressive power.
The results of this paper have been announced at DLT 2004 in Auckland, New Zealand.
This work was mainly carried out while T. Jurdziński was visiting the University of Kassel, supported by a grant from the
Deutsche Forschungsgemeinschaft (DFG).
F. Mráz and M. Plátek were partially supported by the Grant Agency of the Czech Republic under Grant-No. 201/04/2102 and by
the program ‘Information Society’ under project 1ET100300517. F. Mráz was also supported by the Grant Agency of Charles University
in Prague under Grant-No. 358/2006/A-INF/MFF. 相似文献
11.
We give an elementary self-contained proof that the minimal Renyi entropy output of arbitrary products of channels
is additive. 相似文献
12.
We present two algorithms that are near optimal with respect to the number of inversions present in the input. One of the
algorithms is a variation of insertion sort, and the other is a variation of merge sort. The number of comparisons performed
by our algorithms, on an input sequence of length n that has I inversions, is at most . Moreover, both algorithms have implementations that run in time . All previously published algorithms require at least comparisons for some c > 1.
M. L. Fredman was supported in part by NSF grant CCR-9732689. 相似文献
13.
In this paper, the method of well-combined semantics and syntax proposed by Pavelka is applied to the research of the propositional
calculus formal system
. The partial constant values are taken as formulas, formulas are fuzzified in two manners of semantics and syntax, and inferring
processes are fuzzified. A sequence of new extensions {
} of the system
is proposed, and the completeness of
is proved. 相似文献
14.
15.
In statistical analysis of measurement results it is often necessary to compute the range of the population variance when we only know the intervals of possible values of the x
i
. While can be computed efficiently, the problem of computing is, in general, NP-hard. In our previous paper “Population Variance under Interval Uncertainty: A New Algorithm” (Reliable Computing
12 (4) (2006), pp. 273–280) we showed that in a practically important case we can use constraints techniques to compute in time O(n · log(n)). In this paper we provide new algorithms that compute (in all cases) and (for the above case) in linear time O(n).
Similar linear-time algorithms are described for computing the range of the entropy when we only know the intervals of possible values of probabilities p
i
.
In general, a statistical characteristic ƒ can be more complex so that even computing ƒ can take much longer than linear time.
For such ƒ, the question is how to compute the range in as few calls to ƒ as possible. We show that for convex symmetric functions ƒ, we can compute in n calls to ƒ. 相似文献
16.
Avram Sidi 《Journal of scientific computing》2007,31(3):391-417
Variable transformations for numerical integration have been used for improving the accuracy of the trapezoidal rule. Specifically,
one first transforms the integral via a variable transformation that maps [0,1] to itself, and then approximates the resulting transformed integral by the trapezoidal rule. In this work, we propose a new class of symmetric and nonsymmetric variable transformations which
we denote , where r and s are positive scalars assigned by the user. A simple representative of this class is . We show that, in case , or but has algebraic (endpoint) singularities at x = 0 and/or x = 1, the trapezoidal rule on the transformed integral produces exceptionally high accuracies for special values of r and s. In particular, when and we employ , the error in the approximation is (i) O(h
r
) for arbitrary r and (ii) O(h
2r
) if r is a positive odd integer at least 3, h being the integration step. We illustrate the use of these transformations and the accompanying theory with numerical examples.
相似文献
17.
18.
Generalized fuzzy bi-ideals of semigroups 总被引:1,自引:0,他引:1
Osman Kazancı Sultan Yamak 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2008,12(11):1119-1124
After the introduction of fuzzy sets by Zadeh, there have been a number of generalizations of this fundamental concept. The
notion of (∈, ∈ ∨q)-fuzzy subgroups introduced by Bhakat is one among them. In this paper, using the relations between fuzzy points and fuzzy
sets, the concept of a fuzzy bi-ideal with thresholds is introduced and some interesting properties are investigated. The
acceptable nontrivial concepts obtained in this manner are the (∈, ∈ ∨q)-fuzzy bi-ideals and -fuzzy bi-ideals, which are extension of the concept of a fuzzy bi-ideal in semigroup. 相似文献
19.
20.
Jiří Močkoř 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2009,13(6):591-596
We investigate interpretations of formulas ψ in a first order fuzzy logic in models which are based on objects of a category SetR(Ω) which consists of Ω-sets, i.e. sets with similarity relations with values in a complete MV-algebra Ω and with morphisms
defined as special fuzzy relations between Ω-sets. The interpretations are then morphisms in a category SetR(Ω) from some Ω-set to the object . We define homomorphisms between models in a category SetR(Ω) and we prove that if is a (special) homomorphism of models in a category SetR(Ω) then there is a relation between interpretations of a formula ψ in models .
Supported by MSM6198898701, grant 201/07/0191 of GAČR and grant 1M0572. 相似文献