Most earlier works in the area of wireless mesh network assume a single interface being equipped in each node. In this paper, we consider the next-generation wireless mesh networks in which each node may be equipped w...
详细信息
Most earlier works in the area of wireless mesh network assume a single interface being equipped in each node. In this paper, we consider the next-generation wireless mesh networks in which each node may be equipped with multiple radio interfaces, each capable of running in one of several modes, one of several channels, and each capable of supporting multiple modulations. For example, from off-the-shelf components, one can easily construct a mesh node with multiple IEEE 802.11a/b/g radio interfaces. Our goal is to address the resource planning and packet forwarding issues in such an environment. the proposed methodology is based on linear programming with network flow principles and radio channel access/interference models. Given a network topology, traffic requirements, and gateway capacities, we show how to allocate network interface cards and their channels to fully utilize channel bandwidths. the results can be used by a wireless Internet service provider to plan their networks under a hardware constraint so as to maximize their profits. To the best of our knowledge, this is the first work addressing resource planning in a wireless mesh network. Our numerical results show significant improvement in terms of aggregate network throughput with moderate network-layer fairness.
this article introduces the turtle++ library which combines constraint-based and imperative paradigms and enables in this way constraint imperative programming (CIP) with c++. Integrating CIP into c++ allows to exploi...
详细信息
We review the many different definitions of symmetry for constraint satisfaction problems (CSPs) that have appeared in the literature, and show that a symmetry can be defined in two fundamentally different ways: as an...
详细信息
We review the many different definitions of symmetry for constraint satisfaction problems (CSPs) that have appeared in the literature, and show that a symmetry can be defined in two fundamentally different ways: as an operation preserving the solutions of a CSP instance, or else as an operation preserving the constraints. We refer to these as solution symmetries and constraint symmetries. We define a constraint symmetry more precisely as an automorphism of a hypergraph associated with a CSP instance, the microstructure complement. We show that the solution symmetries of a CSP instance can also be obtained as the automorphisms of a related hypergraph, the k-ary nogood hypergraph and give examples to show that some instances have many more solution symmetries than constraint symmetries. Finally, we discuss the practical implications of these different notions of symmetry.
We review the many different definitions of symmetry for constraint satisfaction problems (CSPs) that have appeared in the literature, and show that a symmetry can be defined in two fundamentally different ways: as an...
详细信息
ISBN:
(纸本)3540292381
We review the many different definitions of symmetry for constraint satisfaction problems (CSPs) that have appeared in the literature, and show that a symmetry can be defined in two fundamentally different ways: as an operation preserving the solutions of a CSP instance, or else as an operation preserving the constraints. We refer to these as solution symmetries and constraint symmetries. We define a constraint symmetry more precisely as an automorphism of a hypergraph associated with a CSP instance, the microstructure complement. We show that the solution symmetries of a CSP instance can also be obtained as the automorphisms of a related hypergraph, the k-ary nogood hypergraph and give examples to show that some instances have many more solution symmetries than constraint symmetries. Finally, we discuss the practical implications of these different notions of symmetry.
A constraint is a relation with an active behavior. For a given relation, we propose to learn a representation adapted to this active behavior. It yields two contributions. the first is a generic metatechnique for cla...
详细信息
ISBN:
(纸本)3540292438
A constraint is a relation with an active behavior. For a given relation, we propose to learn a representation adapted to this active behavior. It yields two contributions. the first is a generic metatechnique for classifier improvement showing performances comparable to boosting. the second lies in the ability of using the learned concept in constraint-based decision or optimization problems. It opens a new way of integrating Machine Learning in Decision Support Systems.
constraintprogramming is rapidly becoming the technology of choice for modelling and solving complex combinatorial problems. However, users of this technology need significant expertise in order to model their proble...
详细信息
ISBN:
(纸本)3540292438
constraintprogramming is rapidly becoming the technology of choice for modelling and solving complex combinatorial problems. However, users of this technology need significant expertise in order to model their problems appropriately. the lack of availability of such expertise is a significant bottleneck to the broader uptake of constraint technology in the real world. We present a new SAT-based version space algorithm for acquiring constraint satisfaction problems from examples of solutions and non-solutions of a target problem. An important advantage is the ease with which domain-specific knowledge can be exploited using the new algorithm. Finally, we empirically demonstrate the algorithm and the effect of exploiting domain-specific knowledge on improving the quality of the acquired constraint network.
the generalization of the constraint satisfaction problem with universal quantifiers is a challenging PSPACE-complete problem, which is interesting theoretically and also relevant to solving other PSPACE problems aris...
详细信息
ISBN:
(纸本)3540292381
the generalization of the constraint satisfaction problem with universal quantifiers is a challenging PSPACE-complete problem, which is interesting theoretically and also relevant to solving other PSPACE problems arising in AI, such as reasoning with uncertainty, and multiplayer games. I define two new levels of consistency for QCSP, and give an algorithm to enforce consistency for one of these definitions. the algorithm is embedded in backtracking search, and tested empirically. the aims of this work are to increase the facilities available for modelling and to increase the power of constraint propagation for QCSPs. the work is motivated by examples from adversarial games.
Still-life is a challenging problem for CP techniques. We show how to use the global case constraint to construct ad-hoc constraints which can provide stronger propagation than existing CP models. We also demonstrate ...
详细信息
the annualinternational Trading Agent Competition-Supply Chain Management (TAC-SCM) game is based around the manufacture and supply of PCs. there are multiple agents in the game, scheduling production, competing for ...
详细信息
ISBN:
(纸本)3540292381
the annualinternational Trading Agent Competition-Supply Chain Management (TAC-SCM) game is based around the manufacture and supply of PCs. there are multiple agents in the game, scheduling production, competing for orders from customers and components from suppliers. A key decision to be made each day in the game is what offers should be made to customers. Each day, the agents receive a set of request for quotes (RFQ) from customers, agents respond with offers, and then the customers select the lowest bid. We have developed an agent to compete in the competition that combines constraint-based optimisation, reasoning with probabilities, and learning of market conditions in an attempt to determine what customer requests to bid on and what prices to bid. Our agent maintains prices that correspond to different probabilities of success in winning contracts, using an online learning approach. By keeping track of the ratio of offers accepted to those made, the prices can be updated iteratively to move closer to their target probability. this range of price/probability pairs is then used as input to a constraint model. For each request, the model chooses whether or not to bid, and selects a price from the range. these decisions are restricted by capacity and supply constraints. A capacity constraint ensures that we will be able to schedule any new orders we receive with existing orders such that the factory capacity for each day in the current horizon is not exceeded. the agents production ability is also subject to component availability, By ordering components in advance, we know the current amount of components available, and we also know how much of each component will be arriving at each clay. this allows us to add a constraint for availability of supplies. An objective function is specified that maximises our expected profit, where the profit on a request is calculated by subtracting from the selling price the cost of components together with late delivery penalties
For practical reasons, most scheduling problems are an abstraction of the real problem being solved. For example, when you plan your day, you schedule the activities which are critical;that is you schedule the activit...
详细信息
ISBN:
(纸本)3540292381
For practical reasons, most scheduling problems are an abstraction of the real problem being solved. For example, when you plan your day, you schedule the activities which are critical;that is you schedule the activities which are essential to the success of your day. So you may plan what time to leave the house to get to work, when to have meetings, how you share your vehicle with your spouse and so on. On the other hand, you probably do not consider the activities that are easy to arrange like brushing your teeth, going to the shops, making photocopies and other such tasks that can usually be accomplished whenever you have the time available. Scheduling all of these activities at once is often too complicated. Instead, a simpler schedule is produced by considering only the critical activities. However, if a schedule goes wrong, it is often because an activity turned out to be critical but was not scheduled. We typically learn which activities are critical by experience and create an abstract scheduling problem which includes all known critical activities. Instead of scheduling the non-critical activities we estimate their effects in the abstract scheduling problem. We are interested in automating this abstraction process for scheduling problems. In our approach, given a set of activities A to be scheduled1, we choose a subset of activities, critical(A), and create a simplified scheduling model which approximates the other activities non-critical(A) instead of scheduling them. We then search this abstract model for a good, if not optimal solution. A solution is a partial order schedule for activities in critical(A). this abstract solution is then extended to a solution the entire problem by inserting the remaining activities non-critical(A) into the schedule. While the approach reduces complexity by solving the problem in two stages it does so at a price. there is a risk that the good abstract solution will not produce a good solution to the entire problem. We know
暂无评论