Although the Steel Mill Slab problem (prob 38 of CSPLib) has already been studied by the CP community, this approach is unfortunately not used anymore by steel producers since last century. Continuous casting is prefe...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Although the Steel Mill Slab problem (prob 38 of CSPLib) has already been studied by the CP community, this approach is unfortunately not used anymore by steel producers since last century. Continuous casting is preferred instead, allowing higher throughput and better steel quality. this paper presents a CP model related to scheduling of operations for steel making with continuous casting. Activities considered range from the extraction of iron in the furnace to its casting in continuous casters. We describe the problem, detail a CP scheduling model that is finally used to solve real-life instances of some of the PSI Metals' customers.
Recursively defined properties are ubiquitous. We present a proof method for establishing entailment G satisfies H of such properties G and H over a set of common variables. the main contribution is a particular proof...
详细信息
ISBN:
(纸本)9783540859574
Recursively defined properties are ubiquitous. We present a proof method for establishing entailment G satisfies H of such properties G and H over a set of common variables. the main contribution is a particular proof rule based intuitively upon the concept of coinduction. this rule allows the inductive step of assuming that tin entailment holds during the proof the entailment. In general, the proof method is based on an unfolding (and no folding) algorithm that reduces recursive definitions to a point where only constraint solving is necessary. the constraint-based proof obligation is then discharged with available solvers. the algorithm executes the proof-by a search-based method which automatically discovers the opportunity of applying induction instead of the user having to specify some induction schema, and which does not require any base case.
Flight routes are paths in a network, the nodes of which represent waypoints in a 3D space. A common approach to route planning is first to calculate a cheapest path in a 2D space, and then to optimize the flight cost...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
Flight routes are paths in a network, the nodes of which represent waypoints in a 3D space. A common approach to route planning is first to calculate a cheapest path in a 2D space, and then to optimize the flight cost in the third dimension. We focus on the problem of finding a cheapest paththrough a network describing the 2D projection of the 3D waypoints. In European airspaces, traffic flow is handled by heavily constraining the flight network. the constraints can have very diverse structures, among them a generalization of the forbidden pairs type. they invalidate the FIFO property, commonly assumed in shortest path problems. We formalize the problem and provide a framework for the description, representation and propagation of the constraints in path finding algorithms, best-first, and A* search. In addition, we study a lazy approach to deal withthe constraints. We conduct an experimental evaluation based on real-life data and conclude that our techniques for constraint propagation work best together with an iterative search approach, in which only constraints that are violated in previously found routes are introduced in the constraint set before the search is restarted.
Large neighborhood search (LNS) [25] is a framework that combines the expressiveness of constraintprogramming withthe efficiency of local search to solve combinatorial optimization problems. this paper introduces an...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
Large neighborhood search (LNS) [25] is a framework that combines the expressiveness of constraintprogramming withthe efficiency of local search to solve combinatorial optimization problems. this paper introduces an extension of LNS, called multi-objective LNS (MO-LNS), to solve multi-objective combinatorial optimization problems ubiquitous in practice. the idea of MO-LNS is to maintain a set of nondominated solutions rather than just one best-so-far solution. At each iteration, one of these solutions is selected, relaxed and optimized in order to strictly improve the hypervolume of the maintained set of nondominated solutions. We introduce modeling abstractions into the OscaR solver for MO-LNS and show experimentally the efficiency of this approach on various multi-objective combinatorial optimization problems.
the constraint paradigm provides powerful concepts to represent and solve different kinds of planning problems. Typically a large and conflicting set of restrictions, objectives and preferences has to be considered fo...
详细信息
ISBN:
(纸本)3540652248
the constraint paradigm provides powerful concepts to represent and solve different kinds of planning problems. Typically a large and conflicting set of restrictions, objectives and preferences has to be considered for real planning problems. We introduce a unified formalism - called Petri decision nets -for representation and implementation of complex CSP solution algorithms. the formalism enables the consideration of the problem structure as well as given objectives and the usage of problem specific heuristics or expert knowledge. It is based on the fundamental assumption that designing CSP solution algorithms means designing decision networks.
the protein structure prediction problem is one of the most (if not the most) important problem in computational biology. this problem consists of finding the conformation of a protein (i.e., a sequence of amino-acids...
详细信息
ISBN:
(纸本)3540652248
the protein structure prediction problem is one of the most (if not the most) important problem in computational biology. this problem consists of finding the conformation of a protein (i.e., a sequence of amino-acids) with minimal energy. Because of the complexity of this problem, simplified models like Dill's HP-lattice model [12] have become a major tool for investigating general properties of protein folding. Even for this simplified model, the structure prediction problem has been shown to be NP-complete [3, 5]. We describe a constraint formulation of the HP-model structure prediction problem, present the basic constraints and search strategy. We then introduce a novel, general technique for excluding geometrical symmetries in constraintprogramming. To our knowledge, this is the first general and declarative technique for excluding symmetries in constraintprogrammingthat can be added to an existing implementation. Finally, we describe a new lower bound on the energy of an HP-protein. Both techniques yield an efficient pruning of the search tree.
the multibin_packing constraint captures a fundamental substructure of many assignment problems, where a set of items, each with a fixed number of dimensions, must be assigned to a number of bins with limited capaciti...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
the multibin_packing constraint captures a fundamental substructure of many assignment problems, where a set of items, each with a fixed number of dimensions, must be assigned to a number of bins with limited capacities. In this work we propose a simple decomposition for multibin_packing that uses a bin packing constraint for each dimension, a set of all different constraints automatically derived from a conflict graph, plus two alternative symmetry breaking approaches. Despite its simplicity, the proposed decomposition is very effective on a number of instances recently proposed in the literature.
Resource Constrained Project;Scheduling Problem is a very important problem in project management, manufacturing and resource optimization. We focus on a variant of RCPSP with time lags and variable activity durations...
详细信息
ISBN:
(纸本)9783642042430
Resource Constrained Project;Scheduling Problem is a very important problem in project management, manufacturing and resource optimization. We focus on a variant of RCPSP with time lags and variable activity durations. the solving approach is based on Precedence constraint Posting that adds new precedence constraints to the original project graph so that all resource Conflicts are solved and a consisteut assignment of start times can be computed for whatever combination of activity durations. We propose a novel method for computing resource conflicts based on the minimum flow on the resource graph and we use it in an efficient complete search strategy. We experiment the approach on instances coming from the scheduling of parallel applications on multi processor systems on chip.
Most work on constraint satisfaction problems (CSP) starts with a standard problem definition and focuses on algorithms for finding solutions. However, formulating a CSP so that it can be solved by such methods is oft...
详细信息
ISBN:
(纸本)3540666265
Most work on constraint satisfaction problems (CSP) starts with a standard problem definition and focuses on algorithms for finding solutions. However, formulating a CSP so that it can be solved by such methods is often a difficult problem in itself. In this paper, we consider the problem of routing in networks, an important problem in communication networks. It is as an example of a problem where a CSP formulation would lead to unmanageable solution complexity. We show how an abstraction technique results in tractable formulations and makes the machinery of CSP applicable to this problem.
One promising trend in digital system integration consists of boosting on-chip communication performance by means of silicon photonics, thus materializing the so-called Optical Networkson- Chip. Among them, wavelength...
详细信息
One promising trend in digital system integration consists of boosting on-chip communication performance by means of silicon photonics, thus materializing the so-called Optical Networkson- Chip. Among them, wavelength routing can be used to route a signal to destination by univocally associating a routing path to the wavelength of the optical carrier. Such wavelengths should be chosen so to minimize interferences among optical channels and to avoid routing faults. As a result, physical parameter selection of such networks requires the solution of complex constrained optimization problems. In previous work, published in the proceedings of the internationalconference on Computer-Aided Design, we proposed and solved the problem of computing the maximum parallelism obtainable in the communication between any two endpoints while avoiding misrouting of optical signals. the underlying technology, only quickly mentioned in that paper, is Answer Set programming. In this work, we detail the Answer Set programming approach we used to solve such problem. Another important design issue is to select the wavelengths of optical carriers such that they are spread across the available spectrum, in order to reduce the likelihood that, due to imperfections in the manufacturing process, unintended routing faults arise. We show how to address such problem in constraint Logic programming on Finite Domains.
暂无评论