We describe FATCOP, a new parallel mixedinteger program solver written in PVM. The implementation uses the Condor resource management system to provide a virtual machine composed of otherwise idle computers. The solv...
详细信息
We describe FATCOP, a new parallel mixedinteger program solver written in PVM. The implementation uses the Condor resource management system to provide a virtual machine composed of otherwise idle computers. The solver differs from previous parallel branch-and-bound codes by implementing a general purpose parallel mixed integer programming algorithm in an opportunistic multiple processor environment, as opposed to a conventional dedicated environment. It shows how to make effective use of resources as they become available while ensuring the program tolerates resource retreat. The solver performs well on test problems arising from real applications and is particularly useful for solving long running hard mixed integer programming problems.
This paper puts forward an integrated optimisation model that combines three distinct problems, namely berth allocation, quay crane assignment, and quay crane scheduling that arise in container ports. Each one of thes...
详细信息
This paper puts forward an integrated optimisation model that combines three distinct problems, namely berth allocation, quay crane assignment, and quay crane scheduling that arise in container ports. Each one of these problems is difficult to solve in its own right. However, solving them individually leads almost surely to sub-optimal solutions. Hence, it is desirable to solve them in a combined form. The model is of the mixed-integerprogramming type with the objective being to minimize the tardiness of vessels and reduce the cost of berthing. Experimental results show that relatively small instances of the proposed model can be solved exactly using CPLEX. Large scale instances, however, can only be solved in reasonable times using heuristics. Here, an implementation of the genetic algorithm is considered. The effectiveness of this implementation is tested against CPLEX on small to medium size instances of the combined model. Larger size instances were also solved with the genetic algorithm, showing that this approach is capable of finding the optimal or near optimal solutions in realistic times.
This paper represents an integration of mixed integer programming (MIP) and Constraint Logic programming (CLP) which, like MIP, tightens bounds rather than adding constraints during search. The integrated system combi...
详细信息
This paper represents an integration of mixed integer programming (MIP) and Constraint Logic programming (CLP) which, like MIP, tightens bounds rather than adding constraints during search. The integrated system combines components of the CLP system ECLiPSe [7] and the MIP system CPLEX [5], in which constraints can be handled by either one or both components. Our approach is introduced in three stages. Firstly, we present an automatic transformation which maps CLP programs onto such CLP programs that any disjunction is eliminated in favour of auxiliary binary variables. Secondly, we present improvements of this mapping by using a committed choice operator and translations of pre-defined non-linear constraints. Thirdly, we introduce a new hybrid algorithm which reduces the solution space of the problem progressively by calling finite domain propagation of ECLiPSe as well as dual simplex of CPLEX. The advantages of this integration are illustrated by efficiently solving difficult optimisation problems like the Hoist Scheduling Problem [23] and the Progressive Party Problem [27].
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.
This paper reports on the fifth version of the mixed integer programming Library. The MIPLIB 2010 is the first miplib release that has been assembled by a large group from academia and from industry, all of whom work ...
详细信息
This paper reports on the fifth version of the mixed integer programming Library. The MIPLIB 2010 is the first miplib release that has been assembled by a large group from academia and from industry, all of whom work in integerprogramming. There was mutual consent that the concept of the library had to be expanded in order to fulfill the needs of the community. The new version comprises 361 instances sorted into several groups. This includes the main benchmark test set of 87 instances, which are all solvable by today's codes, and also the challenge test set with 164 instances, many of which are currently unsolved. For the first time, we include scripts to run automated tests in a predefined way. Further, there is a solution checker to test the accuracy of provided solutions using exact arithmetic.
作者：
Van Engeland, JensBelien, JeroenKatholieke Univ Leuven
Ctr Econ & Corp Sustainabil Fac Econ & Business Campus BrusselsWarmoesberg 26 B-1000 Brussels Belgium Katholieke Univ Leuven
Ctr Informat Management Modeling & Simulat Fac Econ & Business Campus BrusselsWarmoesberg 26 B-1000 Brussels Belgium Katholieke Univ Leuven
Res Ctr Operat Management Fac Econ & Business Campus LeuvenNaamsestr 69 B-3000 Leuven Belgium
Environmental considerations and corresponding legislation cause a shift from waste management to materials management, requiring efficient collection of these flows. This paper develops a model for building tactical ...
详细信息
Environmental considerations and corresponding legislation cause a shift from waste management to materials management, requiring efficient collection of these flows. This paper develops a model for building tactical waste collection schemes in which a set of capacitated vehicles visits a set of customers during a given time period. Each vehicle must visit the disposal facility to discharge the waste after each customer visit. This is motivated by the fact that the waste of each customer has to be weighed at the disposal facility. The goal is to find a set of routes for each vehicle that satisfy both the demand and the frequency constraints and minimize the total cost. Since a state-of-the-art solver could not find a solution with a reasonable gap within an acceptable time limit, a column generation and a mixed integer programming-based heuristic are proposed. While the mixed integer programming-based heuristic outperforms the column generation heuristic in terms of solution quality, the lower bound provided by column generation allows to prove the small optimality gaps of the solutions obtained. Moreover, by applying both heuristics on instances derived from real-life data, they proved to be capable of finding good quality solutions in small computation times.
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 pseudoconvexity/strong pseudo-concavity and separability assumptions only.
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.
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.
During the last decade, significant progress has been made in solving the Protein Threading Problem (PTP). However, all previous approaches to PTP only perform global sequence-structure alignment. This obvious limitat...
详细信息
During the last decade, significant progress has been made in solving the Protein Threading Problem (PTP). However, all previous approaches to PTP only perform global sequence-structure alignment. This obvious limitation is in clear contrast with the "world of sequences", where local sequence-sequence alignments are widely used to find functionally important regions in families of proteins. This paper presents a novel approach to PIP which allows to align a part of a protein structure onto a protein sequence in order to detect local similarities. We show experimentally that such local sequence-structure alignments improve the quality of the prediction. Our approach is based on mixed integer programming (MIP) which has been shown to be very successful in this domain. We describe five MIP models for local sequence-structure alignments, compare and analyze their performances by using ILOG CPLEX 10 solver on a benchmark of proteins. (C) 2010 Elsevier B.V. All rights reserved.
暂无评论