In this paper, we propose a challenging research direction for constraint programming and optimization techniques in general. We address problems where decisions to be taken affect and are affected by complex systems,...
详细信息
In this paper, we propose a challenging research direction for constraint programming and optimization techniques in general. We address problems where decisions to be taken affect and are affected by complex systems, which exhibit phenomena emerging from a collection of interacting objects, capable to self organize and to adapt their behaviour according to their history and feedback. Such systems are unfortunately impervious to modeling efforts via state-of-the-art combinatorial optimization techniques. We provide some hints on approaches to connect and integrate decision making and optimization technology with complex systems via machine learning, game theory and mechanism design. In the first case, the aim is to extract modeling components to express the relation between global decisions and observables emerging from the real system, or from an accurate predictive model (e.g. a simulator). In the second case, the idea is to exploit game theory, mechanism design and distributed decision making to drive the process toward realistic equilibrium points avoiding globally optimal, but unrealistic, configurations. We conclude by observing how dealing with the complexity of the considered problems will require to greatly extend the capabilities of state of the art solvers: in this context, we identify some key issues and highlight future research directions.
This paper addresses mapping of streaming applications (such as MPEG) on multiprocessor platforms with time-division-multiplexed network-on-chip. In particular, we solve processor selection, path selection and router ...
详细信息
This paper addresses mapping of streaming applications (such as MPEG) on multiprocessor platforms with time-division-multiplexed network-on-chip. In particular, we solve processor selection, path selection and router configuration problems. Given the complexity of these problems, state of the art approaches in this area largely rely on greedy heuristics, which do not guarantee optimality. Our approach is based on a constraint programming formulation that merges a number of steps, usually tackled in sequence in classic approaches. Thus, our method has the potential of finding optimal solutions with respect to resource usage under throughput constraints. The experimental evaluation presented in here shows that our approach is capable of exploring a range of solutions while giving the designer the opportunity to emphasize the importance of various design metrics. (C) 2014 Elsevier Ltd. All rights reserved.
Technology for combinatorial optimization is rapidly changing, and as the size and scope of problems that can be solved steadily increases, the complexity of the underlying technology is growing. We foresee a huge dem...
详细信息
Technology for combinatorial optimization is rapidly changing, and as the size and scope of problems that can be solved steadily increases, the complexity of the underlying technology is growing. We foresee a huge demand for both the simplification of use of combinatorial optimization technology (so called "model and run" capabilities), as well as increasing need for the ability to quickly build complex hybrid solutions. These demands will place new emphasis on universal modeling languages and model transformation capabilities, as well as flexible and high level ways of specifying hybrid solutions. These changes put constraint programming in an ideal position since: constraint programming has the most high-level view of problems to begin with so we can ease modeling difficulties;and since constraint programming is an integrative technology, we have already spent considerable effort in making different solving technologies work together seamlessly. In this position paper we outline some of the key challenges and important research directions we foresee for optimization technology,.
constraint programming (CP) is a proven set of techniques for solving complex combinatorial problems from a range of disciplines. The problem is specified as a set of decision variables (with finite domains) and const...
详细信息
constraint programming (CP) is a proven set of techniques for solving complex combinatorial problems from a range of disciplines. The problem is specified as a set of decision variables (with finite domains) and constraints linking the variables. Local reasoning (propagation) on the constraints is central to CP. Many constraints have efficient constraint-specific propagation algorithms. In this work, we generate custom propagators for constraints. These custom propagators can be very efficient, even approaching (and in some cases exceeding) the efficiency of hand-optimised propagators. Given an arbitrary constraint, we show how to generate a custom propagator that establishes GAC in small polynomial time. This is done by precomputing the propagation that would be performed on every relevant subdomain. The number of relevant subdomains, and therefore the size of the generated propagator, is potentially exponential in the number and domain size of the constrained variables. The limiting factor of our approach is the size of the generated propagators. We investigate symmetry as a means of reducing that size. We exploit the symmetries of the constraint to merge symmetric parts of the generated propagator. This extends the reach of our approach to somewhat larger constraints, with a small run-time penalty. Our experimental results show that, compared with optimised implementations of the table constraint, our techniques can lead to an order of magnitude speedup. Propagation is so fast that the generated propagators compare well with hand-written carefully optimised propagators for the same constraints, and the time taken to generate a propagator is more than repaid. (C) 2014 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license
Bilevel optimization problems involve two decision makers who make their choices sequentially, either one according to its own objective function. Many problems arising in economy and management science can be modeled...
详细信息
Planning research is recently concerned with the resolution of more realistic problems as evidenced in the many works and new extensions to the Planning Domain Definition Language (PDDL) to better approximate real pro...
详细信息
Planning research is recently concerned with the resolution of more realistic problems as evidenced in the many works and new extensions to the Planning Domain Definition Language (PDDL) to better approximate real problems. Researchers' works to push planning algorithms and capture more complex domains share an essential ingredient, namely the incorporation of new types of constraints. Adding constraints seems to be the way of approximating real problems: these constraints represent the duration of tasks, temporal and resource constraints, deadlines, soft constraints, etc., i.e. features that have been traditionally associated to the area of scheduling. This desired expressiveness can be achieved by augmenting the planning reasoning capabilities, at the cost of slightly deviating the planning process from its traditional implicit purpose, that is finding the causal structure of the plan. However, the resolution of complex domains with a great variety of different constraints may involve as much planning effort as scheduling effort (and perhaps the latter being more prominent in many problems). For this reason, in this paper we present a general approach to model those problems under a constraint programming formulation which allows us to represent and handle a wide range of constraints. Our work is based on the original model of CPT, an optimal temporal planner, and it extends the CPT's formulation to deal with more expressive constraints. We will show that our general formulation can be used for planning and/or scheduling, from scheduling a given complete plan to generating the whole plan from scratch. However, our contribution is not a new planner but a constraint programming formulation for representing highly-constrained planning + scheduling problems.
The paper presents a concept and implementation of a novel approach to the modelling and solving of the Two-Echelon Capacitated Vehicle Routing Problem (2E-CVRP). Multi-echelon distribution systems are quite common in...
详细信息
The paper presents a concept and implementation of a novel approach to the modelling and solving of the Two-Echelon Capacitated Vehicle Routing Problem (2E-CVRP). Multi-echelon distribution systems are quite common in supply-chain and logistic systems. Two environments, mathematical programming (MP) and constraint logic programming, in which constraints are treated in different ways and different methods are implemented, were combined to use the strengths of both. The proposed approach is particularly important for the decision models with an objective function and many discrete decision variables added up in multiple constraints. The 2E-CVRP is an extension of the classical Capacitated Vehicle Routing Problem (CVRP) where the delivery depot-customers pass through intermediate depots (called satellites). The 2E-CVRP was selected as a known and documented example for verification and evaluation of the effectiveness of the proposed approach. The presented approach will be compared with classical MP on the same data-sets in computational tests. The proposed approach will be used also for extensions of the modelled problem beyond the standard.
This paper considers a nurse rostering problem from a ward at a Danish hospital. The problem is highly constrained and comprises a large set of different constraints. A branch-and-price method for solving the problem ...
详细信息
This paper considers a nurse rostering problem from a ward at a Danish hospital. The problem is highly constrained and comprises a large set of different constraints. A branch-and-price method for solving the problem exactly is proposed. The master problem is to assign schedules to the nurses, and its linear relaxation is solved by means of column generation. The pricing sub-problem is to generate feasible schedules for the nurses and-as a couple of different constraints including several special Danish regulations have to be observed-is solved by constraint programming. A number of specific algorithms for handling these constraints are proposed. The method is very flexible regarding the rules a schedule should comply with, which is a key concern when creating solution methods for nurse rostering problems. Computational tests show that optimal solutions can be found for instances with a two weeks planning period in a reasonable amount of computing time.
A particularly difficult class of scheduling and routing problems involves an objective that is a sum of time-varying action costs, which increases the size and complexity of such problems. Solve-and-improve approache...
详细信息
A particularly difficult class of scheduling and routing problems involves an objective that is a sum of time-varying action costs, which increases the size and complexity of such problems. Solve-and-improve approaches, which find an initial solution for a simplified model and improve it using a cost function, and mixed integer programming (MIP) are often used for solving such problems. However, constraint programming (CP), particularly with lazy clause generation (LCG), has been found to be faster than MIP for some scheduling problems with time-varying action costs. In this paper, we compare CP and LCG against a solve-and-improve approach for two recently introduced problems in the area of maritime logistics with time-varying action costs: the liner shipping fleet repositioning problem (LSFRP) and the bulk port cargo throughput optimisation problem (BPCTOP). We present a novel CP model for the LSFRP, which is faster than all previous methods and outperforms a simplified automated planning model without time-varying costs. We show that a LCG solver is faster for solving theBPCTOP than a standard finite domainCP solverwith a simplified model. We find that CP and LCG are effective methods for solving problems with time-dependent task costs and are worth investigating for other scheduling and routing problems that are currently being solved usingMIP or solve-and-improve approaches, even when customized global constraints are not available. We also investigate a novel approach to solving the BPCTOP-converting the problem into a vehicle routing problem (VRP) and solving using an existing VRP solver.
Model reduction is a central topic in systems biology and dynamical systems theory, for reducing the complexity of detailed models, finding important parameters, and developing multi-scale models for instance. While s...
详细信息
Model reduction is a central topic in systems biology and dynamical systems theory, for reducing the complexity of detailed models, finding important parameters, and developing multi-scale models for instance. While singular perturbation theory is a standard mathematical tool to analyze the different time scales of a dynamical system and decompose the system accordingly, tropical methods provide a simple algebraic framework to perform these analyses systematically in polynomial systems. The crux of these methods is in the computation of tropical equilibrations. In this paper we show that constraint-based methods, using reified constraints for expressing the equilibration conditions, make it possible to numerically solve non-linear tropical equilibration problems, out of reach of standard computation methods. We illustrate this approach first with the detailed reduction of a simple biochemical mechanism, the Michaelis-Menten enzymatic reaction model, and second, with large-scale performance figures obtained on the http://*** repository.
暂无评论