90-08 Computational methods
Refine
Year of publication
Document Type
- ZIB-Report (17)
Language
- English (17)
Has Fulltext
- yes (17)
Is part of the Bibliography
- no (17)
Keywords
- branch-and-bound (5)
- mixed integer programming (4)
- mixed-integer programming (3)
- Branch-and-Bound (2)
- Mixed Integer Programming (2)
- branching rule (2)
- exact computation (2)
- strong branching (2)
- Branching Rules (1)
- CP (1)
Presolving attempts to eliminate redundant information from the problem formulation and simultaneously tries to strengthen the formulation. It can be very effective and is often essential for solving instances. Especially for mixed integer programming problems, fast and effective presolving algorithms are very important. In this paper, we report on three new presolving techniques. The first method searches for singleton continuous columns and tries to fix the corresponding variables. Then we present a presolving technique which exploits a partial order of the variables to induce fixings. Finally, we show an approach based on connected components in graphs. Our computational results confirm the profitable use of the algorithms in practice.
Branching rules are an integral component of the branch-and-bound algorithm typically used to solve mixed-integer programs and subject to intense research. Different approaches for branching are typically compared based on the solving time as well as the size of the branch-and-bound tree needed to prove optimality. The latter, however, has some flaws when it comes to sophisticated branching rules that do not only try to take a good branching decision, but have additional side-effects. We propose a new measure for the quality of a branching rule that distinguishes tree size reductions obtained by better branching decisions from those obtained by such side-effects. It is evaluated for common branching rules providing new insights in the importance of strong branching.
We report numerical results for SBmethod --- a publically available implementation of the spectral bundle method --- applied to the 7$^{th}$ DIMACS challenge test sets that are semidefinite relaxations of combinatorial optimization problems. The performance of the code is heavily influenced by parameters that control bundle update and eigenvalue computation. Unfortunately, no mathematically sound guidelines for setting them are known. Based on our experience with SBmethod, we propose heuristics for dynamically updating the parameters as well as a heuristc for improving the starting point. These are now the default settings of SBmethod Version 1.1. We compare their performance on the DIMACS instances to our previous best choices for Version 1.0. SBmethod Version 1.1 is also part of the independent DIMACS benchmark by H.~Mittelmann. Based on these results we try to analyze strengths and weaknesses of our approach in comparison to other codes for large scale semidefinite programming.
Finding conflict-free wavelength assignments with a minimum number of required conversions for a routing of the lightpaths is one of the important tasks within the design of all-optical networks. We consider this problem in multi-fiber networks with different types of WDM systems. We give a detailed description of the problem and derive its theoretical complexity. For practical application, we propose several sequential algorithms to compute appropriate wavelength assignments. We also perform computational experiments to evaluate their performance. For the iterative algorithms, we identify characteristic patterns of progression. Two of these algorithms qualify for application in practice.
In this article we investigate methods to solve a fundamental task in gas transportation, namely the validation of nomination problem: Given a gas transmission network consisting of passive pipelines and active, controllable elements and given an amount of gas at every entry and exit point of the network, find operational settings for all active elements such that there exists a network state meeting all physical, technical, and legal constraints.
We describe a two-stage approach to solve the resulting complex and numerically difficult mixed-integer non-convex nonlinear feasibility problem. The first phase consists of four distinct algorithms facilitating mixed-integer linear, mixed-integer nonlinear, reduced nonlinear, and complementarity constrained methods to compute possible settings for the discrete decisions. The second phase employs a precise continuous nonlinear programming model of the gas network. Using this setup, we are able to compute high quality solutions to real-world industrial instances whose size is significantly larger than networks that have appeared in the literature previously.
Fast computation of valid linear programming (LP) bounds serves as an
important subroutine for solving mixed-integer programming problems
exactly. We introduce a new method for computing valid LP bounds designed
for this application. The algorithm corrects approximate LP dual solutions
to be exactly feasible, giving a valid bound. Solutions are repaired by
performing a projection and a shift to ensure all constraints are
satisfied; bound computations are accelerated by reusing structural
information through the branch-and-bound tree. We demonstrate this method
to be widely applicable and faster than solving a sequence of exact LPs.
Several variations of the algorithm are described and computationally
evaluated in an exact branch-and-bound algorithm within the mixed-integer
programming framework SCIP.
It has been shown that any 9 by 9 Sudoku puzzle must contain at least 17 clues to have a unique solution. This paper investigates the more specific question: given a particular completed Sudoku grid, what is the minimum number of clues in any puzzle whose unique solution is the given grid? We call this problem the Minimum Sudoku Clue Problem (MSCP). We formulate MSCP as a binary bilevel linear program, present a class of globally valid inequalities, and provide a computational study on 50 MSCP instances of 9 by 9 Sudoku grids. Using a general bilevel solver, we solve 95\% of instances to optimality, and show that the solution process benefits from the addition of a moderate amount of inequalities. Finally, we extend the proposed model to other combinatorial problems in which uniqueness of the solution is of interest.