November 17 - 21, 2008
The convex cone of n×n completely positive (CPP) matrices
and its dual cone of copositive matrices arise in several
areas of applied mathematics, including optimization. Every
CPP matrix is doubly nonnegative (DNN), i.e., positive
semidefinite and component-wise nonnegative. Moreover
for n less than 5, every DNN matrix is CPP. We investigate the
difference between 5×5 DNN and CPP matrices. We give
a precise characterization of how a 5×5 DNN matrix that is
not CPP differs from a DNN matrix, and use this
characterization
to show how to separate an extreme DNN matrix
that is not CPP from the cone of CPP matrices.
Joint work with Sam Burer and Mirjam Duer.
For the general class of MINLP problems where relaxing the integrality on integer variables yields a nonconvex problem, a commonly used solution method is Branch-and-Bound (BB). Two crucial components of a BB algorithm are: a convex relaxation, often an LP relaxation, to obtain lower bounds; and branching
rules for partitioning the solution set.
We present an extension to nonconvex MINLP of a branching technique that proved successful for Mixed-Integer Linear Programming, namely reliability branching. Branching rules can be applied on both integer and continuous variables in nonconvex MINLPs, and the choice of the branching variable depends on both the MINLP problem and its linear relaxation.
We discuss in detail the choice of both the branching variable and the branching point, i.e. the value of that variable where branching is done. We present some computational results and compare reliability branching with another branching technique for nonconvex MINLPs, Violation Transfer, on a set of publicly available instances.
While implementations of infeasible interior-point methods remain the state-of-the-art in nonlinear programming, there are serious limitations in their use within the framework of MINLP due to lack of warm-start and infeasibility detection capabilities. We present a primal-dual penalty approach that allows interior-point methods to have such capabilities, and remains flexible enough to accommodate changing bounds, additional constraints, and additional variables in the nonlinear subproblems.
Different variants of the branch-and-bound algorithm exist for solving exactly convex MINLPs. These variants differ mainly in the relaxation solved at the nodes of the tree. There are mainly two variants: one that solves a nonlinear programming relaxation at each node and one that solves a linear programming relaxation. In recent year the linear programming based branch-and-bounds have shown to be more effective on large sets of problems. In this talk, we study techniques to make the nonlinear programming based branch-and-bound more competitive. In particular, we study branching strategies and heuristics. The techniques have been implemented in the open-source solver Bonmin We present computational results to assess the effectiveness of the proposed strategies and compare the resulting algorithm with a linear programming (outer approximation based) branch-and-cut.
This talk is based on joint works with Joao Goncalves, Jon Lee and Andreas Waechter.
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.
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.
In recent years algebraic geometry, number theory, and commutative algebra have shown their potential to solve challenging problems in discrete optimization. This talk hopes to show algebraic tools can be used to prove strong computational complexity results in optimization problems with non-linear or multi-objective objective functions and linear constraints.
This is talk is partly based on joint work with M. Koeppe and R. Hemmecke.
We present two algorithms to solve mixed integer second-order cone programming problems: a branch-and-cut method and an outer approximation based branch-and-bound approach. We use different techniques for the generation of linear and convex quadratic cuts and investigate their impact on the branch-and-cut procedure. The presented outer approximation based branch-and-bound algorithm is an extension of the well-known outer approximation based branch-and-bound approach for continuous differentiable problems to subdifferentiable constraint functions. Convergence can be guaranteed, since the subgradients, that satisfy the KKT conditions, can be identified using the dual solution of the occurring second order cone problems. Computational results for test problems and real world applications are given.
An expression graph, informally speaking, represents a function in a
way that cam be manipulated to reveal various kinds of information
about the function, such as its value or partial derivatives at
specified arguments and bounds thereon in specified regions. (Various
representations are possible, and all are equivalent in complexity, in
that one can be converted to another in time linear in the
expression's size.) For mathematical programming problems, including
the mixed-integer nonlinear programming problems that are the subject
of this workshop, there are various advantages to representing
problems as collections of expression graphs. "Presolve" deductions
(to be discussed in more detail by Todd Munson) can simplify the
problem, e.g., by reducing the domains of some variables and proving
that some inequality constraints are never or always active. To find
global solutions, it is helpful sometimes to solve relaxed problems
(e.g., allowing some "integer" variables to vary continuously or
introducing convex or concave relaxations of some constraints or
objectives), and to introduce "cuts" that exclude some relaxed
variable values. There are various ways to compute bounds on an
expression within a specified region or to compute relaxed expressions
from expression graphs. This talk will sketch some of them. As new
information becomes available in the course of a branch-and-bound (or
-cut) algorithm, some expression-graph manipulations and presolve
deductions can be revisited and tightened, so keeping expression
graphs around during the solution process can be helpful. Algebraic
problem representations are a convenient source of expression graphs.
One of my reasons for interest in the AMPL modeling language is that
it delivers expression graphs to solvers.
Sequential quadratic programming (SQP)
methods a powerful and effective class of methods for a
wide range of nonlinearly constrained optimization
problems. Given the scope and utility of nonlinear
optimization, it is not surprising that SQP methods are
still a subject of active research. Recent
developments in methods for mixed integer nonlinear
programming and the minimization of functions subject
to differential equation constraints has led to a
heightened interest in methods that may be "hot
started" from a good approximate solution. We discuss
the role of SQP methods in this context, with
particular reference to some recent enhancements to our
large-scale SQP package SNOPT. We end with some
discussion of the challenges associated with
formulating algorithms that can exploit multicore and
GPU-based computer architectures.
Generalized disjunctive programming (GDP) is an extension of the disjunctive programming paradigm developed by Balas. The GDP formulation involves Boolean and continuous variables that are specified in algebraic constraints, disjunctions and logic propositions, which is an alternative representation to the traditional algebraic mixed integer programming (MIP) formulation. Our research on GDP problems has been motivated by its potential for improved modeling of MINLP optimization, and for the development of customized algorithms that exploit the underlying logical structure of the problem in both the linear and nonlinear cases. We first provide an overview of this work for the case of convex functions emphasizing the quality of continuous relaxations of alternative reformulations that include the big-M, the hull relaxation and the sequential intersection of disjunctions. We then review disjunctive branch and bound as well as logic-based decomposition methods that circumvent some of the limitations in traditional MINLP optimization. Finally, for the case when the GDP problem involves nonconvex functions, we propose a scheme for tightening the lower bounds for obtaining the global optimum using a combined disjunctive and spatial branch and bound search. We illustrate the application of the theoretical concepts and algorithms on a variety of engineering and OR problems.
Sandia National Laboratories has invested considerable effort in massively parallel optimization tools. In this talk, we will summarize relevant experience from developing our parallel mixed-integer programming (MIP) solver PICO (Parallel Integer and Combinatorial Optimizer) and our parallel nonlinear solver GNLP. We will discuss parallel solution of mixed-integer nonlinear programs (MINLP). In particular, we will consider how the choice of parallel platform (tightly-coupled systems, cloud computing, grid computing, etc) can affect algorithmic decisions. We will highlight issues parallel solvers must face that serial solvers do not such as load balancing, ramp up, and termination and some issues that parallel solvers might do differently, such as decomposition. We expect some of our MIP/NLP experience to carry over, and some issues to be unique to, or uniquely difficult for, MINLP.
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.
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.
Joint work with Michael Armbruster (TU Chemnitz),
Marzena Fuegenschuh (TU Darmstadt), and
Alexander Martin (TU Darmstadt).
Semidefinite relaxations are known to deliver good approximations
for combinatorial optimization problems like graph bisection. Using
the spectral bundle method it is possible to exploit structural
properties of the underlying problem and to apply, even to sparse
large scale instances, cutting plane methods, probably the most
successful technique in linear programming. We set up a common
branch-and-cut framework for linear and semidefinite relaxations of
the minimum graph bisection problem. It incorporates
separation algorithms for valid inequalities presented in the recent
study by Armbruster, Fuegenschuh, Helmberg, and Martin 2007 of the
facial structure of the associated polytope. Extensive numerical
experiments show that the semidefinite branch-and-cut approach
outperforms the classical simplex approach on a clear majority of
the sparse large scale test instances. On instances from compiler
design the simplex approach is faster.
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.
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.
Ford was tasked with determining the best sourcing footprint for its $1.5 billion Automotive Components Holdings, LLC Interiors business. This extensive undertaking required a complete re-engineering of the supply footprint of 42 high-volume product lines over 26 major manufacturing processes and more than 50 potential supplier sites. We propose an approximation of the large-scale Mixed Integer Nonlinear Program (MINLP) that accurately accommodates the nonlinear nature of facility cost as a function of utilization and present an iterative Mixed Integer Program (MIP) approach to solve the underlying MINLP. We demonstrate that the resulting solution to the iterative algorithm provides an equivalent solution to the approximated MINLP. The recommendations from this work have been implemented in practice and have resulted in savings of approximately $40 million in upfront investment over the previously preferred alternative.
The classic idea to relate the maximum of a function over a
discrete or continuous domain to certain sums or integrals has
made its apppearance in a number of recent papers from the
point of view of optimization (A.I. Barvinok, "Exponential
integrals and sums over convex polyhedra",
Funktsional. Anal. i Prilozhen. 26 (1992); J.B. Lasserre,
"Generating functions and duality for integer programs",
Discrete Optim. 1 (2004)).
Efficient summation and integration procedures can give rise
to efficient approximation algorithms for optimization
problems. As an example, a fully polynomial-time
approximation scheme for optimizing arbitrary polynomial
functions over the integer points in polyhedra of arbitrary,
fixed dimension has been obtained (work with J. A. De Loera,
R. Hemmecke, R. Weismantel, Math. Oper. Res. 31 (2006)).
In this talk I report on recent work (with V. Baldoni,
N. Berline, J. A. De Loera, M. Vergne) to study the efficiency
of integration procedures for polynomial functions in high
dimension. The methods are related to Brion's formulas,
Barvinok's exponential sums, and also to the polynomial Waring
problem that asks to represent a polynomial as a sum of powers
of few linear forms.
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
programming, 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
If a mathematical program (be it linear or nonlinear) has many symmetric optima, solving it via Branch-and-Bound techniques often yields search trees of disproportionate sizes; thus, finding and exploiting symmetries is an important task. We propose a method for: (a) automatically finding the formulation group of any given Mixed-Integer Nonlinear Program, and (b) reformulating the problem so that it has fewer symmetric solutions. The reformulated problem can then be solved via standard Branch-and-Bound codes such as CPLEX (for linear programs) and Couenne (for nonlinear programs). Our computational results include formulation group tables for the MIPLib3, MIPLib2003, GlobalLib, MINLPLib and MacMINLP instance libraries, solution tables for some instances in the aforementioned libraries, and a theoretical and computational study of the symmetries of the Kissing Number Problem.
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.
The most effective solvers for mixed integer linear programs (MILP)s
employ a variety of algorithmic refinements that have made previously
intractable models routinely solvable. Solvers for Mixed Integer
Nonlinear Programs (MINLP)s should be no different. In this talk, we
will discuss the impact of applying advanced branching rules, primal
heuristics, preprocessing, and cutting planes in algorithms to solve
(convex) mixed integer nonlinear programs. Many of the ideas have
been implemented in the solver FilMINT, and the talk contains
computational results to demonstrate the improvements that can be
obtained by applying traditional MILP techniques for MINLPs.
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.
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.
Preprocessing technique simplify and strengthen a model prior to calculating a solution. A combination of rules exploiting the constraint set and primal-dual relationships are applied to fix variables, improve their bounds, and eliminate redundant expressions. In addition, some nonconvex constraints can be transformed into convex constraints. Exploiting discrete variables during preprocessing adds rules to identify and exploit special structures and strengthen the formulation prior to computing convex estimators and cuts, and exploring a branch-and-bound tree. In this talk, I will discusses a unified preprocessor for mixed integer mathematical programs with equilibrium constraints being developed for MINOTAUR.
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.
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.
An important issue in branch and bound methods for mixed integer nonlinear programming is the fast detection of infeasibility. This topic has not received sufficient attention and the methods developed for nonlinear programming often required a large number of iterations before a declaration of infeasibility can be made.
The focus of this talk is to address the need for optimization
algorithms that can both efficiently solve feasible problems and rapidly detect when a given problem instance is infeasible. One way to address these concerns is to employ a switch in an algorithm to decide whether
the current iteration should seek a solution of the nonlinear program
or, in contrast, to solely minimize some measure of feasibility. A challenge with such an approach lies in the difficulty of designing effective criteria for determining when such a switch should be made.
We propose an alternative approach involving a single optimization
strategy, and show that it is effective for finding an optimal feasible solution (when one exists) or finding the minimizer of a feasibility measure (when no feasible point exists). Our algorithm is an active-set method that uses the penalty parameter to emphasize optimality over
infeasibility detection, or vice versa. We establish superlinear convergence results and discuss numerical experiments that demonstrate
the advantages of our approach.
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.
We develop an algorithmic theory of nonlinear optimization over sets
of integer points presented by inequalities or by oracles. Using a
combination of geometric and algebraic methods, involving zonotopes,
Graver bases, multivariate polynomials and Frobenius numbers, we provide
polynomial-time algorithms for broad classes of nonlinear combinatorial
optimization problems and integer programs in variable dimension.
I will overview this work, joint with many colleagues over the last few
years, and discuss some of its many applications in statistics and
operations research, including privacy in statistical databases,
experimental design, nonlinear transportation, multicommodity flows,
error-correcting codes, matroids and general independence systems.
The Lovasz theta body TH(G) is a well-known relaxation of the stable set
polytope STAB(G) that is computable using semidefinite programming. These
ideas can be extended via sum of squares techniques to other combinatorial
optimization problems, providing a natural generalization of the theta body
for general polynomial ideals. In this talk we describe these general
techniques, and characterize finite point sets whose theta body coincides
with its convex hull. This is joint work with Joao Gouveia and Rekha Thomas
(U. Washington).
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.
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.
Sandia National Laboratories has invested considerable effort in massively parallel optimization tools. In this talk, we will summarize relevant experience from developing our parallel mixed-integer programming (MIP) solver PICO (Parallel Integer and Combinatorial Optimizer) and our parallel nonlinear solver GNLP. We will discuss parallel solution of mixed-integer nonlinear programs (MINLP). In particular, we will consider how the choice of parallel platform (tightly-coupled systems, cloud computing, grid computing, etc) can affect algorithmic decisions. We will highlight issues parallel solvers must face that serial solvers do not such as load balancing, ramp up, and termination and some issues that parallel solvers might do differently, such as decomposition. We expect some of our MIP/NLP experience to carry over, and some issues to be unique to, or uniquely difficult for, MINLP.
It has recently been shown that linear programs over the cone of
completely positive matrices give exact formulations for many
NP-hard combinatorial optimization problems. This motivates the
investigation of solution methods for such problems.
In this talk I will present a heuristic algorithm for this problem,
whos main effort in each iteration consists in solving a convex quadratic
problem in sign constrained variables.
The algorithm will be applied to random copositive programs
as well as to the copositive formulation of some
NP-hard graph optimization problems.
(joint work with M. Bomze (Vienna) and F. Jarre (Duesseldorf))
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.
Joint work with Sven Leyffer (Argonne National Laboratory)
and Emilie Wanufelle (University of Namur).
Motivated by problems related to power systems analysis which give rise
to nonconvex mixed integer nonlinear programming (MINLP) problems,
we propose a global optimization method based on ideas and techniques
that can be easily extended to handle a large class of nonconvex MINLPs.
Our method decomposes the nonlinear functions appearing in the problem
to solve into one- and two-dimensional components for which piecewise
linear envelopes are constructed using ideas similar to special ordered sets.
The resulting relaxations are then successively refined by branching on integer
or continuous variables. We prove convergence to a global optimum within a
desired accuracy under mild assumptions and present some preliminary
numerical experience.
Joint work with Pierre Bonami and Jon Lee.
This talk addresses the problem of generating strong convex
relaxations of Mixed Integer Quadratically Constrained Programming
(MIQCP) problems. MIQCP problems are very difficult because they
combine two kinds of non-convexities: integer variables and
non-convex quadratic constraints. To produce strong relaxations of
MIQCP problems, we use techniques from disjunctive programming and
the lift-and-project methodology. In particular, we propose new methods for
generating valid inequalities by using the equation Y = x x^{T}. We
use the concave constraint $0 succcurlyeq Y - x x^{T} $ to derive
disjunctions of two types. The first ones are directly derived from
the eigenvectors of the matrix Y - x x^{T} with positive
eigenvalues, the second type of disjunctions are obtained by
combining several eigenvectors in order to minimize the width
of the disjunction. We also use the convex SDP constraint Y - x
x^{T} succcurlyeq 0 to derive convex quadratic cuts, and we combine
both approaches in a cutting plane algorithm. We present
computational results to illustrate our findings.
same abstract as the 11/18 talk
Joint work with Walter Murray (Stanford University).
The siting and sizing of electrical substations on a rectangular electrical grid can be formulated
as an integer programming problem with a quadratic objective and linear constraints. We propose a novel
approach that is based on solving a sequence of local relaxations of the problem for a given number of
substations. Two methods are discussed for determining a new location from the solution of the relaxed
problem. Each leads to a sequence of strictly improving feasible integer solutions. The number of substations
is then modified to seek a further reduction in cost. Lower bounds for the solution are also provided by solving
a sequence of mixed-integer linear programs. Results are provided for a variety of uniform and Gaussian load
distributions as well as some real examples from an electric utility. The results of GAMS/DICOPT, GAMS/SBB,
GAMS/BARON and CPLEX applied to these problems are also reported. Our algorithm shows slow growth in
computational effort with the number of integer variables.
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.
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.
We present the extended Branch and Cut algorithm implemented in the software package LaGO for the solution of block-separable nonconvex mixed-integer nonlinear programs.
The algorithm reformulates every function into a block-separable form and computes convex underestimators for each term separately. For that purpose, nonquadratic functions are first replaced by quadratic underestimators using a powerful heuristic. Nonconvex quadratic functions are then replaced by exakt convex underestimators.
Finally, a linear outer approximation is constructed by linearization of the convex relaxation and the generation of mixed-integer rounding cuts and linearized interval gradient cuts.
The efficiency of the method is improved by the application of a simple constraint propagation technique based on interval arithmetic.
This talk is concerned with optimizing nonlinear
functions over the lattice points in a polyhedral set.
We present three families of polynomial time algorithms
for special cases of the general problem.
Each such algorithm makes use of
combinatorial, geometric or algebraic
properties of the underlying problem.
The first problem deals with optimizing nonlinear functions over a matroid.
(Joint work with Jon Lee and Shmuel Onn).
The second class of problems concerns convex n-fold
integer minimization problems.
(Joint work with Raymond Hemmecke and Shmuel Onn).
Our last family of problems is to maximize polynomials
over the integer points in a polytope when the dimension is fixed.
Under mild assumptions we present an FPTAS for performing this task.
(Joint work with Jesus De Loera, Matthias Koeppe and Raymond Hemmecke).
Joint work with Andreas Lundell,
Process Design and Systems Engineering, Åbo Akademi University
Biskopsgatan 8, FIN-20500 Turku, Finland.
Keywords: Transformation techniques; mixed integer nonlinear programming; signomial functions; global optimization.
Abstract:
In this presentation some transformation techniques are discussed. With the given techniques a class of non-convex MINLP problems, including signomial functions, can be solved to global optimality. The transformation techniques are based on single variable power and exponential transformations and the signomial functions can be converted into convex form, by the transformations. In addition, the original non-convex problem can be relaxed into convex form, if the transformations have certain properties and the inverse transformations are approximated by piecewise linear functions.
The transformations are not unique and there exists degrees of freedom in selecting them. For determining an "optimal" set of transformations a mixed integer linear programming (MILP) problem can be formulated. The solution of the MILP problem can be used separately but acts, in our case, as a pre-processing step in the global optimization framework. Certain properties of the transformations can be emphasized in the initial MILP pre-processing step. For example, the total number of transformations needed can be minimized. The principles behind the transformation techniques are given and some numerical examples are used to illustrate the given techniques.
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.)