The proceedings contain 55 papers. The special focus in this conference is on Technical Track, Application Track, Computational Sustainability Track, cp, Biology Track, Music Track, Preference, Social Choice, Optimiza...
ISBN:
(纸本)9783319449524
The proceedings contain 55 papers. The special focus in this conference is on Technical Track, Application Track, Computational Sustainability Track, cp, Biology Track, Music Track, Preference, Social Choice, Optimization Track, Testing and Verification Track. The topics include: Exploiting short supports for improved encoding of arbitrary constraints into SAT;an adaptive parallel SAT solver;improved linearization of constraintprogramming models;impact of SAT-based preprocessing on core-guided MaxSAT solving;multiobjective optimization by decision diagrams;dependency schemes in QBF calculi;the multirate resource constraint;the dichotomy for conservative constraint satisfaction is polynomially decidable;the vertex cover constraint;extending broken triangles and enhanced value-merging;a bounded path propagator on directed graphs;interval constraints with learning: application to air traffic control;backdoors to tractable valued CSP;monte-carlo tree search for the maximum satisfiability problem;on finding minimum satisfying assignments;towards a dynamic decomposition of CSPs with separators of bounded size;a global constraint for closed frequent pattern mining;parallel strategies selection;learning parameters for the sequence constraint from solutions;explaining producer/consumer constraints;learning from learning solvers;on incremental core-guided MaxSAT solving;an implementation of MIP andcp for interactive soccer queries;solving a supply-delivery scheduling problem with constraintprogramming;availability optimization in cloud-based in-memory data grids;constraining redundancy to improve protein docking;finding alternative musical scales;morphing between stable matching problems;the power of propagation: when GAC is enough and AHP based portfolio selection with risk preference modeling.
Considerable effort in constraintprogramming has focused on the development of efficient propagators for individual constraints. In this paper, we consider the combined power of such propagators when applied to colle...
详细信息
Considerable effort in constraintprogramming has focused on the development of efficient propagators for individual constraints. In this paper, we consider the combined power of such propagators when applied to collections of more than one constraint. In particular we identify classes of constraint problems where such propagators can decide the existence of a solution on their own, without the need for any additional search. Sporadic examples of such classes have previously been identified, including classes based on restricting the structure of the problem, restricting the constraint types, and some hybrid examples. However, there has previously been no unifying approach which characterises all of these classes: structural, language-based and hybrid. In this paper we develop such a unifying approach and embed all the known classes into a common framework. We then use this framework to identify a further class of problems that can be solved by propagation alone.
The payload of communications satellites must go through a series of tests to assert their ability to survive in space. Each test involves some equipment of the payload to be active, which has an impact on the tempera...
详细信息
The payload of communications satellites must go through a series of tests to assert their ability to survive in space. Each test involves some equipment of the payload to be active, which has an impact on the temperature of the payload. Sequencing these tests in a way that ensures the thermal stability of the payload and minimizes the overall duration of the test campaign is a very important objective for satellite manufacturers. The problem can be decomposed in two sub-problems corresponding to two objectives: First, the number of distinct configurations necessary to run the tests must be minimized. This can be modeled as packing the tests into configurations, and we introduce a set of implied constraints to improve the lower bound of the model. Second, tests must be sequenced so that the number of times an equipment unit has to be switched on or off is minimized. We model this aspect using the constraint Switch, where a buffer with limited capacity represents the currently active equipment units, and we introduce an improvement of the propagation algorithm for this constraint. We then introduce a search strategy in which we sequentially solve the sub-problems (packing and sequencing). Experiments conducted on real and random instances show the respective interest of our contributions.
The Hospitals / Residents problem with Couples (hrc) models the allocation of intending junior doctors to hospitals where couples are allowed to submit joint preference lists over pairs of (typically geographically cl...
详细信息
The Hospitals / Residents problem with Couples (hrc) models the allocation of intending junior doctors to hospitals where couples are allowed to submit joint preference lists over pairs of (typically geographically close) hospitals. It is known that a stable matching need not exist, so we consider min bp hrc, the problem of finding a matching that admits the minimum number of blocking pairs (i.e., is "as stable as possible"). We show that this problem is NP-hard and difficult to approximate even in the highly restricted case that each couple finds only one hospital pair acceptable. However if we further assume that the preference list of each single resident and hospital is of length at most 2, we give a polynomial-time algorithm for this case. We then present the first Integer programming (IP) andconstraintprogramming (cp) models for min bp hrc. Finally, we discuss an empirical evaluation of these models applied to randomly-generated instances of min bp hrc. We find that on average, the cp model is about 1.15 times faster than the IP model, and when presolving is applied to the cp model, it is on average 8.14 times faster. We further observe that the number of blocking pairs admitted by a solution is very small, i.e., usually at most 1, and never more than 2, for the (28,000) instances considered.
Optimal power flow (OPF) is the central optimization problem in electric power grids. Although solved routinely in the course of power grid operations, it is known to be strongly NP-hard in general, and weakly NP-hard...
详细信息
Optimal power flow (OPF) is the central optimization problem in electric power grids. Although solved routinely in the course of power grid operations, it is known to be strongly NP-hard in general, and weakly NP-hard over tree networks. In this paper, we formulate the optimal power flow problem over tree networks as an inference problem over a tree-structured graphical model where the nodal variables are low-dimensional vectors. We adapt the standard dynamic programming algorithm for inference over a tree-structured graphical model to the OPF problem. Combining this with an interval discretization of the nodal variables, we develop an approximation algorithm for the OPF problem. Further, we use techniques from constraintprogramming (cp) to perform interval computations and adaptive bound propagation to obtain practically efficient algorithms. Compared to previous algorithms that solve OPF with optimality guarantees using convex relaxations, our approach is able to work for arbitrary tree-structured distribution networks and handle mixed-integer optimization problems. Further, it can be implemented in a distributed message-passing fashion that is scalable and is suitable for "smart grid" applications like control of distributed energy resources. Numerical evaluations on several benchmark networks show that practical OPF problems can be solved effectively using this approach.
Considerable effort in constraintprogramming has focused on the development of efficient propagators for individual constraints. In this paper, we consider the combined power of such propagators when applied to colle...
详细信息
ISBN:
(纸本)9783319449524
Considerable effort in constraintprogramming has focused on the development of efficient propagators for individual constraints. In this paper, we consider the combined power of such propagators when applied to collections of more than one constraint. In particular we identify classes of constraint problems where such propagators can decide the existence of a solution on their own, without the need for any additional search. Sporadic examples of such classes have previously been identified, including classes based on restricting the structure of the problem, restricting the constraint types, and some hybrid examples. However, there has previously been no unifying approach which characterises all of these classes: structural, language-based and hybrid. In this paper we develop such a unifying approach and embed all the known classes into a common framework. We then use this framework to identify a further class of problems that can be solved by propagation alone.
The Hospitals / Residents problem with Couples (hrc) models the allocation of intending junior doctors to hospitals where couples are allowed to submit joint preference lists over pairs of (typically geographically cl...
详细信息
ISBN:
(纸本)9783319449524
The Hospitals / Residents problem with Couples (hrc) models the allocation of intending junior doctors to hospitals where couples are allowed to submit joint preference lists over pairs of (typically geographically close) hospitals. It is known that a stable matching need not exist, so we consider min bp hrc, the problem of finding a matching that admits the minimum number of blocking pairs (i.e., is "as stable as possible"). We show that this problem is NP-hard and difficult to approximate even in the highly restricted case that each couple finds only one hospital pair acceptable. However if we further assume that the preference list of each single resident and hospital is of length at most 2, we give a polynomial-time algorithm for this case. We then present the first Integer programming (IP) andconstraintprogramming (cp) models for min bp hrc. Finally, we discuss an empirical evaluation of these models applied to randomly-generated instances of min bp hrc. We find that on average, the cp model is about 1.15 times faster than the IP model, and when presolving is applied to the cp model, it is on average 8.14 times faster. We further observe that the number of blocking pairs admitted by a solution is very small, i.e., usually at most 1, and never more than 2, for the (28,000) instances considered.
We examine Boolean binary weighted constraint satisfaction problems and derive sufficient conditions for when certain linear programming (LP) relaxations are guaranteed to return an integer solution, in which case the...
详细信息
In this work we investigate the application of optimization-based scheduling technologies to two mobile robot task planning problems. We develop and apply mixed-integer programming (MIP) andconstraintprogramming (cp...
详细信息
Symmetries can be broken statically or dynamically. Advantages of dynamic symmetry breaking methods include ability to break symmetries of arbitrary kinds and compatibility with variable and value heuristics. When con...
详细信息
暂无评论