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

Purpose To use a deep neural network (DNN) for solving the optimization problem of water/fat separation and to compare supervised and unsupervised training. Methods The current T 2 ∗ -IDEAL algorithm for solving water/fat separation is dependent on initialization. Recently, DNN has been proposed to solve water/fat separation without the need for suitable initialization. However, this approach requires supervised training of DNN using the reference water/fat separation images. Here we propose 2 novel DNN water/fat separation methods: 1) unsupervised training of DNN (UTD) using the physical forward problem as the cost function during training, and 2) no training of DNN using physical cost and backpropagation to directly reconstruct a single dataset. The supervised training of DNN, unsupervised training of DNN, and no training of DNN methods were compared with the reference T 2 ∗ -IDEAL. Results All DNN methods generated consistent water/fat separation results that agreed well with T 2 ∗ -IDEAL under proper initialization. Conclusion The water/fat separation problem can be solved using unsupervised deep neural networks.

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.

Forest algebras are defined for investigating languages of forests [ordered sequences] of unranked trees, where a node may have more than two [ordered] successors. They consist of two monoids, the horizontal and the vertical, with an action of the vertical monoid on the horizontal monoid, and a complementary axiom of faithfulness. A pseudovariety is a class of finite algebras of a given signature, closed under the taking of homomorphic images, subalgebras and finitary direct products. By looking at the syntactic congruence for monoids and as the natural extension in the case of forest algebras, we could define a version of syntactic congruence of a subset of the free forest algebra, not just a forest language. Let [Formula: see text] be a finite alphabet and [Formula: see text] be a pseudovariety of finite forest algebras. A language [Formula: see text] is [Formula: see text]-recognizable if its syntactic forest algebra belongs to [Formula: see text]. Separation is a classical problem in mathematics and computer science. It asks whether, given two sets belonging to some class, it is possible to separate them by another set of a smaller class. Suppose that a forest language [Formula: see text] and a forest [Formula: see text] are given. We want to find if there exists any proof for that [Formula: see text] does not belong to [Formula: see text] just by using [Formula: see text]-recognizable languages, i.e. given such [Formula: see text] and [Formula: see text], if there exists a [Formula: see text]-recognizable language [Formula: see text] which contains [Formula: see text] and does not contain [Formula: see text]. In this paper, we present how one can use profinite forest algebra to separate a forest language and a forest term and also to separate two forest languages.

Computing the nucleolus is recognized as an equitable solution to cooperative n person cost games, such as a vehicle routing game (VRG). Computing the nucleolus of a VRG, however, has been limited to small-sized benchmark instances with no more than 25 players, because of the computation time required to solve the NP-hard separation problem. To reduce computation time, we develop an enumerative algorithm that computes the nucleolus of the VRG with time windows (VRGTW) in the case of the non-empty core. Numerical simulations demonstrate the ability of the proposed algorithm to compute the nucleolus of benchmark instances with up to 100 players.

Scientific literature contains large volumes of complex, unstructured figures that are compound in nature (i.e. composed of multiple images, graphs, and drawings). Separation of these compound figures is critical for information retrieval from these figures. In this paper, we propose a new strategy for compound figure separation, which decomposes the compound figures into constituent subfigures while preserving the association between the subfigures and their respective caption components. We propose a two-stage framework to address the proposed compound figure separation problem. In particular, the subfigure label detection module detects all subfigure labels in the first stage. Then, in the subfigure detection module, the detected subfigure labels help to detect the subfigures by optimizing the feature selection process and providing the global layout information as extra features. Extensive experiments are conducted to validate the effectiveness and superiority of the proposed framework, which improves the detection precision by 9%.

For a variety of finite groups $\mathbf H$, let $\overline{\mathbf H}$ denote the variety of finite semigroups all of whose subgroups lie in $\mathbf H$. We give a characterization of the subsets of a finite semigroup that are pointlike with respect to $\overline{\mathbf H}$. Our characterization is effective whenever $\mathbf H$ has a decidable membership problem. In particular, the separation problem for $\overline{\mathbf H}$-languages is decidable for any decidable variety of finite groups $\mathbf H$. This generalizes Henckell's theorem on decidability of aperiodic pointlikes.

We investigate quantifier alternation hierarchies in first-order logic on finite words. Levels in these hierarchies are defined by counting the number of quantifier alternations in formulas. We prove that one can decide membership of a regular language in the levels $\mathcal{B}{\Sigma}_2$ (finite boolean combinations of formulas having only one alternation) and ${\Sigma}_3$ (formulas having only two alternations and beginning with an existential block). Our proofs work by considering a deeper problem, called separation, which, once solved for lower levels, allows us to solve membership for higher levels., Comment: arXiv admin note: text overlap with arXiv:1404.6832

A polymer of intrinsic microporosity, 1, has been incorporated into a series of polyelectrolyte multilayers via the layer-by-layer deposition method. One of these assemblies [a 6 nm multilayer derived from 1 plus poly(diallyldimethylammonium chloride)] showed exceptional permeation properties with respect to CO2 and N2. Specifically, this film exhibited a CO2 permeance of 130 GPU and a CO2/N2 selectivity of 33.

The separation of particles from liquids represents a cross-sectional technology, which touches nearly every industrial process, our personal life and the environment. It is obvious, that very different separation principles and a huge variety of highly specialized apparatuses are needed to solve all separation problems in such different areas of application. Looking to the history of apparatus development one can observe several interesting analogies to evolutionary processes in biology. Motivation for development of new separation technology normally is a preferably urgent need to solve a separation problem and the pressure to be successful on the market. To be successful a new concept must offer advantages in comparison to competing solutions. In contrast to nature the creative “genius” of the engineer in combination with advanced knowledge makes new developments more targeted and faster. Some evolutionary aspects of separation technology will be discussed in the example of filters and centrifuges. According to actual trends latest developments are demonstrated and some future prospects are pointed out.

While almost all existing works which optimally solve just-in-time scheduling problems propose dedicated algorithmic approaches, we propose in this work mixed integer formulations. We consider a single machine scheduling problem that aims at minimizing the weighted sum of earliness tardiness penalties around a common due-date. Using natural variables, we provide one compact formulation for the unrestrictive case and, for the general case, a non-compact formulation based on non-overlapping inequalities. We show that the separation problem related to the latter formulation is solved polynomially. In this formulation, solutions are only encoded by extreme points. We establish a theoretical framework to show the validity of such a formulation using non-overlapping inequalities, which could be used for other scheduling problems. A Branch-and-Cut algorithm together with an experimental analysis are proposed to assess the practical relevance of this mixed integer programming based methods., Comment: 32 pages, 10 figures