Search

Tree search algorithms, such as branch-and-bound, are the most widely used tools for solving combinatorial and non-convex problems. For example, they are the foremost method for solving (mixed) integer programs and constraint satisfaction problems. Tree search algorithms come with a variety of tunable parameters that are notoriously challenging to tune by hand. A growing body of research has demonstrated the power of using a data-driven approach to automatically optimize the parameters of tree search algorithms. These techniques use a training set of integer programs sampled from an application-specific instance distribution to find a parameter setting that has strong average performance over the training set. However, with too few samples, a parameter setting may have strong average performance on the training set but poor expected performance on future integer programs from the same application. Our main contribution is to provide the first sample complexity guarantees for tree search parameter tuning. These guarantees bound the number of samples sufficient to ensure that the average performance of tree search over the samples nearly matches its future expected performance on the unknown instance distribution. In particular, the parameters we analyze weight scoring rules used for variable selection. Proving these guarantees is challenging because tree size is a volatile function of these parameters: we prove that, for any discretization (uniform or not) of the parameter space, there exists a distribution over integer programs such that every parameter setting in the discretization results in a tree with exponential expected size, yet there exist parameter settings between the discretized points that result in trees of constant size. In addition, we provide data-dependent guarantees that depend on the volatility of these tree-size functions: our guarantees improve if the tree-size functions can be well approximated by simpler functions. Finally, via experiments, we illustrate that learning an optimal weighting of scoring rules reduces tree size. [ABSTRACT FROM AUTHOR]

We identify a sufficient condition, treewidth-pliability, that gives a polynomial-time algorithm for an arbitrarily good approximation of the optimal value in a large class of Max-2-CSPs parameterised by the class of allowed constraint graphs (with arbitrary constraints on an unbounded alphabet). Our result applies more generally to the maximum homomorphism problem between two rational-valued structures. The condition unifies the two main approaches for designing a polynomial-time approximation scheme. One is Baker's layering technique, which applies to sparse graphs such as planar or excluded-minor graphs. The other is based on Szemerédi's regularity lemma and applies to dense graphs. We extend the applicability of both techniques to new classes of Max-CSPs. However, we prove that the condition cannot be used to find solutions (as opposed to approximating the optimal value) in general. Treewidth-pliability turns out to be a robust notion that can be defined in several equivalent ways, including characterisations via size, treedepth, or the Hadwiger number. We show connections to the notions of fractional-treewidth-fragility from structural graph theory, hyperfiniteness from the area of property testing, and regularity partitions from the theory of dense graph limits. These may be of independent interest. In particular, we show that a monotone class of graphs is hyperfinite if and only if it is fractionally-treewidth-fragile and has bounded degree. [ABSTRACT FROM AUTHOR]

Abstract This study focuses on the precise model estimation for a position control problem actuated by a shape memory alloy (SMA) wire. Because the hysteresis characteristic of SMA introduces complexities in system modelling and adds degrees of freedom, a model with reduced order is implemented for controller design. This model is online updated by calculating a complementary term from the measured data to compensate for the SMA actuator dynamics and other parametric uncertainties. The position controller, derived from the formulated reduced‐order model, adapts itself to real conditions and is cost‐effective due to the use of only displacement sensor. The saturation of the control input is modelled within the structure of a constrained optimization problem solved by Karush–Kuhn–Tucker theorem. The boundedness of mean and covariance of tracking error and its derivative is demonstrated by stochastic analysis. The experimental results conducted on a platform incorporating a SMA wire show the efficiency of the proposed system in precisely controlling the position by admissible voltage range. The comparative results with a sliding mode controller indicate higher accuracy for the proposed controller to reduce the effect of uncertainties.

For a class of full‐states constraints nonlinear system with actuator failure, an adaptive fuzzy disturbance observer tracking design is carried out by using Lyapunov function and the dynamic surface method. The integral explosion problem is avoided by using the dynamic surface design method. Because the disturbance of the system is unknown, a nonlinear fuzzy disturbance observer is designed to estimate the unknown disturbance. And the unknown nonlinear function is approximated fuzzy logic systems. Based on the Lyapunov function method and backstepping approach, the stability of considered systems are analysed. And the proposed method can guarantee that all the signals in the closed‐loop system are bounded and the system output can track the desired signal to the small neighbourhood range. In addition, the fuzzy disturbance observer can estimate the unknown disturbance state well. Finally, several sets of simulation examples are given and compared with other method, and the experimental results are quantitatively analysed. Then, the robustness and superiority of the proposed control scheme are verified and demonstrated. [ABSTRACT FROM AUTHOR]

