Applications – Science and Engineering

Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes

  • Miguel F. Anjos
  • Anthony Vannelli
    • Categories Facility Planning and Design, Semi-definite Programming, VLSI layout Tags , , , ,

    This paper is concerned with the single-row facility layout problem (SRFLP). A globally optimal solution to the SRFLP is a linear placement of rectangular facilities with varying lengths that achieves the minimum total cost associated with the (known or projected) inter- actions between them. We demonstrate that the combination of a semidefinite programming relaxation with … Read more

    A Class Representative Model for Pure Parsimony Haplotyping

  • Daniele Catanzaro
  • Martine Labbé
  • Alessandra Godi
    • Categories (Mixed) Integer Linear Programming, Basic Sciences Applications Tags , ,

    Parsimonious haplotype estimation from aligned Single Nucleotide Polymorphism (SNP) fragments consists of finding the minimum number of haplotypes necessary to explain a given set of genotypes. This problem is known to be NP-Hard. Here we describe a new integer linear-programming model to tackle this problem based on the concept of class representatives, already used for … Read more

    Convex Optimization Methods for Dimension Reduction and Coefficient Estimation in Multivariate Linear Regression

  • Zhaosong Lu
  • Renato D.C. Monteiro
  • Ming Yuan
    • Categories Convex Optimization, Nonsmooth Optimization, Statistics Tags , , , , , ,

    In this paper, we study convex optimization methods for computing the trace norm regularized least squares estimate in multivariate linear regression. The so-called factor estimation and selection (FES) method, recently proposed by Yuan et al. [17], conducts parameter estimation and factor selection simultaneously and have been shown to enjoy nice properties in both large and … Read more

    LASSO-Patternsearch Algorithm with Application to Ophthalmology and Genomic Data

  • Barbara Klein
  • Stephen Wright
  • Ronald Klein
  • Kristine Lee
  • Weiliang Shi
  • Grace Wahba
    • Categories Nonsmooth Optimization, Statistics Tags , ,

    The LASSO-Patternsearch algorithm is proposed as a two-step method to identify clusters or patterns of multiple risk factors for outcomes of interest in demographic and genomic studies. The predictor variables are dichotomous or can be coded as dichotomous. Many diseases are suspected of having multiple interacting risk factors acting in concert, and it is of … Read more

    Constraint Orbital Branching

  • Jeff Linderoth
  • James Ostrowski
  • Fabrizio Rossi
  • Stefano Smriglio
    • Categories Integer Programming, Statistics

    Orbital branching is a method for branching on variables in integer programming that reduces the likelihood of evaluating redundant, isomorphic nodes in the branch-and-bound procedure. In this work, the orbital branching methodology is extended so that the branching disjunction can be based on an arbitrary constraint. Many important families of integer programs are structured such … Read more

    Intensity based Three-Dimensional Reconstruction with Nonlinear Optimization

  • Martin Gugat
  • Günter Leugering
  • J. Hornegger
    • Categories Applications - Science and Engineering Tags , , ,

    New images of a three-dimensional scene can be generated from known image sequences using lightfields. To get high quality images, it is important to have accurate information about the structure of the scene. In order to optimize this information, we define a residual-function. This function represents the difference between an image, rendered in a known … Read more

    Dissimilarity Measures for Population-Based Global Optimization Algorithms

  • Andrea Cassioli
  • Marco Locatelli
  • Fabio Schoen
    • Categories Basic Sciences Applications, Global Optimization, Stochastic Approaches Tags , , ,

    Very hard optimization problems, i.e., problems with a large number of variables and local minima, have been effectively attacked with algorithms which mix local searches with heuristic procedures in order to widely explore the search space. A Population Based Approach based on a Monotonic Basin Hopping optimization algorithm has turned out to be very effective … Read more

    Multi-Secant Equations, Approximate Invariant Subspaces and Multigrid Optimization

  • Serge Gratton
  • Philippe L. Toint
    • Categories Optimization of Systems modeled by PDEs, Unconstrained Optimization Tags , , ,

    New approximate secant equations are shown to result from the knowledge of (problem dependent) invariant subspace information, which in turn suggests improvements in quasi-Newton methods for unconstrained minimization. It is also shown that this type of information may often be extracted from the multigrid structure of discretized infinite dimensional problems. A new limited-memory BFGS using … Read more

    Controlling the dose distribution with gEUD-type constraints within the convex IMRT optimization framework

  • Tim Craig
  • Harald Keller
  • Michael Sharpe
  • Tamás Terlaky
  • Yuriy Zinchenko
    • Categories Biomedical Applications, Convex Optimization Tags , , , , , ,

    Radiation therapy is an important modality in treating various cancers. Various treatment planning and delivery technologies have emerged to support Intensity Modulated Radiation Therapy (IMRT), creating significant opportunities to advance this type of treatment. We investigate the possibility of including the dose prescription, specified by the DVH, within the convex optimization framework for inverse IMRT … Read more

    On linear infeasibility arising in intensity-modulated radiation therapy inverse planning

  • Adi Ben-Israel
  • Yair Censor
  • James M. Galvin
  • Ying Xiao
    • Categories Applications - Science and Engineering, Approximation Algorithms Tags , , , , ,

    Intensity–modulated radiation therapy (IMRT) gives rise to systems of linear inequalities, representing the effects of radiation on the irradiated body. These systems are often infeasible, in which case one settles for an approximate solution, such as an {a,ß}–relaxation, meaning that no more than a percent of the inequalities are violated by no more than ß … Read more