Search

We close three open problems on the separation complexity of valid inequalities for the knapsack polytope. Specifically, we establish that the separation problems for extended cover inequalities, (1, k)-configuration inequalities, and weight inequalities are all N P -complete. We also show that, when the number of constraints of the LP relaxation is constant and its optimal solution is an extreme point, then the separation problems of both extended cover inequalities and weight inequalities can be solved in polynomial time. Moreover, we provide a natural generalization of (1, k)-configuration inequality which is easier to separate and contains the original (1, k)-configuration inequality as a strict sub-family. [ABSTRACT FROM AUTHOR]

Machine-learning-based behavioural tracking is a rapidly growing method in the behavioural sciences providing data with high spatial and temporal resolution while reducing the risk of observer bias. Nevertheless, only a few canine behaviour studies have applied this method. In the current study, we used three-dimensional (3D) tracking of the dogs' bodies to study how separation from the caregiver affected the dogs' behaviour in a novel environment. During the study, the dogs could move freely in a room equipped with trial-unique objects. We manipulated across trials whether the owner and/or a stranger was present in the room to evaluate the secure base effect, the tendency to explore and play more in the presence of the caregiver compared to another person. This secure base effect is considered a key characteristic of human attachment bonds and has also been described for the dog–caregiver relationship. The tracking data were internally consistent and highly correlated with human scorings and measurements. The results show that both the owner and stranger significantly increased the dogs' exploration; the dogs also spent more time in the proximity of the owner and stranger location when they were present. Even though the presence of both owner and stranger had a significant effect on the dogs' behaviour, the effect of the owner was more pronounced. Moreover, in the presence of the stranger the dogs spent more time close to their owner and showed a reduced tail-wagging asymmetry to the right side further supporting the distinct effect of owner and stranger on the dogs' behaviour. We conclude that machine-driven 3D tracking provides an efficient and reliable access for detailed behavioural analyses of dogs' exploration and attachment-related behaviours. • We used machine-learning-based 3D tracking to measure dogs' exploratory behaviour. • Dogs explored a room with new objects in the presence of the owner and/or stranger. • The tracking data were internally consistent and highly correlated with human scorings. • Both the owner and stranger's presence significantly increased the dogs' exploration. • Dogs' tail-wagging asymmetry and proximity seeking supported caregiver's special role. [ABSTRACT FROM AUTHOR]

We investigate quantifier alternation hierarchies in first-order logic on finitewords. 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 BΣ2 (finite Boolean combinations of formulas having only one alternation) and Σ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. [ABSTRACT FROM AUTHOR]

Abstract Consider the bi-harmonic differential expression of the form A=△M2+q $ 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 L p (M), if for all u∈L p (M) such that Au∈L p (M), we have qu∈L p (M). In this paper, we give sufficient conditions for A to be separated in L p (M),where 1

The 0/1 knapsack polytope is the convex hull of all 0/1 vectors that satisfy a given single linear inequality with non-negative coefficients. This paper provides a comprehensive overview of knapsack polytopes. We discuss basic polyhedral properties, (lifted) cover and other valid inequalities, cases for which complete linear descriptions are known, geometric properties for small dimensions, and connections to independence systems. We also discuss the generalization to (mixed-)integer knapsack polytopes and variants. [ABSTRACT FROM AUTHOR]

Separation is one of the most commonly encountered estimation problems in the context of logistic regression, which often occurs with small and medium sample sizes. The method of maximum likelihood (MLE; [8]) provides spuriously high parameter estimates and their standard errors under separation in logistic regression. Many researchers in social sciences utilize simple but ad-hoc solutions to overcome this issue, such as "doing nothing strategy", removing variable(s) from the model, and combining the levels of the categorical variable in the data causing separation etc. The limitations of these basic solutions have motivated researchers to use more appropriate and innovative estimation techniques to deal with the problem. However, the performance and comparison of these techniques have not been fully investigated yet. The main goal of this paper is to close this research gap by comparing the performance of frequentist and Bayesian estimation methods for coping with separation. A simulation study is performed to investigate the performance of asymptotic, bootstrap-based, and Bayesian estimation techniques with respect to bias, precision, and accuracy measures under separation. In line with the simulation study, a real-data example is used to illustrate how to utilize these methods to solve separation in logistic regression. [ABSTRACT FROM AUTHOR]

The 1‐wheel inequalities for the stable set polytope were introduced by Cheng and Cunningham. In general, there is an exponential number of these inequalities. We present a new polynomial size extended formulation of the stable set relaxation that includes the odd cycle and 1‐wheel inequalities. This compact formulation allows one to polynomially optimize over a polyhedron instead of handling the separation problem for 1‐wheel inequalities by solving many shortest walk problems and relying on the ellipsoid method. [ABSTRACT FROM AUTHOR]

