The selection of branching variables is a key component of branch-and-bound algorithms for solving mixed-integerprogramming (MIP) problems since the quality of the selection procedure is likely to have a significant ...
详细信息
The selection of branching variables is a key component of branch-and-bound algorithms for solving mixed-integerprogramming (MIP) problems since the quality of the selection procedure is likely to have a significant effect on the size of the enumeration tree. State-of-the-art procedures base the selection of variables on their “LP gains”, which is the dual bound improvement obtained after branching on a variable. There are various ways of selecting variables depending on their LP gains. However, all methods are evaluated empirically. In this paper we present a theoretical model for the selection of branching variables. It is based upon an abstraction of MIPs to a simpler setting in which it is possible to analytically evaluate the dual bound improvement of choosing a given variable. We then discuss how the analytical results can be used to choose branching variables for MIPs, and we give experimental results that demonstrate the effectiveness of the method on MIPLIB 2010 “tree” instances where we achieve a \(5\%\) geometric average time and node improvement over the default rule of SCIP, a state-of-the-art MIP solver.
We investigate the problem of scheduling a sequence of cars to be placed on an assembly line. Stations, along the assembly line install options (e.g. air conditioning), but have limited capacities, and hence cars requ...
详细信息
We investigate the problem of scheduling a sequence of cars to be placed on an assembly line. Stations, along the assembly line install options (e.g. air conditioning), but have limited capacities, and hence cars requiring the same options need to be distributed far enough apart. The desired separation is not always feasible, leading to an optimisation problem that minimises the violation of the ideal separation requirements. In order to solve the problem, we use a large neighbourhood search (LNS) based on mixed integer programming (MIP). The search is implemented as a sliding window, by selecting overlapping subsequences of manageable sizes, which can be solved efficiently. Our experiments show that, with LNS, substantial improvements in solution quality can be found.
In the public utility and commercial fuel industries, commodities from multiple supply sources are sometimes blended before use to reduce costs and assure quality. A. typical example of these commodities is the fuel c...
详细信息
In the public utility and commercial fuel industries, commodities from multiple supply sources are sometimes blended before use to reduce costs and assure quality. A. typical example of these commodities is the fuel coal used in coal fired power plants. The diversity of the supply sources for these plants makes the planning and scheduling of fuel coal logistics difficult, especially for a power company that has more than one power plant. This study proposes a mixed integer programming model that provides planning and scheduling of coal imports from multiple suppliers for the Taiwan Power Company. The objective is to minimize total inventory cost by minimizing procurement cost, transportation cost and holding cost. Constraints on the system include company procurement policy, power plant demand, harbor unloading capacity, inventory balance equations, blending requirement, and safety stock. An example problem is presented using the central coal logistics system of the Taiwan Power Company to demonstrate the validity of the proposed model.
作者：
Hua, ZSHuang, FHUSTC
Sch Management Dept Informat Management & Decis Sci Anhua 230026 Peoples R China
To effectively reduce the search space of GAs on large-scale M I P problems, this paper proposed a new variable grouping method based on Structure properties of a problem. Taking the capacity expansion and technology ...
详细信息
To effectively reduce the search space of GAs on large-scale M I P problems, this paper proposed a new variable grouping method based on Structure properties of a problem. Taking the capacity expansion and technology selection problem as a typical example, this method groups problem's decision variables over time period and machine line. Based on this new variable grouping method, we developed a variable-grouping based genetic algorithm according to problem's structure properties (VGGA-S). We tested the performance of VGGA-S by applying it on the capacity expansion and technology selection problem. Numerical experiments suggested that, VGGA-S Outperforms the standard GA and variable-grouping based GAs without considering problem's structure properties, both on computation time and solution quality. Although VGGA-S is proposed based on structure properties of a specific MIP problem, it is a general optimization algorithm and theoretically applicable to other large scale MIP problems. (c) 2005 Elsevier Inc. All rights reserved.
This paper describes the problem of rostering a workforce so as to optimise a weighted sum of three criteria while satisfying several constraints. The rostering entailed deciding on a pattern of working days and break...
详细信息
This paper describes the problem of rostering a workforce so as to optimise a weighted sum of three criteria while satisfying several constraints. The rostering entailed deciding on a pattern of working days and breaks over a period of (typically) one year. Demand had to meet 24 hours each day and 365 days each year. It was possible to formulate this problem as a mixedinteger program and, with some experimentation, solve it using an 'off the shelf' linear programming package. The results obtained are compared with rosters the client now uses.
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.
In apparel manufacturing, cut pieces produced by the cutting process are a key input work-in-process (WIP) to the bottleneck sewing process. However, an excessive inventory of cut pieces not only requires extra storag...
详细信息
In apparel manufacturing, cut pieces produced by the cutting process are a key input work-in-process (WIP) to the bottleneck sewing process. However, an excessive inventory of cut pieces not only requires extra storage space but also creates difficulties with shop floor control. This study determines the ideal cutting times of fabric lays by minimising the cut piece inventory under the constraint that sufficient cut pieces are produced in time to satisfy the bottleneck usage. This study proposes a mixed integer programming (MIP) model and a heuristic method to solve the problem. The solutions for most test instances of the problem that are calculated by the heuristic method are not as good as those by the MIP solver;however, the heuristic method computation times are negligible. The experiments show that the MIP model's efficiency significantly improves by starting from an initial solution provided by the proposed heuristic method.
The cost effective R&D strategy is required especially for large-scale technologies because their development demands a large amount of investment in general. A mixed integer programming model was developed for th...
详细信息
The cost effective R&D strategy is required especially for large-scale technologies because their development demands a large amount of investment in general. A mixed integer programming model was developed for the optimum technology development strategy in the field of energy systems. The module of the technology development process in the model is based on GERT (Graphical Evaluation and Review Technique). In the module, a target technology is broken down into many elemental technologies. Usually several target technologies are involved for the evaluation of technology development strategy of one field and some of the elemental technologies are used common to a number of target technologies. Since elemental technologies are explicitly modeled, their spillover effects are necessarily evaluated in this model analysis. The proposed method was applied to the evaluation of the development strategy of four types of IGCC (Integrated coal Gasification Combined Cycle) technologies which have different levels of thermal efficiencies. The total investment on both their R&D and practical use is optimized under the constraint of meeting a certain exogenous scenario of electricity demand. The evaluation results include the optimum additional investment allocation among the developments of various elemental technologies;developments of integration technology for IGCC-43%, IGCC-55% and IGCC-48%, coal gasification technology, oxide dispersion strengthened superalloy technology for the gas turbine blade and vane, ceramic matrix composite technology for the gas turbine blade, dry sulfur-removal technology, etc. are cost-effective. (C) 2004 Elsevier Ltd. All rights reserved.
This study deals with the school timetabling problem for the case of Greek high schools. At first, the problem is modelled as a mixed integer programming problem for ten instances referring to Greek high schools. Then...
详细信息
This study deals with the school timetabling problem for the case of Greek high schools. At first, the problem is modelled as a mixed integer programming problem for ten instances referring to Greek high schools. Then, the problem is coded using the MathProg programming language. Two different linear programming solvers are employed, Gurobi and CPLEX, to solve the problem for the instances at hand. Two methodologies are proposed. The first one deals with the problem utilising a model that includes all hard and soft constraints, called "monolithic" model, while the second one is based on a decomposition of the problem to six sub-problems. It should be stated that Gurobi and CPLEX did not produced satisfactory results when the monolithic model was the case. Computational results demonstrate the effectiveness of the second proposed methodology, as optimal solutions or new lower bounds were found. In addition, the results produced by mixed integer programming are compared with the best so far published results, obtained by two Nature Inspired algorithms namely Particle Swarm Optimization and Cat Swarm Optimization.
Multi-cluster tools are automated equipment which is increasingly used in semiconductor manufacturing. The scheduling of multi-cluster tools is much more challenging than single-cluster tools due to multi-robot coordi...
详细信息
Multi-cluster tools are automated equipment which is increasingly used in semiconductor manufacturing. The scheduling of multi-cluster tools is much more challenging than single-cluster tools due to multi-robot coordination and increasing chambers. In this paper, we develop a mixed integer programming (MIP) model which manages to formulate the multi-robot coordination for cyclic scheduling of multi-cluster tools. Three reformulations of the model are implemented: 1) linearization;2) eliminating integer variables;and 3) tightening constraints. The first reformulation is designed to make the MIP model solvable by commercial solvers while the other two are intended for promoting computational efficiency which is critical when chambers increase. The proposed model can meet various practical scheduling requirements such as dual-armed robots, wafer residency time constraints, parallel and reentrant processes in multi-cluster tools. Experimental results demonstrate the efficiency of the proposed method.
暂无评论