Background: The protein folding problem remains one of the most challenging open problems in computational biology. Simplified models in terms of lattice structure and energy function have been proposed to ease the co...
详细信息
Background: The protein folding problem remains one of the most challenging open problems in computational biology. Simplified models in terms of lattice structure and energy function have been proposed to ease the computational hardness of this optimization problem. Heuristic search algorithms and constraint programming are two common techniques to approach this problem. The present study introduces a novel hybrid approach to simulate the protein folding problem using constraint programming technique integrated within local search. Results: Using the face-centered-cubic lattice model and 20 amino acid pairwise interactions energy function for the protein folding problem, a constraint programming technique has been applied to generate the neighbourhood conformations that are to be used in generic local search procedure. Experiments have been conducted for a few small and medium sized proteins. Results have been compared with both pure constraint programming approach and local search using well-established local move set. Substantial improvements have been observed in terms of final energy values within acceptable runtime using the hybrid approach. Conclusion: constraint programming approaches usually provide optimal results but become slow as the problem size grows. Local search approaches are usually faster but do not guarantee optimal solutions and tend to stuck in local minima. The encouraging results obtained on the small proteins show that these two approaches can be combined efficiently to obtain better quality solutions within acceptable time. It also encourages future researchers on adopting hybrid techniques to solve other hard optimization problems.
This contribution introduces an efficient constraint programming (CP) model that copes with largescale scheduling problems in multiproduct multistage batch plants. It addresses several features found in industrial env...
详细信息
This contribution introduces an efficient constraint programming (CP) model that copes with largescale scheduling problems in multiproduct multistage batch plants. It addresses several features found in industrial environments, such as topology constraints, forbidden product-equipment assignments, sequence-dependent changeover tasks, dissimilar parallel units at each stage, limiting renewable resources and multiple-batch orders, among other relevant plant characteristics. Moreover, the contribution deals with various inter-stage storage and operational policies. In addition, multiple-batch orders can be handled by defining a campaign operating mode, and lower and upper bounds on the number of batches per campaign can be fixed. The proposed model has been extensively tested by means of several case studies having various problem sizes and characteristics. The results have shown that the model can efficiently solve medium and large-scale problems with multiple constraining features. The approach has also rendered good quality solutions for problems that consider multiple-batch orders under a campaign-based operational policy. (C) 2016 Elsevier Ltd. All rights reserved.
The short-term scheduling of activities in underground mines is an important step in mining operations. This procedure is a challenging optimization problem since it deals with many resources and activities conducted ...
详细信息
The short-term scheduling of activities in underground mines is an important step in mining operations. This procedure is a challenging optimization problem since it deals with many resources and activities conducted in a confined working space. Moreover, underground mining operations deal with multiple uncertainties such as the variation of activity durations. In this paper, a constraint programming (CP) model is proposed for short-term planning in underground mines. The developed model takes into account the technical requirements of underground operations to build realistic mine schedules. Furthermore, two different approaches are proposed based on the CP model for robust short-term underground mine scheduling. The first approach aims to create a robust schedule using multiple scenarios of the problem. This stochastic CP model enables to find a set of ordered robust sequences of activities performed by each available disjunctive resource over several scenarios. In the second approach, a confidence constraint is introduced in the CP model to specify the probability that the schedule generated would not underestimate the duration of activities. The model allows the mine planner to control the risk level with which an optimized solution should be produced such that it can be implemented given the actual activity durations. The presented approaches are tested on real data sets of an underground gold mine in Canada. An evaluation model is designed to evaluate the robust performance of the proposed models. The experiments demonstrate that both scenario-based and confidence-constraint approaches outperform the deterministic model by generating schedules that are more robust to uncertainties in underground operations.
To model combinatorial decision problems involving uncertainty and probability, we introduce scenario based stochastic constraint programming. Stochastic constraint programs contain both decision variables, which we c...
详细信息
To model combinatorial decision problems involving uncertainty and probability, we introduce scenario based stochastic constraint programming. Stochastic constraint programs contain both decision variables, which we can set, and stochastic variables, which follow a discrete probability distribution. We provide a semantics for stochastic constraint programs based on scenario trees. Using this semantics, we can compile stochastic constraint programs down into conventional (non-stochastic) constraint programs. This allows us to exploit the full power of existing constraint solvers. We have implemented this framework for decision making under uncertainty in stochastic OPL, a language which is based on the OPL constraint modelling language (Van Hentenryck, P., Michael, L., Perron, L., & Regin, J.-C. (1999) constraint programming in OPL. In G. Nadathur, (Ed.), Principles and practice of declarative programming, LNCS 1702, (pp. 97-116). Springer-Verlag). To illustrate the potential of this framework, we model a wide range of problems in areas as diverse as portfolio diversification, agricultural planning and production/inventory management.
Combining goal-modeling techniques with constraint programming provides the means to identify the variants best suited to the environmental contexts that a self-adaptive software system might encounter at runtime.
Combining goal-modeling techniques with constraint programming provides the means to identify the variants best suited to the environmental contexts that a self-adaptive software system might encounter at runtime.
Safety-critical software must be thoroughly verified before being exploited in commercial applications. In particular, any TCAS (Traffic Alert and Collision Avoidance System) implementation must be verified against sa...
详细信息
Safety-critical software must be thoroughly verified before being exploited in commercial applications. In particular, any TCAS (Traffic Alert and Collision Avoidance System) implementation must be verified against safety properties extracted from the anti-collision theory that regulates the controlled airspace. This verification step is currently realized with manual code reviews and testing. In our work, we explore the capabilities of constraint programming for automated software verification and testing. We built a dedicated constraint solving procedure that combines constraint propagation with Linear programming to solve conditional disjunctive constraint systems over bounded integers extracted from computer programs and safety properties. An experience we made on verifying a publicly available TCAS component implementation against a set of safety-critical properties showed that this approach is viable and efficient.
We study a tournament format that extends a traditional double round-robin format with divisional single round-robin tournaments. Elitserien, the top Swedish handball league, uses such a format for its league schedule...
详细信息
We study a tournament format that extends a traditional double round-robin format with divisional single round-robin tournaments. Elitserien, the top Swedish handball league, uses such a format for its league schedule. We present a constraint programming model that characterizes the general double round-robin plus divisional single round-robin format. This integrated model allows scheduling to be performed in a single step, as opposed to common multistep approaches that decompose scheduling into smaller problems and possibly miss optimal solutions. In addition to general constraints, we introduce Elitserien-specific requirements for its tournament. These general and league-specific constraints allow us to identify implicit and symmetry-breaking properties that reduce the time to solution from hours to seconds. A scalability study of the number of teams shows that our approach is reasonably fast for even larger league sizes. The experimental evaluation of the integrated approach takes considerably less computational effort to schedule Elitserien than does the previous decomposed approach. (C) 2016 Elsevier B.V. All rights reserved.
We consider the 2D orthogonal feasibility problem (OPP-2) and the 2D strip packing problem (SPP-2). Given a set of rectangular items, the OPP-2 is to decide whether all items can be orthogonally packed into the given ...
详细信息
We consider the 2D orthogonal feasibility problem (OPP-2) and the 2D strip packing problem (SPP-2). Given a set of rectangular items, the OPP-2 is to decide whether all items can be orthogonally packed into the given rectangular container;the SPP-2 is to find a packing of all items occupying the minimal height of the given semi-infinite strip. Both OPP-2 and SPP-2 are considered without items rotation. We investigate the known constraint programming (CP) approaches for OPP-2, in particular the dichotomy and disjunctive branching strategies and adapt 1D relaxation bounds based on linear programming (LP) into the constraint propagation process of the CP. Using the dichotomic search procedure the developed methods for OPP-2 are transformed for the case of SPP-2. Numerical results demonstrate the efficiency of the proposed strategies and of the combination of CP and LP-based pruning rules. (C) 2011 Elsevier Ltd. All rights reserved.
In the literature, line balancing is mostly investigated in deterministic environments. But production systems inevitably contain stochastic situations. In this study, the stochastic type-II assembly line balancing pr...
详细信息
In the literature, line balancing is mostly investigated in deterministic environments. But production systems inevitably contain stochastic situations. In this study, the stochastic type-II assembly line balancing problem (ALBP) is considered. Firstly, a chance-constrained nonlinear mixed integer programming (MIP) formulation is developed from the well-known deterministic form. Then, a new linearized stochastic model is proposed by using some transformation approaches to reduce model complexity, and the model is solved. Finally, constraint programming (CP) models for deterministic ALBPs, nonlinear chance-constrained stochastic ALBPs and linearized chance-constrained stochastic ALBPs are developed, respectively. Problems from the literature are utilized to test the effectiveness of the proposed models and the results are compared with a bidirectional heuristic algorithm. The numerical results show that the CP models are more effective and successful for solving the stochastic ALBP. Some managerial implications are also suggested for industrial environments that consistently face ALBPs.
This study addresses the premarshalling problem when the crane time is limited and a complete rearrangement of the bay is not possible. This issue has been neglected in the literature, but it is very common in practic...
详细信息
This study addresses the premarshalling problem when the crane time is limited and a complete rearrangement of the bay is not possible. This issue has been neglected in the literature, but it is very common in practice. We show that the use of standard approaches often fails to yield good solutions and develop a model for the problem in two steps. First, a constraint programming model is proposed for premarshalling with crane time minimization objective. Then, this model is adapted to the new problem. An extensive computational study shows that the first model improves on the performance of the existing state-of-the-art integer programming model and that the model of the new problem obtains high quality solutions even in short running times.
暂无评论