This study focuses on the precise model estimation for a position control problem actuated by a shape memory alloy (SMA) wire. Because the hysteresis characteristic of SMA introduces complexities in system modelling and adds degrees of freedom, a model with reduced order is implemented for controller design. This model is online updated by calculating a complementary term from the measured data to compensate for the SMA actuator dynamics and other parametric uncertainties. The position controller, derived from the formulated reduced‐order model, adapts itself to real conditions and is cost‐effective due to the use of only displacement sensor. The saturation of the control input is modelled within the structure of a constrained optimization problem solved by Karush–Kuhn–Tucker theorem. The boundedness of mean and covariance of tracking error and its derivative is demonstrated by stochastic analysis. The experimental results conducted on a platform incorporating a SMA wire show the efficiency of the proposed system in precisely controlling the position by admissible voltage range. The comparative results with a sliding mode controller indicate higher accuracy for the proposed controller to reduce the effect of uncertainties. [ABSTRACT FROM AUTHOR]

This paper proposes a heuristic approach for managing complex construction projects. The tool incorporates Primavera P6 EPPM and Synchro 4D, enabling proactive clash detection and resolution of spatial conflicts during concurrent tasks. Additionally, it performs resource verification for sufficient allocation before task initiation. This integrated approach facilitates the generation of conflict-free and feasible construction schedules. By adhering to project constraints and seamlessly integrating with existing industry tools, the proposed solution offers a comprehensive and robust approach to construction project management. This constitutes, to our knowledge, the first dynamic digital twin for the delivery of a complex project. [ABSTRACT FROM AUTHOR]

An ordering constraint satisfaction problem (OCSP) is defined by a family F of predicates mapping permutations on { 1 , … , k } to { 0 , 1 } . An instance of Max-OCSP(F ) on n variables consists of a list of constraints, each consisting of a predicate from F applied on k distinct variables. The goal is to find an ordering of the n variables that maximizes the number of constraints for which the induced ordering on the k variables satisfies the predicate. OCSPs capture well-studied problems including ‘maximum acyclic subgraph’ (MAS) and “maximum betweenness”. In this work, we consider the task of approximating the maximum number of satisfiable constraints in the (single-pass) streaming setting, when an instance is presented as a stream of constraints. We show that for every F , Max-OCSP(F ) is approximation-resistant to o(n)-space streaming algorithms, i.e., algorithms using o(n) space cannot distinguish streams where almost every constraint is satisfiable from streams where no ordering beats the random ordering by a noticeable amount. This space bound is tight up to polylogarithmic factors. In the case of MAS, our result shows that for every ϵ > 0 , MAS is not (1 / 2 + ϵ) -approximable in o(n) space. The previous best inapproximability result, due to Guruswami & Tao (2019), only ruled out 3/4-approximations in o (n) space. Our results build on recent works of Chou et al. (2022b, 2024) who provide a tight, linear-space inapproximability theorem for a broad class of “standard” (i.e., non-ordering) constraint satisfaction problems (CSPs) over arbitrary (finite) alphabets. Our results are obtained by building a family of appropriate standard CSPs (one for every alphabet size q) from any given OCSP and applying their theorem to this family of CSPs. To convert the resulting hardness results for standard CSPs back to our OCSP, we show that the hard instances from this earlier theorem have the following “partition expansion” property with high probability: For every partition of the n variables into small blocks, for most of the constraints, all variables are in distinct blocks. [ABSTRACT FROM AUTHOR]

