<span class=strong>Poster Session and Reception: 5:00-6:30 </span><br><br/><br/><b>Poster submissions welcome from all participants</b>
Tuesday, November 18, 2008 - 5:00pm - 6:30pm
- Towards a parallel macro partitioning (PMaP) framework
for MINLP problems
Mahdi Namazifar (University of Wisconsin, Madison)
PMaP (Parallel Macro Partitioning Framework) is a parallel
framework for solving large mixed integer programs. PMaP tries
to partition the feasible region of the problem using primal
heuristics and solve the partitions using the available
processors. Initial computational resources suggest that PMaP
has significant promise as a framework capable of bringing many
processors to bear effectively on difficult problems. In this
research we try to investigate opportunities to extend PMaP for
- Utilizing strong branching information in convex mixed integer
Mustafa Kilinc (University of Wisconsin, Madison)
We give some computational experience comparing different types of
strong branching methods for the solution of convex mixed integer
nonlinear programs. Simple cutting planes derived from strong
branching information are introduced and tested.
- On non-convex quadratic programming with box constraints
Samuel Burer (The University of Iowa)
Joint work with Adam N. Letchford.
Non-Convex Quadratic Programming with Box Constraints is a fundamental NP-hard global optimization problem. Recently, some authors have studied a certain family of convex sets associated with this problem. We show that the sets are closely related to the boolean quadric polytope, a fundamental polytope in the field of polyhedral combinatorics.
- MISQP: Mixed-integer sequential quadratic programming
Thomas Lehmann (University of Bayreuth)
Joint work with O. Exler and K. Schittkowski.
MISQP is a new approach for solving possibly nonconvex MINLP
problems. It is
an extention of the well-known SQP method to mixed-integer
programms. A sequence
of mixed-integer quadractic programs which are local
approximations of the original
MINLP determine mixed-integer search directions. The method is
stabilized by a trust
region and in combination with standard outer approximation
can be shown for convex MINLPs. The method is very cheap in
terms of function
evaluation and achieves promising results for nonconvex
black-box problems arising in
the oil industry. MISQP is descriped in detail in Exler O.,
Schittkowksi K. (2007):
A trust region SQP algorithm for mixed integer nonlinear
Letters, Vol 1, No 3, p. 269-280.
Keywords: nonconvex MINLP; mixed integer programming; mixed
integer quadratic programming; MIQP; mixed integer nonlinear programming; MINLP;
numerical algorithms; Outer Approximation
- Exact algorithms for the quadratic linear ordering problem
Angelika Wiegele (Universität Klagenfurt)
The quadratic linear ordering problem naturally generalizes various
optimization problems, such as bipartite crossing minimization or the
betweenness problem, which includes linear arrangement. These
problems have important applications in, e.g., automatic graph drawing
and computational biology. We present a new polyhedral approach to the
quadratic linear ordering problem that is based on a linearization of the
quadratic objective function. Our main result is a reformulation of
the 3-dicycle inequalities using quadratic terms, the resulting
constraints are shown to be face-inducing for the polytope
corresponding to the unconstrained quadratic problem. We exploit this
result both within a branch-and-cut algorithm and within an SDP-based
branch-and-bound algorithm. Experimental results for bipartite
crossing minimization show that this approach clearly
outperforms other methods.
(Joint work with C. Buchheim and L. Zheng.)
- Some challenging mixed integer nonlinear optimization problems
Tamás Terlaky (Lehigh University)
Nonlinear mixed integer optimization has numerous applications in engineering practice.
We present two classes of MINLP problems that arise in engineering practice,
but their solution to proven optimality in size relevant for practice is beyond the
capacity of available MINLP solvers. Both of the following problem classes offer
the possibility to generate test problem suites with increasing problem size.
The first problem class is the optimization of the reloading of nuclear reactor core,
where the physics of the problem is governed by PDE's, whose discretization
combined with the reloading (assignment constraints) provide
a large family of large scale MINP problems.
The second class of problems arise from flood control, where safe dike heights
need to be built at minimal cost while considering the expected risk of flooding.
- Variable neighbourhood search for MINLPs
Giacomo Nannicini (École Polytechnique)
In a recent work we presented a general-purpose heuristic for
(nonconvex) MINLPs based on Variable Neighbourhood Search, Local
Branching, Sequential Quadratic Programming and Branch-and-Bound,
combining several commercial solvers together. That method, which we
called RECIPE, turned out to be very effective on the majority of the
test instances, finding solutions at least as good as the best known
optima for 55% of the MINLPLib. We analyse the computational
performance of RECIPE when relying on open-source solvers only.
Moreover, we study the effect of iiteratively applying a bound
tightening phase throughout the algorithm.
- Real-time optimization, control and optimal allocation
Jaroslav Pekar (Honeywell)
The importance, popularity and the number of applications of advanced
algorithms in industrial control is rapidly growing. This is given by
the fact that the smart control solutions can improve the efficiency
of processes which usually results in economical benefits. Most of the
advanced solutions formulate the problem as optimization task. From the
huge number of possible fields, we would like to mention the following
three areas in this presentation: optimal allocation problem; real-time
control and optimal design in distributed control systems.
- Exact and heuristic algorithms for the Euclidean Steiner
Jon Van Laarhoven (The University of Iowa)
The Euclidean Steiner tree problem (ESTP) asks for a tree of
minimal length spanning a set of vertices in ℝd
(terminal points), while allowing for the addition of
auxiliary points (Steiner points). The ESTP has been
extensively studied for dimension d=2, but is poorly
understood for d>2. Our work is two-fold. First, we present
a heuristic for the Euclidean Steiner tree problem in ℝd
for d ≥2. The algorithm utilizes the Delaunay
triangulation to generate candidate Steiner points for
insertion, but unlike other ESTP heuristics relying upon
Delaunay triangulation, inserts Steiner points
probabilistically into Delaunay triangles to achieve different
trees on subsets of terminal nodes. Second, we derive new
geometric exclusion criteria for d≥2 that enhance the
exact algorithm of Smith (1992). These new geometric criteria
promote fathoming higher in the branch-and-bound tree than the
length-based criterion used by Smith and also require less
- An algorithm for solving nonlinear optimization problems with
linear constraints and binary variables
Kien Ming Ng (National University of Singapore)
Joint work with Walter Murray (Stanford University).
A smoothing approach is proposed to solve nonlinear optimization
problems with linear constraints and binary variables. Such problems
may be transformed to that of finding a global optimum of a problem in
continuous variables. The proposed algorithm involves convexifying the
transformed problem with an appropriate smoothing function, and then
solving a sequence of subproblems whose solutions form a trajectory that
leads to a solution. Computational results of applying the algorithm to
problems taken from the literature and new test problems with known
optimal solutions are shown, and they indicate that the proposed
approach is able to obtain good quality solutions within reasonable
- Water network design by MINLP
Claudia D'Ambrosio (Università di Bologna)
The optimal design of a Water Distribution Network (WDN) is a real-world
optimization problem known and studied since the seventies. Several
approaches has been proposed, for example, heuristics, metaheuristics, Mixed
Integer Linear Programming models and global optimization methods. Despite
this interest, it is still an open problem, since it is very hard to find
good solutions for even medium sized instances. In this work we propose a
non-convex Mixed Integer Non-Linear Programming (MINLP) model that accurately
approximates the WDN problem, and we solve it with an ad-hoc modified
branch-and-bound for MINLPs. This was possible thanks to the use of the
open-source MINLP solver Bonmin. Computational results are presented on
literature instances and new instances based on data of medium-sized Italian
cities. Even for the bigger instances, we are able to find good feasible
This is a joint work with C. Bragalli, J. Lee, A. Lodi and P. Toth.
- Physarum can solve the shortest path decision problem
Isamu Ohnishi (Hiroshima University)
Physarum polycephalum is an amoeba-like organism that exhibits
path-finding behavior in a maze. Its body contains a tube network by
means of which nutrients and signals circulate through the body in
effective manner. Physarum solver is a model equation which was
proposed by Tero et al.. It describes the adaptive dynamics of a
transport network of the true slime mold Physarum polycephalum.
However, according to the results of numerical simulations, it can
also used for path-finding in a complicated network. In this paper, we
prove mathematically rigorously for two specified vertices s, t on the
same face of any planar graph Physarum solver can find the shortest
s-t path. In other words, we give a rigorous proof of the fact that
the equilibrium point corresponding to the shortest path is globally
asymptotically stable for Physarum solver. As telling from the
mathematically technical point of view, it is a very interesting point
that we prove the gllobally asymptotical stability without using usual
Lyapunov function, which is defined globally in the whole domain.
Instead of this, we use a kind of local Lyapunov function to operate
a graph under consideration on which Physarum solver is defined. From
the viewpoint of the dynamical system, such an operation of graph is a
kind of reduction of the system to an inertial manifold. We make the
reduction of the system by using of ëxponential tracking property of
Physarum solver. This property is proved by our local Lyapunov
function. As telling about an application of Physarum solver, they
have attempted to apply Physarum solver to navigation system of road
map. In fact, Physarum solver has found the shortest path connecting
between Seattle and Houston admirably. It is, therefore, meaningful
very much from the viewpoint of application to verify that Physarum
solver solves the shortest path decision problem mathematically
- New convex relaxations for quadratic assignment problems
Jiming Peng (University of Illinois at Urbana-Champaign)
Joint work with X. Li, IESE, U. Illinois and H. Mittelmann, ASU.
Quadratic assignment problems (QAPs) are known to be among the
hardest discrete optimization problems. Recent study shows that even
obtaining a strong lower bound for QAPs is a computational
challenge. In this paper, we first introduce a new mechanism of constructing convex relaxations
of QAPs based on various matrix splitting schemes. Then we introduce a new class of mappings, the so-called symmetric mappings
that can be used to derive strong cuts for the proposed relaxation model. The bounds based on the new models are comparable to the strongest bounds in the literature. Experimental results show that strong bounds for large scale QAPs can be obtained.
- Linear programs with complementarity constraints: Algorithms
John Mitchell (Rensselaer Polytechnic Institute)
Joint work with Jing Hu and Jong-Shi Pang.
Linear programs with complementarity constraints have many applications in practice. Perhaps the best known are formulations of bilevel linear programming problems and of nonconvex quadratic programming problems. We discuss other applications, including inverse convex quadratic programming and order statistics. In addition, we outline a logical Benders decomposition method for these problems that finds a global optimum if it exists, and which can verify unboundedness or infeasibility as appropriate.
- Triangles, envelopes, and nonconvex quadratic programming
Jeff Linderoth (University of Wisconsin, Madison)
In this work, we derive the convex and concave envelope of a simple bilinear function over a triangular region. We demonstrate that these envelopes form a significantly tighter relaxation that the well-known McCormick envelopes and further show that the functions are second-order cone representable. Possible branching schemes are discussed and computational results are reported.
- Direct numerical methods for mixed-integer optimal control problems
Sebastian Sager (Ruprecht-Karls-Universität Heidelberg)
Optimal control problems involving time-dependent decisions from a finite
set have gained much interest lately, as they occur in practical
applications with a high potential for optimization. Typical examples are
the choice of gears in transport or separation processes involving valves
to switch inflow/outflow locations between trays or columns. We present
relaxation and convexification based rounding strategies for direct
methods of optimal control such that the resulting trajectory fulfills
constraints and reaches the objective function value of any (and in
particular the optimal) relaxed solution up to a certain tolerance. We
show that this tolerance depends on the control discretization grid, in
other words, that the rounded solution will be arbitrarily close to the
relaxed one, if only the underlying grid is chosen fine enough. This is
even true for a finite number of switches, and holds for the linear as
well as for the nonlinear case, involving path and control constraints.
Examples will be supplied to illustrate the procedure.
- HIPO: A non-linear mixed integer constrained optimization algorithm for treatment planning in brachytherapy
Andreas Karabis (PI Medical Ltd)
Joint work with Stavroula Giannouli (Pi Medical) and Dimos
Baltas (Klinikum Offenbach GmbH, Germany).
HIPO (Hybrid Inverse Planning and Optimization) is a general, state-of-the-art treatment planning optimization tool with inverse planning capabilities for interstitial template based brachytherapy. HIPO was presented in 2005 and the first commercial release was launched in 2007. It is used in more than 30 clinics around the world. An improved version is presented here, able to take into account clinical recommendations as soft & hard constrains.
During the template-based brachytherapy treatment procedure, a perforated template is fixed on patient’s body and needles are placed -through the holes- inside patient’s body, penetrating the tumour. Within the needles, an irradiating source is stepping. The total dose distribution in the tumour, the surrounding organs and tissue, is a function of the times (dwell times) that the source is spending at each position. The main purpose of planning is to irradiate the target while protecting the surrounding healthy tissues.
The problem that the planer has to solve, is to define the optimal positions (binary variables) of a predefined number of catheters on the template, and then to optimize the dose distribution by adapting the dwell times (continuous variables). Typical numbers of template holes and required catheters can easily result to O(1012) possible combinations. This problem can be formulated as a mixed integer non-linear programming (MINLP) problem, where each combination requires the solution of a continuous nonlinear optimization problem. Furthermore, the clinical requirements that the planers are typically following (e.g. GEC-ESTRO recommendations) can be handled as soft or hard constrains.
HIPO is giving a near optimal solution in relatively short time (typically 0.5-5min), convenient for real-time planning in the operation room. A hybrid algorithm, based on Simulated Annealing and a problem-specific, deterministic heuristic, is used for the binary optimization problem of catheter positioning. The problem-specific heuristic is incorporating expert knowledge. The continuous dose optimization for each set up of the catheters is solved by the standard LBFGS algorithm.
- Experimental investigations in non-linear matroid
David Haws (University of California)
We consider the problem of optimizing a balancing function over matroid bases with defined weightings. Recently, polynomial time algorithms were shown to exist for non-linear matroid optimization when sufficient conditions were placed on the weightings of the matroid bases, or on the balancing function. We present new algorithms and heuristics for non-linear matroid optimization and explore their practical efficiency. We provide experimental data of our algorithms. This is work in progress.
- Graph realizations corresponding to
optimized extremal eigenvalues of the Laplacian
Christoph Helmberg (Technische Universität Chemnitz-Zwickau)
In spectral graph partitioning heuristics the initial partition
typically based on the sign structure of the Fiedler vector,
eigenvector to the second smallest eigenvalue of the Laplace
the Graph. In order to obtain a better understanding of
between the spectrum of the Laplacian and separator structures
graph we study graph realizations in Euclidean space obtained
optimal solutions of semidefinite programs that seek to
extremal eigenvalues of the Laplacian by redistributing the
the edges of the graph. We show that not only the geometric
of optimal graph realizations is tightly linked to the
structure of the graph but that in both cases (maximizing
and minimizing λmax) there even exist optimal
whose dimension is bounded by the tree width of the graph plus
- Computer algebra, combinatorics, and complexity:
Hilbert's Nullstellensatz and NP-complete problems
Systems of polynomial equations over algebraically
closed fields can be used to characterize NP-complete problems.
Via Hilbert's Nullstellensatz and a sequence of large-scale
sparse linear algebra computations, we can construct a
certificate of infeasibility: a certificate for a no instance
of the underlying NP-complete problem. Using the Nullstellensatz
Linear Algebra (NulLA) algorithm, we successfully solved
non-3-colorable graph instances with thousands of nodes and tens
of thousands of edges.
- Convex relaxations of non-convex MIQCP
Anureet Saxena (Axioma Inc.)
same abstract as the 11/18 talk