Refine
Language
- English (11)
- Multiple languages (1)
Keywords
- branch-and-cut (3)
- MIP (2)
- Mixed Integer Programming (2)
- chip verification (2)
- constraint programming (2)
- mixed integer programming (2)
- optimization software (2)
- Container terminal (1)
- IP (1)
- Instances (1)
In this article, we present a mathematical model and an algorithm to support one of the central
strategic planning decisions of network operators: How to organize a large number of locations into
an hierarchy of network levels? We propose a mixed-integer program and a Lagrangian relaxation
based algorithm to model and solve this planning task. As one big advantage of this approach, not
only solutions but also worst-case quality gurarantees can be provided. We present a solution for
a G-WiN planning instance of DFN with 759 locations which has been computed in less than 30
minutes and which is (provably) less than 0.5 percent away from optimality.
The UMTS radio network planning problem poses the challenge of designing a cost-effective network that provides users with sufficient coverage and capacity. We describe an optimization model for this problem that is based on comprehensive planning data of the EU project MOMENTUM. We present heuristic mathematical methods for this realistic model, including computational results.
MIPLIB 2003
(2005)
This paper is about the fourth version of the Mixed Integer Programming Library (MIPLIB).
More than 7 years have been past since the last update. Since the focus of the MIPLIB is to provide a concise set of challenging problems, it became again necessary to purge the library from instances that have become too easy due to improvements in optimizers and computing machinery.
The free slots have been filled by 27 new challenging instances. We give an overview of the new problems and present statistical data for all 60 instances included in the MIPLIB 2003.
This paper concerns the problem of operating a landside container exchange area that is serviced by multiple semi-automated rail mounted gantry cranes (RMGs) that are moving on a single bi-directional traveling lane. Such a facility is being built by Patrick Corporation at the Port Botany terminal in Sydney. The gantry cranes are a scarce resource and handle the bulk of container
movements. Thus, they require a sophisticated analysis to achieve near optimal utilization. We present a three stage algorithm to manage the container exchange facility, including the scheduling of cranes, the control of associated short-term container stacking, and
the allocation of delivery locations for trucks and other container transporters. The key components of our approach are a time scale decomposition, whereby an integer program controls decisions across a long time horizon to produce a balanced plan that is fed to a series of short time scale online subproblems, and a highly efficient space-time divisioning of short term storage areas.
A computational evaluation shows that our heuristic can find effective solutions for the planning problem; on real-world data it yields a solution at most 8% above a lower bound on optimal RMG utilization.
In this paper we investigate the performance of several out-of-the box solvers for mixed-integer quadratically constrained programmes (MIQCPs) on an open pit mine production scheduling problem with mixing constraints. We compare the solvers BARON, Couenne, SBB, and SCIP to a problem-specific algorithm on two different MIQCP formulations. The computational results presented show that general-purpose solvers with no particular knowledge of problem structure are able to nearly match the performance of a hand-crafted algorithm.
この論文ではソフトウェア・パッケージSCIP Optimization Suite を紹介し,その3つの構成要素:モデリン グ言語Zimpl, 線形計画(LP: linear programming) ソルバSoPlex, そして,制約整数計画(CIP: constraint integer programming) に対するソフトウェア・フレームワークSCIP, について述べる.本論文では,この3つの 構成要素を利用して,どのようにして挑戦的な混合整数線形計画問題(MIP: mixed integer linear optimization problems) や混合整数非線形計画問題(MINLP: mixed integer nonlinear optimization problems) をモデル化 し解くのかを説明する.SCIP は,現在,最も高速なMIP,MINLP ソルバの1つである.いくつかの例により, Zimpl, SCIP, SoPlex の利用方法を示すとともに,利用可能なインタフェースの概要を示す.最後に,将来の開 発計画の概要について述べる.
In this article, we present a mathematical model and an algorithm to support one of the central
strategic planning decisions of network operators: How to organize a large number of locations into a
hierarchical network? We propose a solution approach that is based on mixed-integer programming and
Lagrangian relaxation techniques. As major advantage, our approach provides not only solutions but
also worst-case quality guarantees. Real-world scenarios with more than 750 locations have been solved
within 30 minutes to less than 1% off optimality.
Branching Rules Revisited
(2004)
Mixed integer programs are commonly solved with linear programming
based branch-and-bound algorithms. The success of the algorithm
strongly depends on the strategy used to select the variable to
branch on.
We present a new generalization called reliability branching of today's
state-of-the-art strong branching and pseudocost branching branching
strategies for linear programming based branch-and-bound algorithms.
After reviewing commonly used branching strategies and performing
extensive computational studies we compare different parameter
settings and show the superiority of our proposed new strategy.
This article introduces constraint integer programming (CIP), which is a novel way to combine constraint programming (CP) and mixed integer programming (MIP) methodologies. CIP is a generalization of MIP that supports the notion of general constraints as in CP. This approach is supported by the CIP framework SCIP, which also integrates techniques for solving satisfiability problems. SCIP is available in source code and free for noncommercial use.
We demonstrate the usefulness of CIP on three tasks. First, we apply the constraint integer programming approach to pure mixed integer programs. Computational experiments show that SCIP is almost competitive to current state-of-the-art commercial MIP solvers. Second, we demonstrate how to use CIP techniques to compute the number of optimal solutions of integer programs. Third, we employ the CIP framework to solve chip design verification problems, which involve some highly nonlinear constraint types that are very hard to handle by pure MIP solvers. The CIP approach is very effective here: it can apply the full sophisticated MIP machinery to the linear part of the problem, while dealing with the nonlinear constraints by employing constraint programming techniques.
This article introduces constraint integer programming (CIP), which is a novel way to combine constraint programming (CP) and mixed integer programming (MIP) methodologies.
CIP is a generalization of MIP that supports the notion of general constraints as in CP.
This approach is supported by the CIP framework SCIP, which also integrates techniques from SAT solving.
SCIP is available in source code and free for non-commercial use.
We demonstrate the usefulness of CIP on two tasks.
First, we apply the constraint integer programming approach to pure mixed integer programs.
Computational experiments show that SCIP is almost competitive to current state-of-the-art commercial MIP solvers.
Second, we employ the CIP framework to solve chip design verification problems, which involve some highly non-linear constraint types that are very hard to handle by pure MIP solvers.
The CIP approach is very effective here:
it can apply the full sophisticated MIP machinery to the linear part of the problem, while dealing with the non-linear constraints by employing constraint programming techniques.