Finite-domain constraint satisfaction problems are either solvable by Datalog or not even expressible in fixedpoint logic with counting. The border between the two regimes can be described by a universal-algebraic minor condition. For infinite-domain constraint satisfaction problems (CSPs), the situation is more complicated even if the template structure of the CSP is model-theoretically tame.We prove that there is no Maltsev condition that characterizes Datalog already for the CSPs of first-order reducts of (Q; <); such CSPs are called temporal CSPs and are of fundamental importance in infinite-domain constraint satisfaction. Our main result is a complete classification of temporal CSPs that can be expressed in one of the following logical formalisms: Datalog, fixed-point logic (with or without counting), or fixed-point logic with the mod-2 rank operator. The classification shows that many of the equivalent conditions in the finite fail to capture expressibility in Datalog or fixed-point logic already for temporal CSPs. [ABSTRACT FROM AUTHOR]

A reflexive cycle is any reflexive digraph whose underlying undirected graph is a cycle. Call a relational structure Słupecki if its surjective polymorphisms are all essentially unary. We prove that all reflexive cycles of girth at least 4 have this property. [ABSTRACT FROM AUTHOR]

High‐speed trains (HSTs) often face challenges associated with car‐body hunting, resulting from factors such as complex operating environments and wheel‐rail contact degradation. These issues have a significant impact on the ride quality and operational safety. Passive suspension systems are inadequate to provide satisfactory dynamic performance for HSTs in such circumstances. However, active suspension systems can provide an effective solution. To address the car‐body hunting stability of HSTs, this study proposes a novel control approach called displacement inequality constraint following control (ICFC‐BIS) for the active suspension of HSTs. The ICFC‐BIS leverages the beneficial nonlinearity of bio‐inspired structures (BIS) to indirectly achieve excellent dynamic characteristics of the BIS through actuators installed in the suspension of HSTs, eliminating the need for actual BIS installation. Numerical simulation results demonstrate that the proposed ICFC‐BIS can effectively suppress car‐body hunting motion, thereby enhancing the ride comfort of HSTs. Consequently, the operational safety and ride comfort indices of HSTs equipped with active suspension systems are significantly improved. [ABSTRACT FROM AUTHOR]

CG:SHOP is an annual geometric optimization challenge and the 2022 edition proposed the problem of coloring a certain geometric graph defined by line segments. Surprisingly, the top three teams used the same technique, called conflict optimization. This technique has been introduced in the 2021 edition of the challenge, to solve a coordinated motion planning problem. In this article, we present the technique in the more general framework of binary constraint satisfaction problems (binary CSP). Then, the top three teams describe their different implementations of the same underlying strategy. We evaluate the performance of those implementations to vertex color not only geometric graphs, but also other types of graphs. [ABSTRACT FROM AUTHOR]

Abstract This paper conducts research on obstacle and collision avoidance under kinematical constraints in unknown environments, while communication and simultaneous localization and mapping (SLAM) are unavailable to agents. Then a strategy based on mixed‐integer programming is proposed, in which velocity constraints are established with a modified Barrier function for obstacles that can be completely detected. As for obstacles that cannot be completely detected, a feasible set is built for the velocity programming based on the convex theory, and the contradicted constraints are addressed with the logic metric method. Besides, the actuator saturation is avoided by converting kinematical constraints into the restrictions on the magnitude, the restrictions on the direction, and the negative correlations between the components of the velocity respectively. Given that invalid nominal velocity leads to collisions, a virtual goal is estimated for nominal velocity improvement. In addition, the local extremum brought by empty programming space due to multiple constraints is repaired by fixing the velocity constraints. The feasibility of the proposed strategy is analyzed, and numerical simulations are provided to verify the effectiveness of the proposed strategy.

The factor graph of an instance of a constraint satisfaction problem with n variables and m constraints is the bipartite graph between [m] and [n] describing which variable appears in which constraints. Thus, an instance of a CSP is completely determined by its factor graph and the list of predicates. We show optimal inapproximability of Max-3-LIN over non-Abelian groups (both in the perfect completeness case and in the imperfect completeness case), even when the factor graph is fixed. Previous reductions which proved similar optimal inapproximability results produced factor graphs that were dependent on the input instance. Along the way, we also show that these optimal hardness results hold even when we restrict the linear equations in the Max-3-LIN instances to the form x · y · z = g , where x, y, z are the variables and g is a group element. We use representation theory and Fourier analysis over non-Abelian groups to analyze the reductions. [ABSTRACT FROM AUTHOR]

