Knapsack problem is one of classical combinatorialoptimization problems, and has a lot of applications. It is known to be NP-hard. In this paper we propose a multistart local search heuristic for solving the knapsack...
详细信息
We model maximum cross-free matchings and minimum biclique covers of two-directional orthogonal ray graphs (2-dorgs) as maximum independent sets and minimum hitting sets of an associated family of rectangles in the pl...
详细信息
ISBN:
(纸本)9783642208072
We model maximum cross-free matchings and minimum biclique covers of two-directional orthogonal ray graphs (2-dorgs) as maximum independent sets and minimum hitting sets of an associated family of rectangles in the plane, respectively. We then compute the corresponding maximum independent set using linear programming and uncrossing techniques. this procedure motivates an efficient combinatorial algorithm to find a cross-free matching and a biclique cover of the same cardinality, proving the corresponding min-max relation. We connect this min-max relation withthework ofGyori [19], Lubiw[23], and Frank and Jordan [16] on seemingly unrelated problems. Our result can be seen as a non-trivial application of Frank and Jord ' an's theorem. As a direct consequence, we obtain the first polynomial algorithm for the jump number problem on 2-dorgs. For the subclass of convex graphs, our approach is a vast improvement over previous algorithms. Additionally, we prove that the weighted maximum cross-free matching problem is NP-complete for 2-dorgs and give polynomial algorithms for some subclasses.
In this paper we consider the general problem of optimizing over the intersection of a submodular base polyhedron and an affine space. An example is the following flow problem defined on a capacitated network: we wish...
详细信息
this paper provides a practical comparison between Mixed integer Linear programming and Particle Swarm optimization when applied to the Optimal Sizing and Placement of Distributed Generation in Microgrids. the two for...
详细信息
ISBN:
(纸本)9781509040001
this paper provides a practical comparison between Mixed integer Linear programming and Particle Swarm optimization when applied to the Optimal Sizing and Placement of Distributed Generation in Microgrids. the two formulations are presented and the methods are applied to a planning problem of a real isolated microgrid in Alaska.
Energy efficiency is considered a challenging problem in modern multicore systems. Partitioning the cores into multiple voltage and frequency islands (VFI) provides a compromise between simple global Dynamic Voltage F...
详细信息
ISBN:
(纸本)9781538625880
Energy efficiency is considered a challenging problem in modern multicore systems. Partitioning the cores into multiple voltage and frequency islands (VFI) provides a compromise between simple global Dynamic Voltage Frequency Scaling (DVFS) and fine-grain per-core, per-task DVFS. this paper formulates the optimization problem of scheduling tasks statically on multiple VFIs as a Mixed integer Linear programming (MILP) such that for a given energy budget, the program execution time (makespan) is minimized. Our proposed solution consists of two steps. In the first step, we use an integer Linear programming (ILP)-based algorithm, from our previous work, to assign per-core fine-grain dynamic Voltage/Frequency (V/F) levels to each task in a task set (program) to minimize the makespan for a given energy budget. In the second step, which is the focus of this paper, we use the MILP framework to schedule this task set, withthe given V/F levels provided in step one, on the islands of a VFI-enabled multicore system to again minimize the makespan subject to (1) the energy budget and (2) the task set's precedence (dependency) constraints. Together withthe solutions obtained by MILP, a round-robin algorithm is used to compare these two methodologies to ILP that provides the best solution. Our experimental results show that across all the benchmarks considered, the MILP-based and round-robin makespan solutions are on average 1.2 and 2.28 times slower than the ILP based makespan solutions, respectively.
A subset selection problem from a finite set of items is considered, where a constraint is imposed on the cardinality of a selected subset. the subset selection problem is motivated by automated packaging systems, so-...
详细信息
ISBN:
(纸本)9781538626337
A subset selection problem from a finite set of items is considered, where a constraint is imposed on the cardinality of a selected subset. the subset selection problem is motivated by automated packaging systems, so-called multi-head weighers. Given a set of n items withtheir integral weights, a positive integer target weight t and a positive integer k, the subset selection problem asks to find a subset of the items so that the total weight of chosen items is no less than the target weight, and the number of the chosen items is exactly k, and further the total weight of them is as close to the target weight as possible. In this paper, an O(knt) time algorithm is presented to solve the subset selection problem. Numerical experiments are also conducted to demonstrate the performance of the pseudo-polynomial time algorithm on certain test instances having a feasible solution, and the results are reported.
Stream programming abstracts parallelism complexity by modeling a program as a set of streaming tasks. Tasks run repeatedly and can even be internally parallel, i.e., use one or multiple cores simultaneously (moldable...
详细信息
ISBN:
(纸本)9781728138435
Stream programming abstracts parallelism complexity by modeling a program as a set of streaming tasks. Tasks run repeatedly and can even be internally parallel, i.e., use one or multiple cores simultaneously (moldable). the throughput of the streaming application, as well as its energy consumption, depends strongly on scheduling, i.e., on how tasks are mapped to cores, and on the frequency at which they run. Crown scheduling is a scheduling method that reduces this problem's combinatorial complexity considerably by introducing a few additional restrictions especially on tasks' core allocation sizes and mapping. While it has previously been shown to outperform competing methods, the impact of these restrictions on the schedule quality has, up to now, never been analyzed quantitatively. In this paper, we first propose several crown scheduler improvements toward fewer restrictions. Also, we provide an integer Linear programming formulation that solves the same optimization problem without the inherent restrictions of crown scheduling. While in an extreme case an unrestricted schedule might use 3.7 times less energy than a crown schedule for a realistic execution platform model, we show that in practical benchmarks the difference is small while crown schedulers are significantly faster than unrestricted scheduling. We experimentally confirm this with benchmarks derived from random task collections, classic parallel algorithms as well as the Streamit benchmark suite.
the proceedings contain 28 papers. the special focus in this conference is on Integration of Constraint programming, Artificial Intelligence, and Operations Research. the topics include: Solving the Extended Job ...
ISBN:
(纸本)9783031080104
the proceedings contain 28 papers. the special focus in this conference is on Integration of Constraint programming, Artificial Intelligence, and Operations Research. the topics include: Solving the Extended Job Shop Scheduling Problem with AGVs – Classical and Quantum Approaches;stochastic Decision Diagrams;Improving the Robustness of EPS to Solve the TSP;Efficient Operations Between MDDs and Constraints;deep Policy Dynamic programming for Vehicle Routing Problems;learning a Propagation Complete Formula;a FastMap-Based Algorithm for Block Modeling;packing by Scheduling: Using Constraint programming to Solve a Complex 2D Cutting Stock Problem;dealing withthe Product Constraint;multiple-choice Knapsack Constraint in Graphical Models;A SAT Encoding to Compute Aperiodic Tiling Rhythmic Canons;a Learning Large Neighborhood Search for the Staff Rerostering Problem;a MinCumulative Resource Constraint;practically Uniform Solution Sampling in Constraint programming;training thinner and Deeper Neural Networks: Jumpstart Regularization;hybrid Offline/Online optimization for Energy Management via Reinforcement Learning;enumerated Types and Type Extensions for MiniZinc;A Parallel Algorithm for GAC Filtering of the Alldifferent Constraint;analyzing the Reachability Problem in Choice Networks;model-Based Approaches to Multi-attribute Diverse Matching;Transferring Information Across Restarts in MIP;towards Copeland optimization in combinatorial Problems;Coupling Different integer Encodings for SAT;model-Based Algorithm Configuration with Adaptive Capping and Prior Distributions;shattering Inequalities for Learning Optimal Decision Trees;learning Pseudo-Backdoors for Mixed integer Programs.
To stay competitive and preserve high service levels for their customers, the focus of warehouses in today's supply chain is on timely and faster delivery of smaller and more frequent orders. To keep up with compe...
详细信息
ISBN:
(纸本)9781510847675
To stay competitive and preserve high service levels for their customers, the focus of warehouses in today's supply chain is on timely and faster delivery of smaller and more frequent orders. To keep up with competitors, companies accept late orders from customers, which results in additional pressure for order picking operations. Specifically, more orders need to be picked and sorted in shorter and more flexible time windows, which often results in workload peaks during the day. the objective of this study is to balance the workload across the day in parallel zone order picking systems. A real-life case-study demonstrates the value of balancing the workload for European order lines in a large international warehouse system located in Belgium, engaged in the distribution of spare parts. Solving the operational workload imbalance problem results in a more stable order picking process and overall productivity improvements for the total warehouse operations.
暂无评论