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.

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 λ₂ 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¹²) 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.

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.)