# <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

Lind 400

**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

MINLP problems.**Utilizing strong branching information in convex mixed integer**

nonlinear programs

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

techniques convergence

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*, Optimization

programming

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**

tree problem

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

computation.**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

computation time.**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

solutions.

This is a joint work with C. Bragalli, J. Lee, A. Lodi and P. Toth.**Physarum can solve the shortest path decision problem**

mathematically rigorously

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

rigorously.**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**

and applications

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(10^{12}) 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**

optimization

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

is

typically based on the sign structure of the Fiedler vector,

i.e, the

eigenvector to the second smallest eigenvalue of the Laplace

matrix of

the Graph. In order to obtain a better understanding of

connections

between the spectrum of the Laplacian and separator structures

in the

graph we study graph realizations in Euclidean space obtained

from the

optimal solutions of semidefinite programs that seek to

optimize the

extremal eigenvalues of the Laplacian by redistributing the

mass on

the edges of the graph. We show that not only the geometric

structure

of optimal graph realizations is tightly linked to the

separator

structure of the graph but that in both cases (maximizing

λ_{2}

and minimizing λ_{max}) there even exist optimal

realizations

whose dimension is bounded by the tree width of the graph plus

one.**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