Parallel constraint programming (CP) solvers typically split the search space in disjoint subspaces, and run solvers independently on these. This may induce significant overhead when solving optimization problems. Par...
详细信息
ISBN:
(数字)9783319339542
ISBN:
(纸本)9783319339542;9783319339535
Parallel constraint programming (CP) solvers typically split the search space in disjoint subspaces, and run solvers independently on these. This may induce significant overhead when solving optimization problems. Parallel Boolean Satisfiability (SAT) solvers typically run a portfolio of solvers, all solving the same problem but sharing some limited learnt clause information. In this paper we consider parallelizing a lazy clause generation (LCG) constraint programming solver, which is a constraint programming solver with learning. Since it is both a kind of CP solver and a kind of SAT solver it is not clear which approach to parallelization is likely to be most effective. We give examples of very different kinds of optimization problems we wish to parallelize and show that a hybrid approach to parallelization can provide a robust and high performing parallel LCG solver.
We consider a steelmaking-continuous casting (SCC) scheduling problem in the steel industry, which is a variant of the hybrid flow shop scheduling problem subject to practical constraints. Recently, Hong et al. [Hong,...
详细信息
ISBN:
(纸本)9783031332708;9783031332715
We consider a steelmaking-continuous casting (SCC) scheduling problem in the steel industry, which is a variant of the hybrid flow shop scheduling problem subject to practical constraints. Recently, Hong et al. [Hong, J., Moon, K., Lee, K., Lee, K., Pinedo, M.L., International Journal of Production Research 60(2), 623-643 (2022)] developed an algorithm, called Iterated Greedy Matheuristic (IGM), in which a Mixed Integer programming (MIP) model was proposed and its sub-problems are iteratively solved to improve the solution. We propose a new constraint programming (CP) formulation for the SCC scheduling problem and develop an algorithm, called Iterated Greedy CP (IGC), which uses the framework of IGM but replaces the MIP model with our CP model. When we solve the CP subproblems iteratively, we also refine them by adding appropriate constraints, reducing the domains of the variables, and giving the variables hints derived from the current solution. From computational experiments in various settings, we show that IGC implemented with an open-source CP solver can be competitive with IGM running on a commercial MIP solver.
This paper concerns guarantees on system performance through Service Level Agreement (SLA) compliance and focuses on devising energy aware resource management techniques based on Dynamic Voltage and Frequency Scaling ...
详细信息
ISBN:
(纸本)9781450341479
This paper concerns guarantees on system performance through Service Level Agreement (SLA) compliance and focuses on devising energy aware resource management techniques based on Dynamic Voltage and Frequency Scaling (DVFS) used by resource management middleware in clouds that handle MapReduce jobs. This research formulates the resource management problem as an optimization problem using constraint programming (CP). Experimental results presented in the paper demonstrate the effectiveness of the technique.
This paper aims at solving a nonconvex mixed integer nonlinear programming (MINLP) model used to solve a refinery crude-oil operations scheduling problem. The, model is mostly linear but contains bilinear products of ...
详细信息
ISBN:
(纸本)9783642019289
This paper aims at solving a nonconvex mixed integer nonlinear programming (MINLP) model used to solve a refinery crude-oil operations scheduling problem. The, model is mostly linear but contains bilinear products of continuous variables in the objective function. It is possible to define a linear relaxation of the model leading to a weak bound on the objective value of the optimal solution. A typical method to circumvent this issue;is to discretize the continuous space and to use linear relaxation constraints based on variables lower and upper bounds (e.g. McCormick convex envelopes) on each subdivision of the continuous space. This work explores another approach involving constraint programming (CP). The idea is to use all additional CP model which is used to tighten the bounds of the continuous variables involved in bilinear terms and then generate cuts based on McCormick convex envelopes. These cuts are then added to the mixed integer linear program (MILP) during the search leading to a tighter linear relaxation of the MINLP. Results show large reductions of the optimality gap of a two step MILP-NLP solution method due to the tighter linear relaxation obtained.
This paper presents the concept of objective landscape in the context of constraint programming. An objective landscape is a lightweight structure providing some information on the relation between decision variables ...
详细信息
ISBN:
(纸本)9783319930312;9783319930305
This paper presents the concept of objective landscape in the context of constraint programming. An objective landscape is a lightweight structure providing some information on the relation between decision variables and objective values, that can be quickly computed once and for all at the beginning of the resolution and is used to guide the search. It is particularly useful on decision variables with large domains and with a continuous semantics, which is typically the case for time or resource quantity variables in scheduling problems. This concept was recently implemented in the automatic search of CP Optimizer and resulted in an average speed-up of about 50% on scheduling problems with up to almost 2 orders of magnitude for some applications.
Machine-Part Cell Formation consists on organizing a plant as a set of cells, each one of them processing machines containing different part types. In recent years, different techniques have been used to solve this pr...
详细信息
ISBN:
(纸本)9781467398176
Machine-Part Cell Formation consists on organizing a plant as a set of cells, each one of them processing machines containing different part types. In recent years, different techniques have been used to solve this problem ranging from exact to approximate methods. This paper focuses on solving new instances of this problem for which no optimal value exists by using the classic Boctor's mathematical model. We employ constraint programming as the underlying solving technique illustrating that global optimums are achieved for the whole set of tested instances.
The stockyard management problem in a cargo assembly terminal mainly focuses on finding an efficient allocation of limited resources such as stockyard space, stacking and reclaiming machines to stockpiles such that th...
详细信息
ISBN:
(纸本)9783319459394;9783319459400
The stockyard management problem in a cargo assembly terminal mainly focuses on finding an efficient allocation of limited resources such as stockyard space, stacking and reclaiming machines to stockpiles such that the waiting time of a vessel fleet at port can be minimized. This highly complex problem involves scheduling with resource constraints in a dynamic environment and is a typical NP-hard problem in general. In this study, we present a constraint programming (CP) based approach to address the problem with utilizing the strength of CP in its flexibility in formulating various complex and nonlinear constraints for industrial applications. In addition, we explore the ability of the CP solver with trying different combinations of constraint propagation and constructive search strategies and report our best findings from an extensive computational study.
The CP conference is the annual international conference on constraint programming. It is concerned with all aspects of computing with constraints, including theory, algorithms, environments, languages, models, system...
详细信息
The CP conference is the annual international conference on constraint programming. It is concerned with all aspects of computing with constraints, including theory, algorithms, environments, languages, models, systems, and applications such as decision-making, resource allocation, scheduling, configuration, and planning. The CP community is very keen to ensure it remains open to interdisciplinary research at the intersection between constraint programming and related fields. Hence, in addition to the usual technical and application tracks, the CP 2016 conference featured thematic tracks: "Computational Sustainability", "CP and Biology", "Preferences, Social Choice and Optimization", and "Testing and Verification". In this overview, we highlight several remarkable papers that have been selected by the senior program committee and papers with the most innovative methods and techniques, and a very high potential for applications (in our opinion).
Given a graph G = (S, E), the problem dealt with in this paper consists in partitioning S into a disjoint union of cliques by adding or removing a minimum number z(G) of edges. The problem, which is refered to by the ...
详细信息
ISBN:
(纸本)9783319075938;9783319075921
Given a graph G = (S, E), the problem dealt with in this paper consists in partitioning S into a disjoint union of cliques by adding or removing a minimum number z(G) of edges. The problem, which is refered to by the Zahn Problem (ZP), is NP-hard in general. This paper presents a constraint programming approach to ZP. The problem is formulated in terms of a Weighted constraint Satisfaction Problem (WCSP), a widely used framework for solving hard combinatorial problems. As a seach strategy, we applied a Limited Discrepancy Search coupled with a branch-and-bound algorithm, a combination which has proved to be very advantageous. We compared our approach to a fixed-parameter tractability algorithm, one of the most used algorithms for solving ZP. The comparison clearly show that our approach is very competitive, especially on large ZP instances.
The design of efficient and generic algorithms for solving combinatorial optimization problems has been an active field of research for many years. Standard exact solving approaches are based on a clever and complete ...
详细信息
ISBN:
(纸本)9783030782306;9783030782290
The design of efficient and generic algorithms for solving combinatorial optimization problems has been an active field of research for many years. Standard exact solving approaches are based on a clever and complete enumeration of the solution set. A critical and non-trivial design choice with such methods is the branching strategy, directing how the search is performed. The last decade has shown an increasing interest in the design of machine learning-based heuristics to solve combinatorial optimization problems. The goal is to leverage knowledge from historical data to solve similar new instances of a problem. Used alone, such heuristics are only able to provide approximate solutions efficiently, but cannot prove optimality nor bounds on their solution. Recent works have shown that reinforcement learning can be successfully used for driving the search phase of constraint programming (CP) solvers. However, it has also been shown that this hybridization is challenging to build, as standard CP frameworks do not natively include machine learning mechanisms, leading to some sources of inefficiencies. This paper presents the proof of concept for SeaPearl, a new CP solver implemented in Julia, that supports machine learning routines in order to learn branching decisions using reinforcement learning. Support for modeling the learning component is also provided. We illustrate the modeling and solution performance of this new solver on two problems. Although not yet competitive with industrial solvers, SeaPearl aims to provide a flexible and open-source framework in order to facilitate future research in the hybridization of constraint programming and machine learning.
暂无评论