This paper presents a new approach to describe the analog power-down synthesis problem by combining two state-of-the art constraint programs to a unified, homogeneous constraint optimization problem that, in contrast ...
详细信息
ISBN:
(纸本)9781728171838
This paper presents a new approach to describe the analog power-down synthesis problem by combining two state-of-the art constraint programs to a unified, homogeneous constraint optimization problem that, in contrast to the previous approach, allows trade-offs between the two design goals "matching" and "area". Furthermore, enhanced symmetry constraints are incorporated by the new method. Experimental results show the efficacy of the proposed method.
We present a new constraint programming (CP) model to optimize the transition cost of Fixed Job Scheduling (FJS), which improves our previous approach based on per-resource constraints by orders of magnitude. Our new ...
详细信息
ISBN:
(纸本)9781643681016;9781643681009
We present a new constraint programming (CP) model to optimize the transition cost of Fixed Job Scheduling (FJS), which improves our previous approach based on per-resource constraints by orders of magnitude. Our new model relies on a much tighter relaxation which encompasses all resources to directly propagate on the global cost, thanks to the MinWeightAllDiff optimization constraint. We also present several strategies which exploit the optimal matching computed by the MinWeightAllDiff constraint to efficiently guide the search. The resulting CP solver, using parallel cooperation between the strategies, consistently outperforms a state-of-the-art MIP solver on real instances of an FJS application, the Gate Allocation Problem, at Paris-Charles-de-Gaulle international airport.
The profitability of any assembly robot installation depends on the production throughput, and to an even greater extent on incurred costs. Most of the cost comes from manually designing the layout and programming the...
详细信息
ISBN:
(纸本)9783030589424;9783030589417
The profitability of any assembly robot installation depends on the production throughput, and to an even greater extent on incurred costs. Most of the cost comes from manually designing the layout and programming the robot as well as production downtime. With ever smaller production series, fewer products share this cost. In this work, we present the dual arm assembly program as an integrated routing and scheduling problem with complex arm-to-arm collision avoidance. We also present a set of high-level layout decisions, and we propose a unified CP model to solve the joint problem. The model is evaluated on realistic instances and real data. The model finds high-quality solutions in short time, and proves optimality for all evaluated problem instances, which demonstrates the potential of the approach.
The traditional approach to Model Expansion (MX) is to reduce the theory to a propositional language and apply a search algorithm to the resulting theory. Function symbols are typically replaced by predicate symbols r...
详细信息
ISBN:
(纸本)9781479929733
The traditional approach to Model Expansion (MX) is to reduce the theory to a propositional language and apply a search algorithm to the resulting theory. Function symbols are typically replaced by predicate symbols representing the graph of the function, an operation that blows up the reduced theory. In this paper, we present an improved approach to handle function symbols in a ground-and-solve methodology, building on ideas from constraint programming. We do so in the context of FO(·)~(IDP), the knowledge representation language that extends First-Order Logic (FO) with, among others, inductive definitions, arithmetic and aggregates. An MX algorithm is developed, consisting of (i) a grounding algorithm for FO(·)~(IDP), parametrised by the function symbols allowed to occur in the reduced theory, and (ii) a search algorithm for unrestricted, ground FO(·)~(IDP). The ideas are implemented in the IDP knowledge-base system and experimental evaluation shows that both more compact groundings and improved search performance are obtained.
This paper considers the on-time guillotine cutting of small rectangular items from large rectangular bins. Items assigned to a bin define the bins' processing time. Consequently, an item inherits the completion t...
详细信息
This paper considers the on-time guillotine cutting of small rectangular items from large rectangular bins. Items assigned to a bin define the bins' processing time. Consequently, an item inherits the completion time of its assigned bin. Any deviation of an item's completion time from its due date causes either earliness or tardiness penalties. This just-in-time two-dimensional bin packing problem (JITBP) combines two difficult discrete optimization problems: Bin packing and total weighted earliness tardiness single machine scheduling. It is herein modeled as an integrated constraint program, augmented with two sets of logically redundant constraints that speed the search. The first set uses the concept of dual feasible functions. It focuses on bin packing feasibility. The second is the result of a linear program that schedules filled bins on a single machine. As an alternative to this integrated model, this paper proposes two decomposition cut-and-check approaches that define the master problem (MP) as a relaxation of JITBP where the items are reduced to dimensionless entities. They then reestablish the geometric feasibility of the MPs' solutions by iteratively augmenting MP with Benders cuts generated from the subproblems. The two approaches are similar in concept except that one implements MP as a constraint program (CP) while the second implements it as a mixed-integer program (MIP). Because JITBP is computationally challenging, we test all approaches under a number of heuristic assumptions, which include a maximum runtime for the MIP and CP solvers. The results provide computational evidence that the integrated constraint programming approach performs relatively well, and outperforms the decomposition approach whose MP is a CP. However, both approaches are outperformed by the decomposition approach whose MP is a warm-started MIP. (c) 2020 Elsevier Ltd. All rights reserved.
Reinforcement learning has shown its relevance in designing search heuristics for backtracking algorithms dedicated to solving decision problems under constraints. Recently, an efficient heuristic, called Conflict His...
详细信息
ISBN:
(纸本)9781728192284
Reinforcement learning has shown its relevance in designing search heuristics for backtracking algorithms dedicated to solving decision problems under constraints. Recently, an efficient heuristic, called Conflict History Search (CHS), based on the history of search failures was introduced for the constraint Satisfaction Problem (CSP). The Exponential Recency Weighted Average (ERWA) is used to estimate the hardness of constraints and CHS favors the variables that often appear in recent failures. The step parameter is important in CHS since it controls the estimation of the hardness of constraints and its refinement may lead to notable improvements. The current research aims to achieve this objective. Indeed, a Multi-Armed Bandits (MAB) framework can select an appropriate value of this parameter during the restarts performed by the search algorithm. Each arm represents a CHS with a given value for the step parameter and it is rewarded by its ability to improve the search. A training phase is introduced earlier in the search to help MAB choose a relevant arm. The experimental evaluation shows that this approach leads to significant improvements regarding CHS and other state-of-the-art heuristics.
This competition paper presents microPhantom, a bot playing microRTS and participating in the 2020 microRTS AI competition. microPhantom is based on our previous bot POAdaptive which won the partially observable track...
详细信息
ISBN:
(纸本)9781728145334
This competition paper presents microPhantom, a bot playing microRTS and participating in the 2020 microRTS AI competition. microPhantom is based on our previous bot POAdaptive which won the partially observable track of the 2018 and 2019 microRTS AI competitions. In this paper, we focus on decision-making under uncertainty, by tackling the Unit Production Problem with a method based on a combination of constraint programming and decision theory. We show that using our method to decide which units to train improves significantly the win rate against the second-best microRTS bot from the partially observable track. We also show that our method is resilient in chaotic environments, with a very small loss of efficiency only. To allow replicability and to facilitate further research, the source code of microPhantom is available, as well as the constraint programming toolkit it uses.
The article considers ontology as a set of relations (unary and binary) which are represented by specialized matrix like structures C-systems. That allows us to consider tasks of inference on ontologies as constraint ...
详细信息
ISBN:
(纸本)9781643680453;9781643680446
The article considers ontology as a set of relations (unary and binary) which are represented by specialized matrix like structures C-systems. That allows us to consider tasks of inference on ontologies as constraint satisfaction problems. A method of a priori analysis and transformation of SPARQL queries patterns into a form which speeds up the subsequent execution of concrete user queries has been developed. The method is oriented on ontologies developed with using content ontology design patterns, that ensures the predictability of the structure of potential queries. The method is based on the combining of the methods of structural decomposition and the original methods for non-numerical constraints satisfaction.
In this article, we consider the problem of planning maintenance operations at a locomotive maintenance depot. There are three types of tracks at the depot: buffer tracks, access tracks and service tracks. A depot con...
详细信息
ISBN:
(纸本)9783030386030;9783030386023
In this article, we consider the problem of planning maintenance operations at a locomotive maintenance depot. There are three types of tracks at the depot: buffer tracks, access tracks and service tracks. A depot consists of up to one buffer track and a number of access tracks, each of them ending with one service track. Each of these tracks has a limited capacity measured in locomotive sections. We present a constraint programming model and a greedy algorithm for solving the problem of planning maintenance operations. Using lifelike data based on the operation of several locomotive maintenance depots in Eastern polygon of Russian Railways, we carry out numerical experiments to compare the presented approaches.
A mixed model assembly line is production line where various product models are assembled. Line balancing and model sequencing problems are important for the efficiency of the assembly line. This paper solves them sim...
详细信息
A mixed model assembly line is production line where various product models are assembled. Line balancing and model sequencing problems are important for the efficiency of the assembly line. This paper solves them simultaneously aiming to minimize the latest completion time. A mixed integer liner programming model and a constraint programming model are proposed to provide the exact solution of the problem with station‐dependent assembly times. Because of NP‐hardness, a variable neighborhood simulated annealing algorithm is applied and compared to the hybrid simulated annealing algorithm from the literature. To strength the search process, a encoding method and a decoding method were proposed. Numerical results statistically show the efficiency of the proposed algorithm in terms of both the quality of solution and the time of achieving the best solution.
暂无评论