In the context of CSPs, a strong backdoor is a subset of variables such that every complete assignment yields a residual instance guaranteed to have a specified property. If the property allows efficient solving, then...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
In the context of CSPs, a strong backdoor is a subset of variables such that every complete assignment yields a residual instance guaranteed to have a specified property. If the property allows efficient solving, then a small strong backdoor provides a reasonable decomposition of the original instance into easy instances. An important challenge is the design of algorithms that can find quickly a small strong backdoor if one exists. We present a systematic study of the parameterized complexity of backdoor detection when the target property is a restricted type of constraint language defined by means of a family of polymorphisms. In particular, we show that under the weak assumption that the polymorphisms are idempotent, the problem is unlikely to be FPT when the parameter is either r (the constraint arity) or k (the size of the backdoor) unless P = NP or FPT = W[2]. When the parameter is k + r, however, we are able to identify large classes of languages for which the problem of finding a small backdoor is FPT.
Packing 2D objects in a limited space is an ubiquitous problem with many academic and industrial variants. In any case, solving this problem requires the ability to determine where a first object can be placed so that...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Packing 2D objects in a limited space is an ubiquitous problem with many academic and industrial variants. In any case, solving this problem requires the ability to determine where a first object can be placed so that it does not intersect a second, previously placed, object. this subproblem is called the non-overlapping constraint. the complexity of this non-overlapping constraint depends on the type of objects considered. It is simple in the case of rectangles. It has also been studied in the case of polygons. this paper proposes a numerical approach for the wide class of objects described by non-linear inequalities. Our goal here is to calculate the non-overlapping constraint, that is, to describe the set of all positions and orientations that can be assigned to the first object so that intersection withthe second one is empty. this is done using a dedicated branch & prune approach. We first show that the non-overlapping constraint can be cast into a Minkowski sum, even if we take into account orientation. We derive from this an inner contractor, that is, an operator that removes from the current domain a subset of positions and orientations that necessarily violate the non-overlapping constraint. this inner contractor is then embedded in a sweeping loop, a pruning technique that was only used with discrete domains so far. We finally come up with a branch & prune algorithm that outperforms Rsolver, a generic state-of-the-art solver for continuous quantified constraints.
Real-Time Embedded Systems (RTES) in safety-critical domains, such as maritime and energy, must satisfy strict performance requirements to be deemed safe. therefore, such systems have to be thoroughly tested to ensure...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Real-Time Embedded Systems (RTES) in safety-critical domains, such as maritime and energy, must satisfy strict performance requirements to be deemed safe. therefore, such systems have to be thoroughly tested to ensure their correct behavior even under the worst operating conditions. In this paper, we address the need of deriving worst case scenarios with respect to three common performance requirements, namely task deadlines, response time, and CPU usage. Specifically, we investigate whether this worst-case analysis can be effectively re-expressed as a Constrained Optimization Problem (COP) over the space of possible inputs to the system. Solving this problem means finding the sets of inputs that maximize the chance to violate performance requirements at runtime. Such inputs can in turn be used to test if the target RTES meets the expected performance even in the worst case. We develop an OPL model for IBM ILOG CP OPTIMIZER that implements a task priority-based preemptive scheduling, and apply it to a case study from the maritime and energy domain. Our validation shows that (1) the input to our model can be provided with reasonable effort in an industrial setting, and (2) the COP effectively identifies test cases that maximize deadline misses, response time, and CPU usage.
MC-nets is a concise representation of the characteristic functions that exploits a set of rules to compute payoffs. Given a MC-nets instance, the problem of computing a payoff division in the least core, which is a g...
详细信息
ISBN:
(数字)9783319131917
ISBN:
(纸本)9783319131917;9783319131900
MC-nets is a concise representation of the characteristic functions that exploits a set of rules to compute payoffs. Given a MC-nets instance, the problem of computing a payoff division in the least core, which is a generalization of the core-non-emptiness problem that is known to be coNP-complete, is definitely a hard computational problem. In fact, to the best of our knowledge, no algorithm can actually compute such a payoff division for MC-nets instances with dozens of agents. We propose a new algorithm for this problem, that exploits the constraint generation technique to solve the linear programming problem that potentially has a huge number of constraints. Our experimental results are striking since, using 8 GB memory, our proposed algorithm can successfully compute a payoff division in the least core for the instances with up to 100 agents, but the naive algorithm fails due to a lack of memory for instances with 30 or more agents.
Game theory studies situations in which multiple agents having conflicting objectives have to reach a collective decision. the question of a compact representation language for agents utility function is of crucial im...
详细信息
the Balance constraint introduced by Beldiceanu ensures solutions are balanced. this is useful when, for example, there is a requirement for solutions to be fair. Balance bounds the difference B between the minimum an...
详细信息
When solving a problem using constraintprogramming, constraint modelling is widely acknowledged as an important and difficult task. Even a constraint modelling expert may explore many models and spend considerable ti...
详细信息
the proceedings contain 71 papers. the topics discussed include: constraintprogramming and a usability quest;optimization challenges in smart grid operations;where are the interesting problems?;a generic method for i...
ISBN:
(纸本)9783642335570
the proceedings contain 71 papers. the topics discussed include: constraintprogramming and a usability quest;optimization challenges in smart grid operations;where are the interesting problems?;a generic method for identifying and exploiting dominance relations;scheduling scientific experiments on the Rosetta/Philae mission;an optimal arc consistency algorithm for a chain of atmost constraints with cardinality;conflict directed lazy decomposition;boosting local consistency algorithms over floating-point numbers;a model seeker: extracting global constraint models from positive examples;on computing minimal equivalent subformulas;Weibull-based benchmarks for bin packing;space-time tradeoffs for the regular constraint;inter-instance nogood learning in constraintprogramming;a characterization of the complexity of forbidding subproblems in binary max-CSP;and optimization modeling for software developers.
principles of agile information systems development (ISD) have attracted the interest of practice as well as research. the goal of this literature review is to validate, update and extend previous reviews in terms of ...
详细信息
ISBN:
(纸本)9781479925056
principles of agile information systems development (ISD) have attracted the interest of practice as well as research. the goal of this literature review is to validate, update and extend previous reviews in terms of the general state of research on agile ISD. Besides including categories such as the employed research methods and data collection techniques, the importance of theory is highlighted by evaluating the theoretical foundations and contributions of former studies. Since agile ISD is rooted in the IS as well as software engineering discipline, important outlets of both disciplines are included in the search process, resulting in 482 investigated papers. the findings show that quantitative studies and the theoretical underpinnings of agile ISD are lacking. Extreme programming is still the most researched agile ISD method, and more efforts on Scrum are needed. In consequence, multiple research gaps that need further research attention are identified.
In a previous work, we introduced a filtering for the Bin-Packing constraint based on a cardinality reasoning for each bin combined with a global cardinality constraint. We improve this filtering with an algorithm pro...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
In a previous work, we introduced a filtering for the Bin-Packing constraint based on a cardinality reasoning for each bin combined with a global cardinality constraint. We improve this filtering with an algorithm providing tighter bounds on the cardinality variables. We experiment it on the Balanced Academic Curriculum Problems demonstrating the benefits of the cardinality reasoning for such bin-packing problems.
暂无评论