Given polyhedron P and and a point x ∗ , the separation problem for polyhedra asks to certify that x ∗ ∈ P and if not, to determine an inequality that is satisfied by P and violated by x ∗ . This problem is repeatedly solved in cutting plane methods for Integer Programming and the quality of the violated inequality is an essential feature in the performance of such methods. In this paper we address the problem of finding efficiently an inequality that is violated by x ∗ and either defines an improper face or a facet of P. We show that, by solving a single linear program, one almost surely obtains such an improper face or facet. [ABSTRACT FROM AUTHOR]

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

In the theory of formal languages, the understanding of concatenation hierarchies of regular languages is one of the most fundamental and challenging topics. In this paper, we survey progress made on this problem since 1971. We also establish new generic statements regarding this problem. [ABSTRACT FROM AUTHOR]

Clique inequalities appear in linear descriptions of many combinatorial optimisation problems. In general, they form an exponential family and, in addition, the associated separation problem is strongly NP-hard, being equivalent to a maximum weight clique problem. Therefore, most of the known (both exact and heuristic) separation procedures follow the decomposition scheme of a maximum clique algorithm. We introduce a new heuristic, aimed at constructing a collection of (violated) clique inequalities covering all the edges of the underlying graph. We present an extensive computational experience showing that this closely approximates the results of an exact separation oracle while being faster than standard heuristics. [ABSTRACT FROM AUTHOR]

We propose a moment relaxation for two problems, the separation and covering problems with semialgebraic sets generated by a polynomial of degree d. We show that (a) the optimal value of the relaxation finitely converges to the optimal value of the original problem, when the moment order r increases, and (b) after performing some small perturbation of the original problem, convergence can be achieved with r = d. We further provide a practical iterative algorithm that is computationally tractable for large datasets and present encouraging computational results. [ABSTRACT FROM AUTHOR]

An important endeavor in computer science is to precisely understand the expressive power of descriptive formalisms (such as fragments of first-order logic) over discrete structures (such as finite words, trees or graphs). Of course, the term "understanding" is not a precise mathematical notion. Therefore, carrying out this investigation requires a concrete objective to capture this understanding. In the literature, the standard choice for this objective is the membership problem, whose aim is to find a procedure deciding whether an input language can be defined in the formalism under investigation. This approach was cemented as the "right" one by the seminal work of Schützenberger, McNaughton and Papert on "first-order logic over finite words", and has been in use since then. Unfortunately, membership questions are hard: for several fundamental formalisms, researchers have failed in this endeavor despite decades of investigation. In view of recent results on one of the most famous open questions, namely membership for all levels in the quantifier alternation hierarchy of first-order logic, an explanation may be that membership is too restrictive as a setting. Indeed, these new results were obtained by considering more general problems than membership, taking advantage of the increased flexibility of the enriched mathematical setting. Investigating such new problems opened a promising research avenue, which permitted to solve membership for natural fragments of first-order logic. However, many of these problems are ad hoc: for each fragment, the solution relies on a specific one. A unique new problem replacing membership as the right one is still missing. The main contribution of this paper is a suitable candidate to play this role: the covering problem. We motivate this problem with several arguments. First, it admits an elementary set theoretic formulation, similar to membership. Second, we are able to reexplain or generalize all known results with this problem. Third, we develop a mathematical framework as well as a methodology tailored to the investigation of this problem. At last, for each class admitting a decidable membership, we are able to instantiate our methodology to solve this more general problem. In particular, this yields constructive solutions to membership. We illustrate our approach with algorithms solving covering (hence also membership and generalizations thereof, such as the problem called separation) for some classical fragments of first-order logic: level 1 in the quantifier alternation hierarchy of first-order logic, which consists of the so called piecewise testable languages, the well-known 2-variable fragment of first-order logic, and level ½ in the quantifier alternation hierarchy of first-order logic. [ABSTRACT FROM AUTHOR]

For two given ω-terms α and β, the word problem for ω-terms over a variety V asks whether α = β in all monoids in V. We show that the word problem for ω-terms over each level of the Trotter-Weil Hierarchy is decidable. More precisely, for every fixed variety in the Trotter-Weil Hierarchy, our approach yields an algorithm in nondeterministic logarithmic space (NL). In addition, we provide deterministic polynomial time algorithms which are more efficient than straightforward translations of the NL-algorithms. As an application of our results, we show that separability by the so-called corners of the Trotter-Weil Hierarchy is witnessed by ω-terms (this property is also known as ω-reducibility). In particular, the separation problem for the corners of the Trotter-Weil Hierarchy is decidable. [ABSTRACT FROM AUTHOR]

The class of strict-feedback systems enjoys special properties that make it similar to linear systems. This paper proves that such a class is equivalent, under a change of coordinates, to the wider class of feedback linearisable systems with multiplicative input, when the multiplicative terms are functions of the measured variables only. We apply this result to the control problem of feedback linearisable nonlinear MIMO systems with input and/or output delays. In this way, we provide sufficient conditions under which a separation result holds for output feedback control and moreover a predictor-based controller exists. When these conditions are satisfied, we obtain that the existence of stabilising controllers for arbitrarily large delays in the input and/or the output can be proved for a wider class of systems than previously known. [ABSTRACT FROM AUTHOR]