the typical constraint store transmits a limited amount of information because it consists only of variable domains. We propose a richer constraint store in the form of a limited-width multivalued decision diagram (MD...
详细信息
ISBN:
(纸本)9783540749691
the typical constraint store transmits a limited amount of information because it consists only of variable domains. We propose a richer constraint store in the form of a limited-width multivalued decision diagram (MDD). It reduces to a traditional domain store when the maximum width is one but allows greater pruning of the search tree for larger widths. MDD propagation algorithms can be developed to exploit the structure of particular constraints, much as is done for domain filtering algorithms. We propose specialized propagation algorithms for alldiff and inequality constraints. Preliminary experiments show that MDD propagation solves multiple alldiff problems an order of magnitude more rapidly than traditional domain propagation. It also significantly reduces the search tree for inequality problems, but additional research is needed to reduce the computation time.
this paper presents a constraintprogramming model and search strategy to formulate and solve staff scheduling problems in health care. this is a well-studied problem for which many different approaches have been deve...
详细信息
ISBN:
(纸本)3540202021
this paper presents a constraintprogramming model and search strategy to formulate and solve staff scheduling problems in health care. this is a well-studied problem for which many different approaches have been developed over the years but it remains a challenge to successfully apply any given instance of a method to the various contexts encountered. We show how the main categories of rules involved may be expressed using global constraints. We describe a modular architecture for heuristic search. the resulting flexible and rather general constraintprogramming approach is evaluated on benchmark problems from different hospitals and for different types of personnel.
Most distributed constraint optimization problems assume the overall objective function to be the "utilitarian social welfare", i.e., a sum of several utility functions, belonging to different agents. this a...
详细信息
ISBN:
(纸本)9783030300487
Most distributed constraint optimization problems assume the overall objective function to be the "utilitarian social welfare", i.e., a sum of several utility functions, belonging to different agents. this also holds for the most popular soft constraint formalisms, cost function networks and weighted constraints. While, in theory, this model is sound, it is susceptible to manipulation and resulting bias in practice. Even without malevolent intentions, bias can result from the way orderings over solutions are transformed into numerical values or normalized. Alternatively, preferences can be aggregated directly using the tools of social choice theory to discourage manipulations and practically reduce unwanted bias. Several common voting functions can be implemented on top of constraint modeling languages through incremental search and suitable improvement predicates. We demonstrate that our approach, in particular Condorcet voting, can undo bias which is shown on two real-life-inspired case studies using the soft constraint extension MiniBrass on top of MiniZinc.
Optimal planning with respect to learned neural network (NN) models in continuous action and state spaces using mixed-integer linear programming (MILP) is a challenging task for branch-and-bound solvers due to the poo...
详细信息
ISBN:
(纸本)9783030300487
Optimal planning with respect to learned neural network (NN) models in continuous action and state spaces using mixed-integer linear programming (MILP) is a challenging task for branch-and-bound solvers due to the poor linear relaxation of the underlying MILP model. For a given set of features, potential heuristics provide an efficient framework for computing bounds on cost (reward) functions. In this paper, we model the problem of finding optimal potential bounds for learned NN models as a bilevel program, and solve it using a novel finite-time constraint generation algorithm. We then strengthen the linear relaxation of the underlying MILP model by introducing constraints to bound the reward function based on the precomputed reward potentials. Experimentally, we show that our algorithm efficiently computes reward potentials for learned NN models, and that the overhead of computing reward potentials is justified by the overall strengthening of the underlying MILP model for the task of planning over long horizons.
this book constitutes the proceedings of the 25thinternationalconference on principles and practice of constraintprogramming, cp 2019, held in Stamford, CT, USA, France, in September/October 2019.
ISBN:
(数字)9783030300487
ISBN:
(纸本)9783030300470
this book constitutes the proceedings of the 25thinternationalconference on principles and practice of constraintprogramming, cp 2019, held in Stamford, CT, USA, France, in September/October 2019.
the 13thinternationalconference on principles and practice of constraintprogramming (cp 2007) was held in Providence, RI, USA, September 23–27, 2007, in conjunction withthe internationalconference on Automated P...
详细信息
ISBN:
(数字)9783540749707
ISBN:
(纸本)9783540749691
the 13thinternationalconference on principles and practice of constraintprogramming (cp 2007) was held in Providence, RI, USA, September 23–27, 2007, in conjunction withthe internationalconference on Automated Pl- ning and Scheduling (ICAPS). Held annually, the cpconference series is the premier internationalconference on constraintprogramming. the conference focuses on all aspects of computing withconstraints. the cpconference - ries is organized by the Association for constraintprogramming (Acp). - formation about the conferences in the series can be found on the Web at http://www. cs. ualberta. ca/~ai/cp/. Information about Acp can be found athttp://www. a4cp. org/. cp 2007 launched two calls for contributions: a call for research papers, describing novel contributions in the ?eld, and a call for application papers, describing applications of constraint technology in the industrial world. the research track received 143 submissions and the application track received 22 submissions. Research papers were reviewed under a double-blind scheme. they received three reviews that the authors had the opportunity to see and to react tobeforethepapersandtheirreviewswerediscussedextensivelybythemembers of the ProgramCommittee. Application papers werereviewedby a separate- plication Committee. the Program Committee and the Application Committee then selected 43 researchpapers and 9 application papers to be published in full inthe proceedings,andanadditional14researchpapersto be publishedas short papers. the full papers were presented at the conference in two parallel tracks and the short papers were presented in a poster session.
We propose two new asynchronous algorithms for solving Distributed constraint Satisfaction Problems (DisCSPs). the first algorithm, AFC-ng, is a nogood-based version of Asynchronous Forward Checking (AFC). the second ...
详细信息
ISBN:
(纸本)9783642042430
We propose two new asynchronous algorithms for solving Distributed constraint Satisfaction Problems (DisCSPs). the first algorithm, AFC-ng, is a nogood-based version of Asynchronous Forward Checking (AFC). the second algorithm, Asynchronous Inter-Level Forward-Checking (AILFC), is based oil the AFC-ng algorithm and is performed oil a pseudo-tree ordering of the constraint graph. AFC-ng and AILFC only need polynomial space. We compare the performance of these algorithms with other DisCSP algorithms on random DisCSPs in two kinds of communication environments: Fast communication and slow communication. Our experiment,, show that AFC-ng improves oil AFC and that AILFC Outperforms all compared algorithms in communication load.
this paper describes a new approach for solving disjunctive temporal problems such as the open shop and job shop scheduling domains. Much previous research in systematic search approaches for these problems has focuse...
详细信息
ISBN:
(纸本)9783642042430
this paper describes a new approach for solving disjunctive temporal problems such as the open shop and job shop scheduling domains. Much previous research in systematic search approaches for these problems has focused oil developing problem specific constraint propagators and ordering heuristics. Indeed, the common belief is that many of these problems are too difficult to solve without such domain specific models. We introduce a simple constraint model that combines a generic adaptive heuristic with naive propagation, and show that it often outperforms state-of-the-art solvers for both open shop and job shop problems.
Instruction scheduling is one of the most important steps for improving the performance of object code produced by a compiler. the local instruction scheduling problem is to find a minimum length instruction schedule ...
详细信息
Accurately estimating the distribution of solutions to a problem, should such solutions exist, provides efficient search heuristics. the purpose of this paper is to propose new ways of computing such estimates, with d...
详细信息
ISBN:
(纸本)9783642042430
Accurately estimating the distribution of solutions to a problem, should such solutions exist, provides efficient search heuristics. the purpose of this paper is to propose new ways of computing such estimates, with different degrees of accuracy and complexity. We build oil the Expectation-Maximizatiou Belief-Propagation (EMPB) framework proposed by Hsu et al. to solve constraint Satisfaction Problems (CSPs). We propose two general approaches within the EMBP framework: we firstly derive update rules at;the constraint level while enforcing domain consistency and then derive update rules globally, at the problem level. the contribution of this paper is two-fold: first, we derive new generic update rules suited to tackle ally CSP;second, we propose all efficient EMP-inspired approach, thereby improving this method and making it competitive withthe state of the art. We evaluate these approaches experimentally and demonstrate their effectiveness.
暂无评论