Abstract This paper aims to discuss the approach of constrained modified feedback linearization model predictive control for the spacecraft simulator. By utilizing the high accuracy and constrained properties of model predictive control (MPC), an optimum MPC is designed for the spacecraft feedback linearized system. The composite controller has the ability to control both the attitude and angular velocity of the reaction wheels (i.e. steering the angular momentum to zero at the end of the maneuver). The simulation and experimental results demonstrate that the proposed hybrid controller has an insignificant calculative cost and facilitates the spacecraft to perform regulation maneuver with sufficient precision in the presence of external torques and actuator saturations.

This paper proposes a heuristic approach for managing complex construction projects. The tool incorporates Primavera P6 EPPM and Synchro 4D, enabling proactive clash detection and resolution of spatial conflicts during concurrent tasks. Additionally, it performs resource verification for sufficient allocation before task initiation. This integrated approach facilitates the generation of conflict-free and feasible construction schedules. By adhering to project constraints and seamlessly integrating with existing industry tools, the proposed solution offers a comprehensive and robust approach to construction project management. This constitutes, to our knowledge, the first dynamic digital twin for the delivery of a complex project.

Evaluating conjunctive queries (CQs) is NP-hard in general; however, acyclic CQs or nearest acyclic CQs can be evaluated in polynomial time. Many structural methods for characterising such classes are proposed in the literature. However, exploiting these methods to answer CQs is not efficient in practice when the relations have a realistic size. In this work, we propose a new method called HSJ-Solver for evaluating CQs and for solving constraint satisfaction problems (CSPs) represented by a generalised hypertree decomposition (GHD). Experiments carried out on CSP benchmarks show that using HSJ-Solver significantly improves the achieved performance. [ABSTRACT FROM AUTHOR]

Convex relaxations of nonconvex functions provide useful bounding information in applications such as deterministic global optimization and reachability analysis. In some situations, the original nonconvex functions may not be known explicitly, but are instead described implicitly by nonlinear equation systems. In these cases, established convex relaxation methods for closed-form functions are not directly applicable. This article presents a new general strategy to construct convex relaxations for such implicit functions. These relaxations are described as convex parametric programs whose constraints are convex relaxations of the original residual function. This relaxation strategy is straightforward to implement, produces tight relaxations in practice, is particularly efficient to carry out when monotonicity properties can be exploited, and does not assume the existence or uniqueness of an implicit function on the entire intended domain. Unlike all previous approaches to the authors' knowledge, this new approach permits any relaxations of the residual function; it does not require the residual relaxations to be factorable or to be obtained from a McCormick-like traversal of a computational graph. This new convex relaxation strategy is extended to inverse functions, compositions involving implicit functions, feasible-set mappings in constraint satisfaction problems, and solutions of parametric ODEs. Based on a proof-of-concept implementation in Julia, numerical examples are presented to illustrate the convex relaxations produced for various implicit functions and optimal-value functions. [ABSTRACT FROM AUTHOR]

This paper conducts research on obstacle and collision avoidance under kinematical constraints in unknown environments, while communication and simultaneous localization and mapping (SLAM) are unavailable to agents. Then a strategy based on mixed‐integer programming is proposed, in which velocity constraints are established with a modified Barrier function for obstacles that can be completely detected. As for obstacles that cannot be completely detected, a feasible set is built for the velocity programming based on the convex theory, and the contradicted constraints are addressed with the logic metric method. Besides, the actuator saturation is avoided by converting kinematical constraints into the restrictions on the magnitude, the restrictions on the direction, and the negative correlations between the components of the velocity respectively. Given that invalid nominal velocity leads to collisions, a virtual goal is estimated for nominal velocity improvement. In addition, the local extremum brought by empty programming space due to multiple constraints is repaired by fixing the velocity constraints. The feasibility of the proposed strategy is analyzed, and numerical simulations are provided to verify the effectiveness of the proposed strategy. [ABSTRACT FROM AUTHOR]

