A graph is an interval graph if its vertex set corresponds to a family of intervals on the real line, called a model, such that two distinct vertices are adjacent in the graph if and only if their corresponding interv...
详细信息
A graph is an interval graph if its vertex set corresponds to a family of intervals on the real line, called a model, such that two distinct vertices are adjacent in the graph if and only if their corresponding intervals intersect each other. The minimum number of interval lengths that suffices to represent a model of a given interval graph is its interval count. The use of mathematical optimization techniques for solving interval count problems was first explored by Joos et al.[1]. In more detail, given a bipartition of vertices into classes of lengths, the authors propose an efficient linear programming based algorithm for solving the interval count two problem. However, so far, no mathematical formulation exists in the literature for general interval count. As a contribution in that direction, we introduce a mixed integer programming formulation for the exact value of interval count, parameterized by the largest interval length. Additionally, we also propose a quadratic formulation for a valid upper bound on interval count. Solution algorithms for these formulations were tested on interval count instances found in the literature. As an outcome of these experiments, the algorithm for the upper bound formulation was shown to run much faster than its exact solution counterpart. Furthermore, the upper bounds thus obtained were frequently certified as optimal by the exact algorithm.
The problem addressed in this paper focuses on the reduction of electrical energy costs for the operation of hydraulic pumps, which are used for catchment and distribution of water in water supply systems. As the elec...
详细信息
The problem addressed in this paper focuses on the reduction of electrical energy costs for the operation of hydraulic pumps, which are used for catchment and distribution of water in water supply systems. As the electricity tariffs are different according to the time of day, it is necessary to decide when and how many pumps must be used to collect and distribute water, in each period of time, and, when there must be water transfer among tanks so that the demand of each consumer center is met without a lack of resources. A mixed integer programming (MIP) model is proposed and a competitive MIP-based heuristic is developed to solve this problem. Numerical tests in a case study carried out with the water supply system of a Brazilian city demonstrate the efficiency of the proposed mathematical model and solution method.
Large Neighborhood Search (LNS) heuristics are among the most powerful but also most expensive heuristics for mixedinteger programs (MIP). Ideally, a solver adaptively concentrates its limited computational budget by...
详细信息
Large Neighborhood Search (LNS) heuristics are among the most powerful but also most expensive heuristics for mixedinteger programs (MIP). Ideally, a solver adaptively concentrates its limited computational budget by learning which LNS heuristics work best for the MIP problem at hand. To this end, this work introduces Adaptive Large Neighborhood Search (ALNS) for MIP, a primal heuristic that acts as a framework for eight popular LNS heuristics such as Local Branching and Relaxation Induced Neighborhood Search (RINS). We distinguish the available LNS heuristics by their individual search spaces, which we call auxiliary problems. The decision which auxiliary problem should be executed is guided by selection strategies for the multi armed bandit problem, a related optimization problem during which suitable actions have to be chosen to maximize a reward function. In this paper, we propose an LNS-specific reward function to learn to distinguish between the available auxiliary problems based on successful calls and failures. A second, algorithmic enhancement is a generic variable fixing prioritization, which ALNS employs to adjust the subproblem complexity as needed. This is particularly useful for some LNS problems which do not fix variables by themselves. The proposed primal heuristic has been implemented within the MIP solver SCIP. An extensive computational study is conducted to compare different LNS strategies within our ALNS framework on a large set of publicly available MIP instances from the MIPLIB and Coral benchmark sets. The results of this simulation are used to calibrate the parameters of the bandit selection strategies. A second computational experiment shows the computational benefits of the proposed ALNS framework within the MIP solver SCIP.
We introduce a novel and powerful approach for solving certain classes of mixedinteger programs (MIPs): decomposition branching. Two seminal and widely used techniques for solving MIPs, branch-and-bound and decomposi...
详细信息
We introduce a novel and powerful approach for solving certain classes of mixedinteger programs (MIPs): decomposition branching. Two seminal and widely used techniques for solving MIPs, branch-and-bound and decomposition, form its foundation. Computational experiments with instances of a weighted set covering problem and a regionalized p-median facility location problem with assignment range constraints demonstrate its efficacy: it explores far fewer nodes and can be orders of magnitude faster than a commercial solver and an automatic Dantzig-Wolfe approach.
In this work, we present the design and implementation of an ultra-low latency Deep Reinforcement Learning (DRL) FPGA based accelerator for addressing hard real-time mixed integer programming problems. The accelerator...
详细信息
In this work, we present the design and implementation of an ultra-low latency Deep Reinforcement Learning (DRL) FPGA based accelerator for addressing hard real-time mixed integer programming problems. The accelerator exhibits ultra-low latency performance for both training and inference operations, enabled by training-inference parallelism, pipelined training, on-chip weights and replay memory, multi-level replication-based parallelism and DRL algorithmic modifications such as distribution of training over time. The design principles can be extended to support hardware acceleration for other relevant DRL algorithms (embedding the experience replay technique) with hard real time constraints. We evaluate the accuracy of the accelerator in a task offloading and resource allocation problem stemming from a Mobile Edge Computing (MEC/5G) scenario. The design has been implemented on a Xilinx Zynq Ultrascale+ MPSoC ZCU104 evaluation kit using High Level Synthesis. The accelerator achieves near optimal performance and exhibits a 10-fold decrease in training-inference execution latency when compared to a high-end CPU-based implementation.
Researchers have studied the nurse rostering problem for multiple decades. Initially, the formulations were rather primitive including only a few necessary restrictions, but down the road, the formulations have become...
详细信息
Researchers have studied the nurse rostering problem for multiple decades. Initially, the formulations were rather primitive including only a few necessary restrictions, but down the road, the formulations have become more complex. Nonetheless, a fraction of the research reaches implementation in practice, and many wards still schedule nurses manually. In this article, we introduce a flexible nurse rostering system that employs mathematical optimization to automatically schedule nurses to shifts. We have developed this system in collaboration with practitioners to fully match their needs. The system consists of a comprehensive mixed integer programming (MIP) model along with a flexible framework. In addition to common constraints from the literature, the mathematical formulation includes three new constraints that further encourage healthy work schedules for each nurse. Additionally, we have reformulated some common constraints from the literature and allow for a complex shift structure that matches the needs of real hospital wards. This flexibility results in increased adaptability for different wards with different needs and is crucial to address the complex nurse rostering problem that practitioners face. We have successfully implemented this system in two wards at two Danish hospitals. We present the MIP model along with computational results for 12 real-world rostering instances. Furthermore, we discuss the practical impact of this system and provide general feedback from the practitioners using it. Overall, the results illustrate the capabilities of the system to tackle diverse nurse rostering instances and produce outstanding results.
Petri nets, as an effective mathematical tool, have been intensively used in modeling and analyzing automated manufacturing systems (AMSs). Many deadlock control policies have been proposed for AMSs, but most of them ...
详细信息
Petri nets, as an effective mathematical tool, have been intensively used in modeling and analyzing automated manufacturing systems (AMSs). Many deadlock control policies have been proposed for AMSs, but most of them assume that resources never fail during product processing. However, resource failures may happen in a real world, which may invalidate existing control policies. This paper concentrates on robust liveness-enforcing supervisor design for a system of simple sequential processes with multiple unreliable resources. Recovery subnets model resource failure and recovery, which are added to the holders of unreliable resource places. The proposed method consists of two steps. At the first step, a mixed integer programming (MIP) problem is developed to detect a strict minimal siphon that can be emptied. At the second step, an extended constraint set derived by the complementary set of a siphon is constructed. The siphon is controlled through the extended constraint set by adding a control place. The above two steps are executed in an iterative way until no new empty siphon is found and a robust liveness-enforcing supervisor can be obtained. Examples are used to expose the advantages of the proposed method.
A two-step topology-finding method based on mixed integer programming and nonlinear programming is proposed for tensegrity structures. In the first step, feasible and symmetric strut connectivities are obtained throug...
详细信息
A two-step topology-finding method based on mixed integer programming and nonlinear programming is proposed for tensegrity structures. In the first step, feasible and symmetric strut connectivities are obtained through a ground structure method combined with mixed integer programming;in the second step, the cable connectivities are optimized through nonlinear programming to obtain a feasible tensegrity structure. The same ground structure used in the first step is adopted in the second step, which is beneficial to find a more symmetric cable layout. The independent continuous mapping method is used in the second step to convert the 0-1 binary variables of cable connectivities to continuous variables to transform the combinatorial optimization problem into a nonlinear programming problem. The number of strut lengths is adopted as a control parameter and a symmetry objective function is proposed to generate a variety of regular and symmetric tensegrity structures. A multi-stage computation scheme is proposed to improve the computational efficiency. Typical examples are carried out to validate the proposed method. The computational efficiency of the method is benchmarked with existing methods fully based on mixed integer programming. Results demonstrate that the computational efficiency of the proposed method is significantly improved compared to the existing methods.
BackgroundIn Brazil, institutional foodservices are required to meet the recommendations of the Workers? Food Program (WFP), a national public policy used to plan collective menus. The current study aimed to propose a...
详细信息
BackgroundIn Brazil, institutional foodservices are required to meet the recommendations of the Workers? Food Program (WFP), a national public policy used to plan collective menus. The current study aimed to propose a mathematical model to generate a one-month menu that meets the nutritional recommendations of the WFP, with low cost and good *** considered aspects related to the eating habits of the Brazilian population, spacing of repetitions between the dishes, texture combination, and monotonicity of colors of the dishes served. A mixed integer programming model was built to formulate daily menus for an institutional foodservice for one month. The menu consisted of a base dish, a base dish option, salads (2 options), a protein dish, a protein dish option, a side dish, and a *** model ensured compliance with the recommendations proposed by the WFP and the provision of healthy and nutritionally balanced meals. The menu generated met the recommendations of the WFP, with an average of 716.97 kcal/meal, including on average 58.28% carbohydrates, 17.89% proteins, and 24.88% total fats/*** model used can help in the menu elaboration dynamics of institutional foodservices, optimizing the work of the nutritionist in charge.
Product recovery has received greater attention in recent years mainly due to increased environmental awareness of consumers and stricter environmental regulations imposed by governments. In product recovery, disassem...
详细信息
Product recovery has received greater attention in recent years mainly due to increased environmental awareness of consumers and stricter environmental regulations imposed by governments. In product recovery, disassembly of the product into its constituent parts is the most significant activity and generally performed on a disassembly line. During disassembly, a complete or partial disassembly of the product may be preferred. In complete disassembly, all parts must be disassembled, while partial disassembly allows to disassemble a subset of parts (e. g., the ones with relatively high revenues). This study deals with a partial disassembly line balancing and sequencing (PDLBS) problem considering revenues of parts to be disassembled, general workstation cost, additional cost of workstation(s) with hazardous parts, and cost of direction changes. For the PDLBS problem, a generic mixed integer programming (MIP) model, with the aim of maximizing total profit, is developed. To strengthen the MIP formulation, two sets of valid inequalities are proposed. The computational results show that the MIP model with valid inequalities is able to provide optimal solutions for the PDLBS problems with up to 30 tasks. To obtain near-optimal solutions for large-sized problems, a MIP-based solution approach is proposed. The proposed approach decomposes the entire MIP model into selection and assignment (SA) and sequencing (SEQ) models. The SA model is an exact relaxation of the MIP model (with valid inequalities) obtained by removing all the sequencing variables and constraints. Hence, SA model also produces an efficient upper bound for the PDLBS problem. The SEQ model, accordingly, aims to find an optimal sequence of tasks subject to the fixed selection and assignment of tasks provided by the SA model. The computational results show that the proposed MIP-based solution approach provides efficient solutions with small optimality gaps for large-sized problems.
暂无评论