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

    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
  • 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(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,
    i.e, the
    eigenvector to the second smallest eigenvalue of the Laplace
    matrix of
    the Graph. In order to obtain a better understanding of
    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
    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