This paper aims to discuss the approach of constrained modified feedback linearization model predictive control for the spacecraft simulator. By utilizing the high accuracy and constrained properties of model predictive control (MPC), an optimum MPC is designed for the spacecraft feedback linearized system. The composite controller has the ability to control both the attitude and angular velocity of the reaction wheels (i.e. steering the angular momentum to zero at the end of the maneuver). The simulation and experimental results demonstrate that the proposed hybrid controller has an insignificant calculative cost and facilitates the spacecraft to perform regulation maneuver with sufficient precision in the presence of external torques and actuator saturations. This paper aims to discuss the approach of constrained modified feedback linearization model predictive control (CMFLMPC) for the spacecraft simulator. The simulation and experimental results demonstrate that the proposed hybrid controller has an insignificant calculative cost and facilitates the spacecraft to perform the regulation maneuver with sufficient precision in the presence of external torques and actuator saturations. [ABSTRACT FROM AUTHOR]

A constraint satisfaction problem (CSP) is, in its most general form, an NP-complete problem. One of the several classes of tractable problems that exist contains all the problems with a restricted structure of the constraint scopes. This paper studies community structure, a particular type of restricted structure underpinning a class of tractable SAT problems with potentially similar relevance to CSPs. Using the modularity, it explores the community structure of a wide variety of problems with both academic and industrial relevance. Its impact on the search times of several general solvers, as well as one that uses tree-decomposition, is also analysed to determine whether constraint solvers exploit this type of structure. Nearly all CSP instances have a strong community structure, and those belonging to the same class have comparable modularity values. For the general solvers, strong correlations between the community structure and the search times are not apparent. A more definite correlation exists between the modularity and the search times of the tree-decomposition, suggesting that it might, in part, be able to take advantage of the community structure. However, combined with the relatively strong correlation between the modularity and the tree-width, it could also indicate a similarity between these two measures. [ABSTRACT FROM AUTHOR]

Semidefinite programming is a powerful tool in the design and analysis of approximation algorithms for combinatorial optimization problems. In particular, the random hyperplane rounding method of Goemans and Williamson [31] has been extensively studied for more than two decades, resulting in various extensions to the original technique and beautiful algorithms for a wide range of applications. Despite the fact that this approach yields tight approximation guarantees for some problems, e.g., Max-Cut, for many others, e.g., Max-SAT and Max-DiCut, the tight approximation ratio is still unknown. One of the main reasons for this is the fact that very few techniques for rounding semi-definite relaxations are known. In this work, we present a new general and simple method for rounding semi-definite programs, based on Brownian motion. Our approach is inspired by recent results in algorithmic discrepancy theory. We develop and present tools for analyzing our new rounding algorithms, utilizing mathematical machinery from the theory of Brownian motion, complex analysis, and partial differential equations. Focusing on constraint satisfaction problems, we apply our method to several classical problems, including Max-Cut, Max-2SAT, and Max-DiCut, and derive new algorithms that are competitive with the best known results. To illustrate the versatility and general applicability of our approach, we give new approximation algorithms for the Max-Cut problem with side constraints that crucially utilizes measure concentration results for the Sticky Brownian Motion, a feature missing from hyperplane rounding and its generalizations. [ABSTRACT FROM AUTHOR]

In configuration design, the task is to compose a system out of a set of predefined, modu-lar building blocks assembled by defined interfaces. Product configuration systems, both with or without integration of geometric models, implement reasoning techniques to model and explore the resulting solution spaces. Among others, the formulation of constraint satisfaction problems (CSP) is state of the art and the informational background in many proprietary configuration engine software packages. Basically, configuration design tasks can also be implemented in modern computer aided design (CAD) systems as these contain different techniques for knowledge-based product modeling but literature reports only little about detailed application examples, best practices or training materials. This article aims at bridging this gap and presents a step-by-step implementation guide for CSP-based CAD configurators for combinatorial designs with the example of Autodesk Inventor. [ABSTRACT FROM AUTHOR]

Asymmetry in the synaptic interactions between neurons plays a crucial role in determining the memory storage and retrieval properties of recurrent neural networks. In this work, we analyze the problem of storing random memories in a network of neurons connected by a synaptic matrix with a definite degree of asymmetry. We study the corresponding satisfiability and clustering transitions in the space of solutions of the constraint satisfaction problem associated with finding synaptic matrices given the memories. We find, besides the usual SAT/UNSAT transition at a critical number of memories to store in the network, an additional transition for very asymmetric matrices, where the competing constraints (definite asymmetry vs memories storage) induce enough frustration in the problem to make it impossible to solve. This finding is particularly striking in the case of a single memory to store, where no quenched disorder is present in the system. [ABSTRACT FROM AUTHOR]

