Search

In this paper, we concentrate on generating cutting planes for the unsplittable capacitated network design problem. We use the unsplittable flow arc-set polyhedron of the considered problem as a substructure and generate cutting planes by solving the separation problem over it. To relieve the computational burden, we show that, in some special cases, a closed form of the separation problem can be derived. For the general case, a brute-force algorithm, called exact separation algorithm, is employed in solving the separation problem of the considered polyhedron such that the constructed inequality guarantees to be facet-defining. Furthermore, a new technique is presented to accelerate the exact separation algorithm, which significantly decreases the number of iterations in the algorithm. Finally, a comprehensive computational study on the unsplittable capacitated network design problem is presented to demonstrate the effectiveness of the proposed algorithm., 35 pages, 1 figure, accepted for publication in Journal of Global Optimization

The maximum separation problem is to find the maximum of the minimum pairwise distance of n points in a planar body $${\mathcal {B}}$$ on the Euclidean plane. In this paper this problem will be considered if $${\mathcal {B}}$$ is the equilateral triangle of side length 1 and the number of points is 13. We will present the exact separation distance of 13 points in the equilateral triangle of side length 1 and we will prove a conjecture of Melissen from 1993 and a conjecture of Graham and Lubachevsky from 1995.

We study the following separation problem: Given a collection of pairwise disjoint coloured objects in the plane withkdifferent colours, compute a shortest “fence”F, i.e., a union of curves of minimum total length, that separates every pair of objects of different colours. Two objects are separated ifFcontains a simple closed curve that has one object in the interior and the other in the exterior. We refer to the problem asgeometrick-cut, as it is a geometric analog to the well-studied multicut problem on graphs. We first give an$$O(n^4\log ^3\!n)$$O(n4log3n)-time algorithm that computes an optimal fence for the case where the input consists of polygons of two colours withncorners in total. We then show that the problem is NP-hard for the case of three colours. Finally, we give a randomised$$4/3\cdot 1.2965$$4/3·1.2965-approximation algorithm for polygons and any number of colours.

The main purpose of this paper is to study certain lattice-valued maps through associated functional equations and inequalities. We deal with morphisms between an algebraic structure and an ordered structure. Next, we solve a separation problem for the inequalities studied. Moreover, we discuss the Hyers-Ulam stability of our main equation. Our research is motivated by the notion of optimal average, which was introduced by the first author in 1994.

International audience; We study the problem of orienting the edges of a graph such that the minimum over all the vertices of the absolute difference between the outdegree and the indegree of a vertex is maximized. We call this minimum the imbalance of the orientation, i.e. the higher it gets, the more imbalanced the orientation is. The studied problem is denoted by MAXIM. We first characterize graphs for which the optimal objective value of MAXIM is zero. Next we show that MAXIM is generally NP-hard and cannot be approximated within a ratio of 1 2 + ε for any constant ε > 0 in polynomial time unless P = NP even if the minimum degree of the graph δ equals 2. Then we describe a polynomial-time approximation algorithm whose ratio is almost equal to 1 2. An exact polynomial-time algorithm is also derived for cacti. Finally, two mixed integer linear programming formulations are presented. Several valid inequalities are exhibited with the related separation algorithms. The performance of the strengthened formulations is assessed through several numerical experiments.

Consider the bi-harmonic differential expression of the form $ A=\triangle _{M}^{2}+q\ $ on a manifold of bounded geometry (M,g) with metric g, where △M is the scalar Laplacian on M and q≥0 is a locally integrable function on M. In the terminology of Everitt and Giertz, the differential expression A is said to be separated in Lp(M), if for all u∈Lp(M) such that Au∈Lp(M), we have qu∈Lp(M). In this paper, we give sufficient conditions for A to be separated in Lp(M),where 1

The separation problem of two sets, whose convex hulls have a nonempty intersection, is considered. In order to find a solution of the problem algorithms of local and global search are developed. The efficiency of the algorithms is demonstrated by computational simulations on test examples.

This paper introduces the anytime anywhere document analysis methodology applied in the context of computer-aided transcription. Its utility is revealed for documents which are difficult to analyse, as in the case of handwritten texts. A special focus lies on the glyph separation problem which turns out to be particularly complicated. As automatic methods show fundamental limitations, a number of interactive methods are proposed which are based on the interplay between user and machine. These methods get along without any assumptions concerning underlying languages or appearances of texts. An evaluation in the context of palaeography and applied to a well-established data set illustrates how well handwritings are dealt with, although they offer distinct differences in their regularity and shape.

Diatom valves and girdle bands are useful micro–nano materials in nanotechnology and micro manufacturing. A settling method is used to extract high-purity diatom valves and girdle bands from Coscinodiscus diatomite. The average models of diatom valves and girdle bands are established. Stokes Law and hydrokinetic theories are used to analyze the settling velocity of valves and girdle bands. Based on the calculation results, settling experiments are carried out, by which clean diatom valves with purity of 80% and girdle bands with purity of 90% are obtained. This method can be applied to other particles separation problem to separate micro-particles with similar radius but different sectional area.

