This is a summary of the author's PhD thesis supervised by Andrea Lodi and Paolo Toth and defended on 16 April 2009 at the UniversitA di Bologna. The thesis is written in English and is available from the author u...
详细信息
This is a summary of the author's PhD thesis supervised by Andrea Lodi and Paolo Toth and defended on 16 April 2009 at the UniversitA di Bologna. The thesis is written in English and is available from the author upon request. This work is focused on mixed integer programming (MIP). In particular, the first part of the thesis deals with general purpose cutting planes, which are probably the key ingredient behind the success of the current generation of MIP solvers. The second part is instead focused on the heuristic and exact exploitation of integerprogramming techniques for hard combinatorial optimization problems in the context of routing applications.
Recently, new models and heuristics for exploiting quantity discounts have been proposed that are applicable in classical purchasing as well as in an e-business environment and can be implemented as part of an advance...
详细信息
Recently, new models and heuristics for exploiting quantity discounts have been proposed that are applicable in classical purchasing as well as in an e-business environment and can be implemented as part of an advanced planning system. These models can now handle both the single- and multi-item case with fixed cost to be shared among several products ordered at the same point in time from a single supplier. Furthermore, the supplier selection problem is addressed, i.e., how to best exploit quantity discounts over time offered by several suppliers. Last but not least, additional constraints on the buyer's or on the supplier's side may be included. While so far only purpose-built heuristics have been proposed for this generalized problem, we present a linear mixed integer programming (MIP) model, which not only represents the all-units discount but also the incremental discount case. Furthermore, the objective function chosen resolves (former) conflicts among proponents of a purely cost oriented and a cash flow oriented modeling approach. Computational tests show that our model yields near optimal solutions within a given CPU time limit by making use of a standard MIP solver.
In a recent paper some duality results were proved for a pair of nonsymmetric and nonlinear mixed integer programming problems under pseudo-convexity/pseudo-concavity, separability and an additional feasibility assump...
详细信息
In a recent paper some duality results were proved for a pair of nonsymmetric and nonlinear mixed integer programming problems under pseudo-convexity/pseudo-concavity, separability and an additional feasibility assumption. In this note the same results have been obtained under strong pseudo-convexity/strong pseudo-concavity and separability assumptions only. [ABSTRACT FROM AUTHOR]
Construction site layout planning, the arrangement of temporary facilities and equipment on site, is a fundamental part of construction preparation. In construction, the operation of tower cranes has a great impact on...
详细信息
Construction site layout planning, the arrangement of temporary facilities and equipment on site, is a fundamental part of construction preparation. In construction, the operation of tower cranes has a great impact on construction process execution and preparation costs. Therefore, tower cranes should be chosen and placed such that they enable smooth construction processes at minimal cost. Since the majority of loads on site are transported either from or to a storage area, the transport routes taken between tower cranes and storage areas have a high impact. This paper presents a mathematical model that computes cost-optimal positions for both tower cranes and storage areas. The model consists of two linked mixedinteger programs, allowing for the detailed quality assessment of the obtained solutions. Time dependency is considered by subdividing the construction process into several construction phases. Conditions on site and construction elements can be retrieved from a building information model. Particular advantages of our approach include the close approximation of complex shapes via convex hulls. Available positions on site are represented by a fine grid and calculated during runtime, which allows for freer placement instead of restricting to a fixed number of possible locations given as input. Using mixed integer programming offers tremendous modeling possibilities and a rigorous quality guarantee for the obtained solutions. In contrast to existing heuristic approaches, the returned solutions are provably optimal up to the chosen optimality gap. A case study is provided to demonstrate the practical applicability of the proposed model.
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.
This paper addresses the question of decomposing an infinite family of rational polyhedra in an integer fashion. It is shown that there is a finite subset of this family that generates the entire family. Moreover, an ...
详细信息
This paper addresses the question of decomposing an infinite family of rational polyhedra in an integer fashion. It is shown that there is a finite subset of this family that generates the entire family. Moreover, an integer analogue of Caratheodory's theorem carries over to this general setting. The integer decomposition of a family of polyhedra has some applications in integer and mixed integer programming, including a test set approach to mixed integer programming.
Unit commitment problem is a complex decision-making process which involves the scheduling of generators over a set of time periods to satisfy system load demand, water demand, system reliability, operational, and sec...
详细信息
Unit commitment problem is a complex decision-making process which involves the scheduling of generators over a set of time periods to satisfy system load demand, water demand, system reliability, operational, and security constraints. Mathematically, this is a nonlinear, nonconvex, high dimensional, and large-scale optimization problem over mixedinteger variables. Additionally, for a short-term unit commitment problem such as hourly or daily scheduling of generators, the operator needs to run the model in realtime. The operator should have immediate access to information concerning which units should be operated when emergency situations arise or how to schedule around planned maintenance of units. mixed integer programming (MIP) model is developed to solve the unit commitment problem. The MIP model developed in this study consists of three sub-models: PLANT-DY-W, PLANT-GO-W, and PLANT-ST-W. It provides generation control tool that regulates the hydropower system while improving powerplants efficiency. Also, it automates and improves the unit schedule process for the powerplants. To demonstrate the capabilities of the unit commitment models a case study was carried out on a hydropower system in Lower Colorado River Basin.
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.
Based on several existing literatures that use mixed integer programming (MIP) to solve parallel machine scheduling problems, this study tests and compares three MIP models. Each order has its own ready date, due date...
详细信息
ISBN:
(纸本)9781509036653
Based on several existing literatures that use mixed integer programming (MIP) to solve parallel machine scheduling problems, this study tests and compares three MIP models. Each order has its own ready date, due date and processing time. The completion time of the order cannot over the its due date. If not, penalties for tardiness will occur. Formulation 1 used in immediate-precedence variables [1]. Formulation 2 is an improved version of immediate-precedence variables original proposed by [2]. Formulation 3 used linear ordering variables[1]. The results reveal that Formulation 2 has better computational performance than other does.
For many decades, solving the optimal architectural layout design is unattainable for the reasonable problem sizes. Architects have to settle foil acceptable layouts instead of the favourable optimal solution. With to...
详细信息
ISBN:
(纸本)1402034601
For many decades, solving the optimal architectural layout design is unattainable for the reasonable problem sizes. Architects have to settle foil acceptable layouts instead of the favourable optimal solution. With today technologies, various optimization techniques have been used to alleviate the optimal search according to diversified goals. This paper formulates the optimal architectural layout design as the multiobjective mixed integer programming model solved by the MIP solver. The main idea is to capture functional constraints, dimensional constraints and the objective function using only linear formulae with binary variables. Functional constraints are the connectivities, the unused grid cells, the fixed room location, the boundary and the fixed border location while dimension constraints are the non-intersecting, the overlapping, the length and the ratio constraints. The objective function is designed to minimize the absolute distance among rooms and maximize room spaces. Due to the nonlinearity of area computation, the linear approximation of width and height constraints have been utilized. Architects can control these different objectives within the model. By specifying the rigid restriction and the time limits, the problem can be solved within a reasonable amount of time.
暂无评论