Quantum computing has the potential to revolutionize the way hard computational problems are solved in terms of speed and accuracy. Quantum hardware is an active area of research and different hardware platforms are being developed. Quantum algorithms target each hardware implementation and bring advantages to specific applications. The focus of this paper is to compare how well quantum annealing techniques and the QAOA models constrained optimization problems. As a use case, a constrained optimization problem called mission covering optimization is used. Quantum annealing is implemented in adiabatic hardware such as D-Wave, and QAOA is implemented in gate-based hardware such as IBM. This effort provides results in terms of cost, timing, constraints held, and qubits used. [ABSTRACT FROM AUTHOR]

We study the complexity of Boolean constraint satisfaction problems (CSPs) when the assignment must have Hamming weight in some congruence class modulo M, for various choices of the modulus M. Due to the known classification of tractable Boolean CSPs, this mainly reduces to the study of three cases: \sanstwo -\sansS \sansA \sansT, \sansH \sansO \sansR \sansN -\sansS \sansA \sansT, and \sansL \sansI \sansN -\sanstwo (linear equations mod 2). We classify the moduli M for which these respective problems are polynomial time solvable, and when they are not (assuming the exponential time hypothesis). Our study reveals that this modular constraint lends a surprising richness to these classic, well-studied problems, with interesting broader connections to complexity theory and coding theory. The \sansH \sansO \sansR \sansN -\sansS \sansA \sansT case is connected to the covering complexity of polynomials representing the \sansN \sansA \sansN \sansD function mod M. The \sansL \sansI \sansN -\sanstwo case is tied to the sparsity of polynomials representing the \sansO \sansR function mod M, which in turn has connections to modular weight distribution properties of linear codes and locally decodable codes. In both cases, the analysis of our algorithm as well as the hardness reduction rely on these polynomial representations, highlighting an interesting algebraic common ground between hard cases for our algorithms and the gadgets which show hardness. These new complexity measures of polynomial representations merit further study. The inspiration for our study comes from a recent work by N\"agele, Sudakov, and Zenklusen on submodular minimization with a global congruence constraint. Our algorithm for \sansH \sansO \sansR \sansN -\sansS \sansA \sansT has strong similarities to their algorithm, and in particular identical kinds of set systems arise in both cases. Our connection to polynomial representations leads to a simpler analysis of such set systems and also sheds light on (but does not resolve) the complexity of submodular minimization with a congruency requirement modulo a composite M. [ABSTRACT FROM AUTHOR]

Constraint satisfaction problems (CSPs) are combinatorial problems with strong ties to universal algebra and clone theory. The recently proved CSP dichotomy theorem states that each finite-domain CSP is either solvable in polynomial time, or that it is NP-complete. However, among the intractable CSPs there is a seemingly large variance in how fast they can be solved by exponential-time algorithms, which cannot be explained by the classical algebraic approach based on polymorphisms. In this contribution we will survey an alternative approach based on partial polymorphisms, which is useful for studying the fine-grained complexity of NP-complete CSPs. Moreover, we will state and discuss some challenging open problems in this research field. [ABSTRACT FROM AUTHOR]

Obtaining lower bounds for NP-hard problems has for a long time been an active area of research. Algebraic techniques introduced by Jonsson et al. (2017) [4] show that the fine-grained time complexity of the parameterized ▪ problem correlates to the lattice of strong partial clones. With this ordering they isolated a relation R such that ▪ can be solved at least as fast as any other NP-hard ▪ problem. In this paper we extend this method and show that such languages also exist for the surjective SAT problem , the max ones problem , the propositional abduction problem , and the Boolean valued constraint satisfaction problem over finite-valued constraint languages. These languages may be interesting when investigating the borderline between polynomial time, subexponential time and exponential-time algorithms since they in a precise sense can be regarded as NP-hard problems with minimum time complexity. Indeed, with the help of these languages we relate all of the above problems to the exponential time hypothesis (ETH) in several different ways. [ABSTRACT FROM AUTHOR]