The master equality polyhedron (MEP) is a canonical set that generalizes the master cyclic group polyhedron (MCGP) of Gomory. We recently characterized a nontrivial polar for the MEP, i.e., a polyhedron T such that an inequality defines a nontrivial facet of the MEP if and only if its coefficient vector forms a vertex of T. In this paper, we study the MEP when it is defined by m > 1 rows. We define the notion of a polaroid, a set containing all nontrivial facet defining inequalities. We show how to use linear programming (LP) to efficiently solve the separation problem for the MEP when the polaroid has a compact polyhedral description. We obtain such descriptions via subadditivity conditions when m = 2 or m = 3 and, using LP duality, show how to efficiently optimize over the MEP. These results yield a pseudo-polynomial time LP-based algorithm to solve the problem min$${\{cx : Ax = b, x \geq {\bf 0}, x \in \mathbb{Z}^n\}}$$ when A has at most three constraints. For the MCGP and the MEP defined by a single constraint, the notions of two-term subadditivity and valid inequalities for MEP are essentially equivalent. We show this is not true in the case of the MEP when m ≥ 3; In fact, we prove that subadditivity conditions with a sub-exponential number of terms do not imply validity. In particular, when m = 3, we show that four-term subadditivity conditions are necessary and sufficient for validity.

In this paper, we address the problem of blind extraction and separation of a continuous chaotic signal from a linear mixture consisting of some chaotic signal and/or random signals. The problem of blind extraction is firstly formulated as a problem of the synchronization-based parameter estimation. Then an efficient least square based parameter estimation method is introduced to determine the desired extracting vector. The proposed blind signal extraction scheme is applicable to blind separation of chaotic signals by formulating the separation problem as the extraction of each chaotic source. Numerical simulation shows that the proposed approach can blindly extract and separate the desired chaotic signals and it is also robust to measurement noise.

The obnoxious p-median (OpM) problem is the repulsive counterpart of the ore known attractive p-median problem. Given a set I of cities and a set J of possible locations for obnoxious plants, a p-cardinality subset Q of J is sought, such that the sum of the distances between each city of I and the nearest obnoxious site in Q is maximised. We formulate (OpM) as a {0,1} linear programming problem and propose three families of valid inequalities whose separation problem is polynomial. We describe a branch-and-cut approach based on these inequalities and apply it to a set of instances found in the location literature. The computational results presented show the effectiveness of these inequalities for (OpM).

The analysis of application of two dynamical models (``Earth–Moon'' and``barycentre'' model) in the motion of Near Earth Asteroids was performed. Mainaim was the quantitative estimation of the influence of lunar perturbations on the motionof NEA. Additionally, basic tests of application of numerical methods weremade (RMVS3 and B–S methods). The orbits of 1083 Apollo–Aten–Amor and 7selected AAA objects were adopted as test particles in numerical integrationof the motion. The comparison between results obtained by both dynamicalmodels is discussed in detail. In specific cases, the application of the``Earth–Moon'' dynamical model is very important and cannot be neglected incomputations of orbits.

The problem of separating two semialgebraic sets in an algebraic R-variety is proved to be decidable in dimension 2 with geometric and topologic means. An interpretation of the equivalence between the known criteria of separation is also given.

The selection, testing, and commercial utilization of flotation reagents is best carried out in stages through microflotation tests on pure minerals and their synthetic mixtures followed by bench-scale batch flotation tests on the ore. A systematic approach to quantitatively evaluate different reagents, in particular, through the analysis of batch flotation data, has been presented in this paper. It is recommended that the reagents are compared both in terms of their performance with respect to the recovery-time as well as the recovery-grade plots. While the former describes the kinetic aspects of reagent interaction, the latter is a measure of its selectivity for a particular separation problem.

The author proves the following theorem: Let A0 be a closed 1-dimensional semianalytic germ at the origin 0∈Rn. Let Z be a semianalytic set in Rn whose germ Z0 at 0 is closed and A0∩Z0={0}. Then there exists a polynomial h∈R[x1,⋯,xn] such that h∣Z∖{0}>0 and h∣A0∖{0}

Four chromatographic support materials from the production of GDR firms, one polytetrafluoroethylene support from USSR, polytrifluorochlorethylene and Hyflo-Super-Cel were investigated for suitability under conditions of separation of uranium from other constituents of irradiated uranium fuel solutions with tributylphosphate as an extracting agent. Among the supports there is a new material developed in GDR on the basis of polytetrafluoroethylene with some favorable properties. The experimental results are discussed in connection with the problem of comparison criteria for columns with supports differing in chemical nature, particle size and other parameters. Reduced plate height and velocity were used to arrange experiments under comparable conditions. The results indicate the fluorocontaining supports to be the most suitable ones from the investigated materials for the considered separation problem.

A half-empirical expression is given for the dependence of HETP vs. specific load for preparative GLC columns. On the basis of this expression and the equation for the required number of theoretical plates derived earlier by the same authors, equations are derived which permit to calculate the maximum allowed specific load for a given separation problem.

The paper is dealing with the separation problem of weak intensity anomalies from the perturbation background. By means of the Shannon's form and based on the values estabilished for a measured gravitational field, Δg, the mean quantity of information sent forth at the source — perturbating body — is calculated in order to intercept the Δg set. This quantity takes a maximum value above the perturbating body, while for the remainder a deadening of the perturbations is obtained.