The best lower bound for the Resource Constrained Project Scheduling Problem is currently based on the resolution of several large Linear Programs (Brucker & Knust, EJOR, 107: 272-288, 1998). In this paper, we sho...
详细信息
The best lower bound for the Resource Constrained Project Scheduling Problem is currently based on the resolution of several large Linear Programs (Brucker & Knust, EJOR, 107: 272-288, 1998). In this paper, we show that (1) intensive constraint propagation can be used to tighten the initial formulation of the linear programs and (2) we introduce several sets of valid cutting planes. These improvements allow us to "close" 16 new instances of the PSPLIB with 60 activities and to improve the best known lower bounds of 64 instances.
We address the automatic generation of timetables for non-commercial sport leagues. By example of table-tennis we stress the particularity of non-commercial leagues, namely the limited access to sport facilities and t...
详细信息
We address the automatic generation of timetables for non-commercial sport leagues. By example of table-tennis we stress the particularity of non-commercial leagues, namely the limited access to sport facilities and temporary non-availability of sportsmen. For this problem class we propose a Memetic Algorithm backed by a constraint propagation based heuristic. The order of variable instantiation for this heuristic is evolved adaptively by means of a co-evolutionary approach. (C) 2003 Elsevier B.V. All rights reserved.
This paper considers a generalisation of the classical RCPSP problem: the resource consumption of each task is continuously varying over time and the duration and the start of each task may vary within real intervals....
详细信息
This paper considers a generalisation of the classical RCPSP problem: the resource consumption of each task is continuously varying over time and the duration and the start of each task may vary within real intervals. A first contribution is a general model for describing the resource consumption of a task over time. This model is justified when considering continuously divisible resources. The second contribution is the computation of the compulsory part or core time of such a task. The compulsory part gives the task's resource consumption common to all feasible schedules. Hence, it can be used in a global resolution process such as constraint programming or branch and bound approaches. The presented polynomial algorithms use only two particular schedules of that task. (C) 2002 Elsevier B.V. All rights reserved.
constraint programming (CP) has been successful in a number of combinatorial search and discrete optimisation problems. Yet other more traditional approaches, such as Integer programming (IP), can still give a better ...
详细信息
constraint programming (CP) has been successful in a number of combinatorial search and discrete optimisation problems. Yet other more traditional approaches, such as Integer programming (IP), can still give a better performance on the same problem types. Central to IFS success is its reliance an a fast Linear programming (LP) solver providing solutions during the search to the corresponding relaxed problems. These solutions are used to guide the search within IP as well as a means of detecting infeasibility and integrality. This paper shows that there is scope also to include LP within the CP framework, in order to similarly guide the CP search. The problems examined here are one for which CP on its own had proved markedly inferior to IP. Hence a hybrid solver based on the CP search and using an LP solver is configured and run on these problems. The outcome shows that using the LP solver within the CP search is a valuable addition to the available search strategies. An improved performance over the CP-only strategies is obtained and, further, comparable results are obtained to those from IF. Overall, CP + LP can be considered as a more robust approach than either CP or IP on their own on a variety of combinatorial search problems.
This paper provides details of a successful application where the Column Generation algorithm was used to combine constraint programming and Linear programming. In the past, constraint programming and linear programmi...
详细信息
This paper provides details of a successful application where the Column Generation algorithm was used to combine constraint programming and Linear programming. In the past, constraint programming and linear programming were considered to be two competing technologies that solved similar types of problems. Both these technologies had their strengths and weaknesses. This paper shows that the two technologies can be combined together to extract the strengths of both these technologies. Details of a real-world application to optimize bus driver duties is given here. This system was developed by ILOG for a major software house in Japan using ILOG-Solver and ILOG-CPLEX, constraint programming and linear programming C/C++ libraries.
Ant Colony Optimisation algorithms perform competitively with other meta-heuristics for many types of optimisation problems, but unfortunately their performance does not always degrade gracefully when the problem cont...
详细信息
ISBN:
(纸本)3540226729
Ant Colony Optimisation algorithms perform competitively with other meta-heuristics for many types of optimisation problems, but unfortunately their performance does not always degrade gracefully when the problem contains hard constraints. Many industrially relevant problems, such as fleet routing, rostering and timetabling, are typically subject to hard constraints. A complementary technique for solving combinatorial optimisation problems is constraint programming (CP). CP techniques axe specialized for solving hard constraints, but they may be inefficient as an optimisation method if the feasible space is very large. A hybrid approach combining both techniques therefore holds the hope to combine these complementary advantages. The paper explores how such an integration can be achieved and presents a hybrid search method CPACS derived by embedding CP into ACS. We have tested CPACS on job scheduling problems. Initial benchmark results axe encouraging and suggest that CPACS has the biggest advantage over the individual methods for problems of medium tightness, where the constraints cause a highly fragmented but still very large search space.
We present a new technique for the generation of non-linear (algebraic) invariants of a program. Our technique uses the theory of ideals over polynomial rings to reduce the non-linear invariant generation problem to a...
详细信息
ISBN:
(纸本)9781581137293
We present a new technique for the generation of non-linear (algebraic) invariants of a program. Our technique uses the theory of ideals over polynomial rings to reduce the non-linear invariant generation problem to a numerical constraint solving problem. So far, the literature on invariant generation has been focussed on the construction of linear invariants for linear programs. Consequently, there has been little progress toward non-linear invariant generation. In this paper, we demonstrate a technique that encodes the conditions for a given template assertion being an invariant into a set of constraints, such that all the solutions to these constraints correspond to non-linear (algebraic) loop invariants of the program. We discuss some trade-offs between the completeness of the technique and the tractability of the constraint-solving problem generated. The application of the technique is demonstrated on a few examples.
A Non-binary constraint Satisfaction Problem (CSP) can be solved by converting the problem into an equivalent binary one and applying well-established binary CSP techniques. An alternative way is to use extended versi...
详细信息
ISBN:
(纸本)3540219374
A Non-binary constraint Satisfaction Problem (CSP) can be solved by converting the problem into an equivalent binary one and applying well-established binary CSP techniques. An alternative way is to use extended versions of binary techniques directly on the non-binary problem. There are two well-known computational methods in the literature for translating a non-binary CSP to an equivalent binary CSP;(i) the hidden variable encoding and (ii) the dual encoding. In this paper we make a theoretical and empirical study of arc consistency for the binary encodings. An arc consistency algorithm for the hidden variable encoding with optimal O(ekd(k)) worst-case time complexity is presented. This algorithm is compared theoretically and empirically to an optimal generalized arc consistency algorithm that operates on the non-binary representation. We also describe an arc consistency algorithm for the dual encoding with O(ekd(k)) worst-case complexity. This gives an O(d(k)) reduction compared to a generic arc consistency algorithm. Both theoretical and computational results show that the encodings are competitive with the non-binary representation for certain classes of non-binary CSPS.
The job sequencing problem for a single machine with sequence-dependent setups is solved using the constraint programming (CP) and mixed-integer programming (MIP) approaches. For the CP search, ten different variable ...
详细信息
ISBN:
(纸本)3540235264
The job sequencing problem for a single machine with sequence-dependent setups is solved using the constraint programming (CP) and mixed-integer programming (MIP) approaches. For the CP search, ten different variable and value ordering heuristics are tested using both the CP model and/or the combined model of the MIP and CP formulations. Some of these heuristics exploit problem specific data like setup cost and due date. Others rely on hybrid strategies that use the linear programming (LP) solver within the CP search or direct the search using the initial feasible solution obtained from the MIP model. A comparative analysis of the search heuristics and the CP and MIP solvers has been given with respect to the solution times. The research results indicate that the CP solver finds the optimum solution in a very short time compared to the MIP solver as the number of jobs to be scheduled increases.
One of the most appealing features of constraint programming is its rich constraint language for expressing combinatorial optimization problems. This paper demonstrates that traditional combinators from constraint pro...
详细信息
ISBN:
(纸本)3540232419
One of the most appealing features of constraint programming is its rich constraint language for expressing combinatorial optimization problems. This paper demonstrates that traditional combinators from constraint programming have natural counterparts for local search, although their underlying computational model is radically different. In particular, the paper shows that constraint combinators, such as logical and cardinality operators, reification, and first-class expressions can all be viewed as differentiable objects. These combinators naturally support elegant and efficient modelings, generic search procedures, and partial constraint satisfaction techniques for local search. Experimental results on a variety of applications demonstrate the expressiveness and the practicability of the combinators.
暂无评论