This research details the creation of a large-scale optimization approach for solving an application of a multi-period bilevel network interdiction problem (NIP). In this class of multi-period NIP, interdiction activi...
详细信息
This research details the creation of a large-scale optimization approach for solving an application of a multi-period bilevel network interdiction problem (NIP). In this class of multi-period NIP, interdiction activities must be scheduled to minimize the cumulative maximum flow over a finite time horizon. A logic-based decomposition (LBD) approach is proposed that utilizes constraint programming to exploit the scheduling nature of this multi-period NIP. Computational results-comparing solutions obtained using the proposed approach versus traditional mixed-integer programming approach-suggest that the LBD approach is more efficient in finding solutions for medium to large problem instances. (C) 2018 Elsevier Ltd. All rights reserved.
In a previous work we introduced a global StockingCost constraint to compute the total number of periods between the production periods and the due dates in a multi-order capacitated lot-sizing problem. Here we consid...
详细信息
In a previous work we introduced a global StockingCost constraint to compute the total number of periods between the production periods and the due dates in a multi-order capacitated lot-sizing problem. Here we consider a more general case in which each order can have a different per period stocking cost and the goal is to minimise the total stocking cost. In addition the production capacity, limiting the number of orders produced in a given period, is allowed to vary over time. We propose an efficient filtering algorithm in O(n log n) where n is the number of orders to produce. On a variant of the capacitated lot-sizing problem, we demonstrate experimentally that our new filtering algorithm scales well and is competitive wrt the StockingCost constraint when the stocking cost is the same for all orders.
This paper considers the flow shop scheduling problem with minimum and maximum time-lag requirements. According to the time-lag constraints, the starting time of each operation of a job must be within a specified time...
详细信息
This paper considers the flow shop scheduling problem with minimum and maximum time-lag requirements. According to the time-lag constraints, the starting time of each operation of a job must be within a specified time-window after the completion of its previous operation. The considered objective function is makespan and the problem is strongly NP-hard. In this article, a mixed integer linear programming (MILP) and two constraint programming (CP) models are proposed for the problem. To deal with the larger instances of this problems, it is decomposed into a sequencing and a timetabling sub-problem. A tabu search (TS) is developed to handle the sequencing sub-problem. Furthermore, an exact method based on the developed MILP as well as a greedy algorithm are proposed to deal with the timetabling sub-problem. A large number of test cases with different time-lag settings are solved to assess the performance of the proposed algorithm. Computational results confirm that the proposed TS is efficient and competitive. Moreover, the greedy timetabling method proves to be significantly faster than the exact method without sacrificing the solution quality.
Software Defined Networking (or SDN) allows to apply a centralized control over a network of commuters in order to provide better global performances. One of the problem to solve is the multicommodity flow routing whe...
详细信息
Software Defined Networking (or SDN) allows to apply a centralized control over a network of commuters in order to provide better global performances. One of the problem to solve is the multicommodity flow routing where a set of demands have to be routed at minimum cost. In contrast with other versions of this problem, we consider here problems with congestion that change the cost of a link according to the capacity used. We propose here to study centralized routing with constraint programming and Column Generation approaches. Furthermore, selfish routing is studied through with constraint Games. Selfish routing is important for the perceived quality of the solution since no user is able to improve his cost by changing only his own path. We present real and synthetic benchmarks that show a good scalability.
This paper presents a constraint programming approach for a batch processing machine on which a finite number of jobs of non-identical sizes must be scheduled. A parallel batch processing machine can process several j...
详细信息
This paper presents a constraint programming approach for a batch processing machine on which a finite number of jobs of non-identical sizes must be scheduled. A parallel batch processing machine can process several jobs simultaneously and the objective is to minimize the maximal lateness. The constraint programming formulation proposed relies on the decomposition of the problem into finding an assignment of the jobs to the batches, and then minimizing the lateness of the batches on a single machine. This formulation is enhanced by a new optimization constraint which is based on a relaxed problem and applies cost-based domain filtering techniques. Experimental results demonstrate the efficiency of cost-based domain filtering techniques. Comparisons to other exact approaches clearly show the benefits of the proposed approach: it can optimally solve problems that are one order of magnitude greater than those solved by a mathematical formulation or by a branch-and-price. (c) 2012 Elsevier B.V. All rights reserved.
Container vessel stowage planning is a hard combinatorial optimization problem with both high economic and environmental impact. We have developed an approach that often is able to generate near-optimal plans for larg...
详细信息
Container vessel stowage planning is a hard combinatorial optimization problem with both high economic and environmental impact. We have developed an approach that often is able to generate near-optimal plans for large container vessels within a few minutes. It decomposes the problem into a master planning phase that distributes the containers to bay sections and a slot planning phase that assigns containers of each bay section to slots. In this paper, we focus on the slot planning phase of this approach and present a constraint programming and Integer programming model for stowing a set of containers in a single bay section. This so-called slot planning problem is NP-hard and often involves stowing several hundred containers. Using state-of-the-art constraint solvers and modeling techniques, however, we were able to solve 90% of 236 real instances from our industrial collaborator to optimality within 1 second. Thus, somewhat to our surprise, it is possible to solve most of these problems optimally within the time required for practical application. (C) 2012 Elsevier B.V. All rights reserved.
constraint programming is a powerful tool for modeling various problems in operations research. Its strength lies in the use of predicates, or global high-level constraints, on a few variables to efficiently model com...
详细信息
constraint programming is a powerful tool for modeling various problems in operations research. Its strength lies in the use of predicates, or global high-level constraints, on a few variables to efficiently model complex and varied problem structures. In this paper, we consider the predicate at-least. It bounds the number of variables in a set that may receive a specific value. This is a generalization of the standard logic condition expressed when the sum of binary variables is expressing a lower bound on the cardinality of a set. We have completely determined the convex hull representation of this predicate and provide a polynomial separation algorithm for inclusion in branch-and-bound integer programming software.
This paper addresses the problem of scheduling on batch and unary machines with incompatible job families such that the total weighted completion time is minimised. A mixed-integer linear programming model is proposed...
详细信息
This paper addresses the problem of scheduling on batch and unary machines with incompatible job families such that the total weighted completion time is minimised. A mixed-integer linear programming model is proposed to solve the problem to optimality for small instances. Tight lower bounds and a 4-approximation algorithm are developed. A constraint programming-based method is also proposed. Numerical results demonstrate that the proposed algorithms can obtain high quality solutions and have a competitive performance. Sensitivity analysis indicates that the performance of the proposed algorithms is also robust on different problem structures.
Modeling discrete optimization problems is not straightforward. It is often the case that precompiling a subproblem that involves only a few tightly constrained variables as a table constraint can improve solving time...
详细信息
Modeling discrete optimization problems is not straightforward. It is often the case that precompiling a subproblem that involves only a few tightly constrained variables as a table constraint can improve solving time. Nevertheless, enumerating all the solutions of a subproblem into a table can be costly in time and space. In this work we propose using Multivalued Decision Diagrams (MDDs) and formulas in Deterministic Decomposable Negation Normal Form (d-DNNFs) rather than tables to compute and store all solutions of a subproblem. This, in turn, can be used to enhance the solver thanks to stronger propagation via specific propagators for these structures. We show how to precompile part of a problem into both these structures, which can then be injected back in the model by substituting the constraints it encodes, or simply adding it as a redundant constraint. Furthermore, in the case of MDDs, they can also be used to create edge-valued MDDs for optimization problems with an appropriate form. From our experiments we conclude that all three techniques are valuable in their own right, and show when each one should be chosen over the others.
Fast-tracking is an important process to speed the delivery of construction projects. To support optimum fast-tracking decisions, this paper introduces a generic schedule optimization framework that integrates four sc...
详细信息
Fast-tracking is an important process to speed the delivery of construction projects. To support optimum fast-tracking decisions, this paper introduces a generic schedule optimization framework that integrates four schedule acceleration dimensions: linear activity crashing;discrete activity modes of execution;alternative network paths;and flexible activity overlapping. Because excessive schedule compression can lead to space congestion and overstressed workers, the optimization formulation uses specific variables and constraints to prevent simultaneous use of overlapping and crashing at the same activity segment. To handle complex projects with a variety of milestones, resource limits, and constraints, the framework has been implemented using the constraint programming (CP) technique. Comparison with a literature case study and further experimentation demonstrated the flexibility and superior performance of the proposed model. The novelty of the model stems from its integrated multi-dimensional formulation, its CP engine, and its ability to provide alternative fast-track schedules to strictly constrained projects without overstressing the construction workers.
暂无评论