The search session has expired. Please query the service again.
Perfect graphs constitute a well-studied graph class with a rich
structure, reflected by many characterizations with respect to
different concepts.
Perfect graphs are, for instance, precisely those graphs G
where the stable set polytope STAB(G) coincides
with the fractional stable set polytope QSTAB(G).
For all imperfect graphs G it holds that STAB(G) ⊂ QSTAB(G).
It is, therefore, natural to use the difference between the two polytopes
in order to decide how far an imperfect graph is away...
The purpose of this paper is to demonstrate that, for globally minimize one dimensional nonconvex problems with
both twice differentiable function and constraint, we can propose an efficient
algorithm based on Branch and Bound techniques. The method is first
displayed in the simple case with an interval constraint. The extension is
displayed
afterwards to the general case with an additional nonconvex twice
differentiable constraint. A quadratic bounding function which is better
than the well known...
The purpose of this article is to show the great interest of the use of propagation (or pruning) techniques, inside classical interval Branch-and-Bound algorithms. Therefore, a propagation technique based on the construction of the calculus tree is entirely explained and some properties are presented without the need of any formalism (excepted interval analysis). This approach is then validated on a real example: the optimal design of an electrical rotating machine.
The purpose of this article is to show the great interest of the
use of propagation (or pruning) techniques, inside classical
interval Branch-and-Bound algorithms. Therefore, a propagation
technique based on the construction of the calculus tree is
entirely explained and some properties are presented without the
need of any formalism (excepted interval analysis). This approach
is then validated on a real example: the optimal design of an
electrical rotating machine.
The -principal points of a random variable with finite second moment are those points in minimizing the expected squared distance from to the closest point. Although the determination of principal points involves in general the resolution of a multiextremal optimization problem, existing procedures in the literature provide just a local optimum. In this paper we show that standard Global Optimization techniques can be applied.
The p-principal points of a random variable X with finite
second moment
are those p
points in minimizing the expected squared distance from X to
the closest point.
Although the determination of principal points involves in general the
resolution of a multiextremal optimization problem, existing procedures in
the literature provide just a local optimum. In this paper we show that
standard Global Optimization techniques can be applied.
The Löwner-John ellipse of a full-dimensional bounded convex set is a circumscribed ellipse with the property that if we shrink it by the factor (where is dimension), we obtain an inscribed ellipse. Goffin’s algorithm constructs, in polynomial time, a tight approximation of the Löwner-John ellipse of a polyhedron given by facet description. In this text we adapt the algorithm for zonotopes given by generator descriptions. We show that the adapted version works in time polynomial in the size...
The problem of finding structures with minimum stabbing number has received considerable attention from researchers. Particularly, [10] study the minimum stabbing number of perfect matchings (mspm), spanning trees (msst) and triangulations (mstr) associated to set of points in the plane. The complexity of the mstr remains open whilst the other two are known to be 𝓝𝓟-hard. This paper presents integer programming (ip) formulations for these three problems, that allowed us to...
AMS Subj. Classification: 90C57; 90C10;Rail transportation is very rich in terms of problems that can be modelled and solved using mathematical optimization techniques. The train scheduling problem as the most important part of a rail operating policy has a very significant impact on a rail company profit considering the fact that from the quality of a train timetable depends a flow of three most important resources on rail network: cars, locomotives and crews. The train timetabling problem aims at...
A co-biclique of a simple undirected graph G = (V,E) is the edge-set of two disjoint complete subgraphs of G.
(A co-biclique is the complement of a biclique.)
A subset F ⊆ E is an independent of G if there is a co-biclique B such that F ⊆ B, otherwise F is a dependent of G. This paper describes the minimal dependents of G. (A minimal dependent is a dependent C such that any proper subset of C is an independent.)
It is showed that a minimum-cost dependent set of G can be determined in polynomial...
The recourse to operation research solutions has strongly increased
the performances of scheduling task in the High-Level Synthesis
(called hardware compilation). Scheduling a whole program is not
possible as too many constraints and objectives interact. We decompose
high-level scheduling in three steps. Step 1: Coarse-grain scheduling
tries to exploit parallelism and locality of the whole program (in
particular in loops, possibly imperfectly nested) with a rough view of
the target architecture....
In this paper we analyze a known relaxation for the Sparsest Cut
problem based on positive semidefinite constraints, and we present a
branch and bound algorithm and heuristics based on this relaxation.
The relaxed formulation and the algorithms were tested on small and moderate
sized instances. It leads to values very close to the
optimum solution values. The exact algorithm could obtain solutions
for small and moderate sized instances, and the best heuristics
obtained optimum or near optimum...
In this paper we analyze a known relaxation for the Sparsest Cut
problem based on positive semidefinite constraints, and we present a
branch and bound algorithm and heuristics based on this relaxation.
The relaxed formulation and the algorithms were tested on small and moderate
sized instances. It leads to values very close to the
optimum solution values. The exact algorithm could obtain solutions
for small and moderate sized instances, and the best heuristics
obtained optimum or near optimum...
We consider the multiple ellipses detection problem on the basis of a data points set coming from a number of ellipses in the plane not known in advance, whereby an ellipse is viewed as a Mahalanobis circle with center , radius , and some positive definite matrix . A very efficient method for solving this problem is proposed. The method uses a modification of the -means algorithm for Mahalanobis-circle centers. The initial approximation consists of the set of circles whose centers are determined...
Currently displaying 21 –
40 of
44