Given an ideal I and a polynomial f the Ideal Membership Problem (IMP) is to test if f ∈ I. This problem is a fundamental algorithmic problem with important applications and notoriously intractable. We study the complexity of the IMP for combinatorial ideals that arise from constrained problems over the Boolean domain. As our main result, we identify the borderline of tractability. By using Gröbner bases techniques, we extend Schaefer's dichotomy theorem [STOC, 1978] which classifies all Constraint Satisfaction Problems (CSPs) over the Boolean domain to be either in P or NP-hard. Moreover, our result implies necessary and sufficient conditions for the efficient computation of Theta Body Semi-Definite Programming (SDP) relaxations, identifying therefore the borderline of tractability for constraint language problems. This article is motivated by the pursuit of understanding the recently raised issue of bit complexity of Sum-of-Squares (SoS) proofs [O'Donnell, ITCS, 2017]. Raghavendra and Weitz [ICALP, 2017] show how the IMP tractability for combinatorial ideals implies bounded coefficients in SoS proofs. [ABSTRACT FROM AUTHOR]

In configuration design, the task is to compose a system out of a set of predefined, modu-lar building blocks assembled by defined interfaces. Product configuration systems, both with or without integration of geometric models, implement reasoning techniques to model and explore the resulting solution spaces. Among others, the formulation of constraint satisfaction problems (CSP) is state of the art and the informational background in many proprietary configuration engine software packages. Basically, configuration design tasks can also be implemented in modern computer aided design (CAD) systems as these contain different techniques for knowledge-based product modeling but literature reports only little about detailed application examples, best practices or training materials. This article aims at bridging this gap and presents a step-by-step implementation guide for CSP-based CAD configurators for combinatorial designs with the example of Autodesk Inventor.

The logic MMSNP is a restricted fragment of existential second-order logic which can express many interesting queries in graph theory and finite model theory. The logic was introduced by Feder and Vardi, who showed that every MMSNP sentence is computationally equivalent to a finite-domain constraint satisfaction problem (CSP); the involved probabilistic reductions were derandomized by Kun using explicit constructions of expander structures. We present a new proof of the reduction to finite-domain CSPs that does not rely on the results of Kun. The new universalalgebraic proof allows us to obtain a stronger statement and to verify the more general Bodirsky--Pinsker dichotomy conjecture for CSPs in MMSNP. Our approach uses the fact that every MMSNP sentence describes a finite union of CSPs for countably infinite ѡ-categorical structures; moreover, by a recent result of Hubička and Nešetřil, these structures can be expanded to homogeneous structures with finite relational signature and the Ramsey property. [ABSTRACT FROM AUTHOR]

Quantum computing has the potential to revolutionize the way hard computational problems are solved in terms of speed and accuracy. Quantum hardware is an active area of research and different hardware platforms are being developed. Quantum algorithms target each hardware implementation and bring advantages to specific applications. The focus of this paper is to compare how well quantum annealing techniques and the QAOA models constrained optimization problems. As a use case, a constrained optimization problem called mission covering optimization is used. Quantum annealing is implemented in adiabatic hardware such as D-Wave, and QAOA is implemented in gate-based hardware such as IBM. This effort provides results in terms of cost, timing, constraints held, and qubits used.

The inverse satisfiability problem over a set of relations Γ (Inv-SAT (Γ)) is the problem of deciding whether a relation R can be defined as the set of models of a SAT (Γ) instance. Kavvadias and Sideri (1998) [15] obtained a dichotomy between P and co-NP-complete for finite Γ containing the two constant Boolean relations. However, for arbitrary constraint languages the complexity has been wide open, and in this article we finally prove a complete dichotomy theorem for finite languages. Kavvadias and Sideri's techniques are not applicable and we have to turn to the more recent algebraic approach based on partial polymorphisms. We also study the complexity of the inverse constraint satisfaction problem prove a general hardness result, which in particular resolves the complexity of inverse k -colouring , mentioned as an open problem in Chen (2008) [8]. [ABSTRACT FROM AUTHOR]