Stabilizer-based symmetry breaking constraints for mathematical programs

Mathematical programs whose formulation is symmetric often take a long time to solve using Branch-and-Bound type algorithms, because of the several symmetric optima. A simple technique used in these cases is to adjoin symmetry breaking constraints to the formulation before solving the problem. These constraints: (a) aim to guarantee that at least one optimum is feasible, whilst making some of the symmetric optima infeasible; and (b) are usually associated to the different orbits of the action of the formulation group on the set of variable indices. In general, one cannot adjoin symmetry breaking constraints from more than one orbit. In Liberti (Math Program A 131:273–304, doi:10.1007/s10107-010-0351-0, 2012), some (restrictive) sufficient conditions are presented which make it possible to adjoin such constraints from several orbits at the same time. In this paper we present a new, less restrictive method for the same task, and show it performs better computationally.     

On the impact of symmetry-breaking constraints on spatial Branch-and-Bound for circle packing in a square

We study the problem of packing equal circles in a square from the mathematical programming point of view. We discuss different formulations, we analyze formulation symmetries, we propose some symmetry breaking constraints and show that not only do they tighten the convex relaxation bound, but they also ease the task of local NLP solution algorithms in finding feasible solutions. We solve the problem by means of a standard spatial Branch-and-Bound implementation, and show that our formulation improvements allow the algorithm to find very good solutions at the root node.     

Point-to-point shortest paths on dynamic time-dependent road networks

This a summary of the author’s PhD thesis supervised by Leo Liberti, Philippe Baptiste and Daniel Krob and defended on 18 June 2009 at Ecole Polytechnique, Palaiseau, France. The thesis is written in English and is available at . The computation of point-to-point shortest paths in road networks has many practical applications that require very fast solution times, meaning that Dijkstra’s algorithm is not a viable option. In this work we develop an efficient algorithm to find the shortest route between two nodes of a large-scale, time-dependent graph, where we also allow the time-dependent arc cost functions to be updated at regular intervals. Furthermore, we propose a mathematical programming formulation for the shortest paths problem on time-dependent networks, that gives rise to integer programs. Within the context of solving Mixed-Integer Linear Programs through a Branch-and-Bound algorithm, we propose a new strategy for branching, mixing branching on single variables with branching on general hyperplanes. Finally, we introduce an effective heuristic for nonconvex Mixed-Integer Nonlinear Programss which combines VNS, Local Branching, NLP local search and Branch-and-Bound.     

On symmetric algorithms for bilinear forms over finite fields

In this paper we study the computation of symmetric systems of bilinear forms over finite fields via symmetric bilinear algorithms. We show that, in general, the symmetric complexity of a system is upper bounded by a constant multiple of the bilinear complexity; we characterize symmetric algorithms in terms of the cosets of a specific cyclic code, and we show that the problem of finding an optimal symmetric algorithm is equivalent to the maximum-likelihood decoding problem for this code.     

On the solution of the symmetric eigenvalue complementarity problem by the spectral projected gradient algorithm

This paper is devoted to the eigenvalue complementarity problem (EiCP) with symmetric real matrices. This problem is equivalent to finding a stationary point of a differentiable optimization program involving the Rayleigh quotient on a simplex (Queiroz et al., Math. Comput. 73, 1849–1863, 2004). We discuss a logarithmic function and a quadratic programming formulation to find a complementarity eigenvalue by computing a stationary point of an appropriate merit function on a special convex set. A variant of the spectral projected gradient algorithm with a specially designed line search is introduced to solve the EiCP. Computational experience shows that the application of this algorithm to the logarithmic function formulation is a quite efficient way to find a solution to the symmetric EiCP.     

Solving the Maximum Clique Problem with Symmetric Rank-One Non-negative Matrix Approximation

Finding complete subgraphs in a graph, that is, cliques, is a key problem and has many real-world applications, e.g., finding communities in social networks, clustering gene expression data, modeling ecological niches in food webs, and describing chemicals in a substance. The problem of finding the largest clique in a graph is a well-known difficult combinatorial optimization problem and is called the maximum clique problem. In this paper, we formulate a very convenient continuous characterization of the maximum clique problem based on the symmetric rank-one non-negative approximation of a given matrix and build a one-to-one correspondence between stationary points of our formulation and cliques of a given graph. In particular, we show that the local (resp. global) minima of the continuous problem corresponds to the maximal (resp. maximum) cliques of the given graph. We also propose a new and efficient clique finding algorithm based on our continuous formulation and test it on the DIMACS data sets to show that the new algorithm outperforms other existing algorithms based on the Motzkin–Straus formulation and can compete with a sophisticated combinatorial heuristic.     

Linearity Embedded in Nonconvex Programs

Nonconvex programs involving bilinear terms and linear equality constraints often appear more nonlinear than they really are. By using an automatic symbolic reformulation we can substitute some of the bilinear terms with linear constraints. This has a dramatically improving effect on the tightness of any convex relaxation of the problem, which makes deterministic global optimization algorithms like spatial Branch-and-Bound much more eff- cient when applied to the problem.     

Pareto optimality and robustness in bi-blending problems

The mixture design problem for two products concerns finding simultaneously two recipes of a blending problem with linear, quadratic and semi-continuity constraints. A solution of the blending problem minimizes a linear cost objective and an integer valued objective that keeps track of the number of raw materials that are used by the two recipes, i.e. this is a bi-objective problem. Additionally, the solution must be robust. We focus on possible solution approaches that provide a guarantee to solve bi-blending problems with a certain accuracy, where two products are using (partly) the same scarce raw materials. The bi-blending problem is described, and a search strategy based on Branch-and-Bound is analysed. Specific tests are developed for the bi-blending aspect of the problem. The whole is illustrated numerically.     

Enriched workflow modelling and Stochastic Branch-and-Bound

Workflow systems provide means and techniques for modelling, designing, performing and controlling repetitive (business) processes. The quality of commercial workflow systems is usually determined to a large extent by their versatility and multi-purpose application. One of the current trends in improving workflow systems lies in enriching modelling methods and techniques in order to enlarge design alternatives.The need for such advanced methods is particularly apparent in those fields in which the process duration can be determined only vaguely, but whose completion schedules are at the same time strictly enforced by a highly competitive market by means of fines and penalties. The risk of an overrun has to be weighed against the expected costs and benefits of certain measures reducing turn-around time and their combinations. Because they can help to avoid such penalties—or, at least, keep any potential losses low by identifying critical subprocesses and evaluate appropriate measures—modelling and evaluation techniques are becoming essential features of workflow systems.Methodologically, we use Stochastic Branch-and-Bound as a technique for finding “optimal” bundles of measures. A numerical study shows the benefits of this meta-approach by means of five stepwise-developed decision scenarios requiring rich modelling. Petri nets as a modelling tool and Stochastic Branch-and-Bound as an optimization technique determine for multi-mode resource constrained workflows of varying complexity an optimal workforce strategy with respect to the number of workers and their qualification.     

A symmetric mixed finite element method for nearly incompressible elasticity based on biorthogonal systems

We present a symmetric version of the nonsymmetric mixed finite element method presented in (Lamichhane, ANZIAM J 50 (2008), C324–C338) for nearly incompressible elasticity. The displacement–pressure formulation of linear elasticity is discretized using a Petrov–Galerkin discretization for the pressure equation in (Lamichhane, ANZIAM J 50 (2008), C324–C338) leading to a non‐symmetric saddle point problem. A new three‐field formulation is introduced to obtain a symmetric saddle point problem which allows us to use a biorthogonal system. Working with a biorthogonal system, we can statically condense out all auxiliary variables from the saddle point problem arriving at a symmetric and positive‐definite system based only on the displacement. We also derive a residual based error estimator for the mixed formulation of the problem. © 2011 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2012     

Enhanced speciation in particle swarm optimization for multi-modal problems

In this paper, we present a novel multi-modal optimization algorithm for finding multiple local optima in objective function surfaces. We build from Species-based particle swarm optimization (SPSO) by using deterministic sampling to generate new particles during the optimization process, by implementing proximity-based speciation coupled with speciation of isolated particles, and by including “turbulence regions” around already found solutions to prevent unnecessary function evaluations. Instead of using error threshold values, the new algorithm uses the particle’s experience, geometric mean, and “exclusion factor” to detect local optima and stop the algorithm. The performance of each extension is assessed with leave-it-out tests, and the results are discussed. We use the new algorithm called Isolated-Speciation-based particle swarm optimization (ISPSO) and a benchmark algorithm called Niche particle swarm optimization (NichePSO) to solve a six-dimensional rainfall characterization problem for 192 rain gages across the United States. We show why it is important to find multiple local optima for solving this real-world complex problem by discussing its high multi-modality. Solutions found by both algorithms are compared, and we conclude that ISPSO is more reliable than NichePSO at finding optima with a significantly lower objective function value.     

A dual exact penalty formulation for the linear complementarity problem

We consider a dual exact penalty formulation for the monotone linear complementarity problem. Tihonov regularization is then used to reduce the solution of the problem to the solution of a sequence of positive-definite, symmetric quadratic programs. A modified form of an SOR method due to Mangasarian is proposed to solve these quadratic programs. We also indicate how to obtain approximate solutions to predefined tolerance by solving a single quadratic program, in special cases.This research was sponsored by US Army Contract DAAG29-80-C-0041, by National Science Foundation Grants DCR-8420963 and MCS-8102684, and AFSOR Grant AFSOR-ISSA-85-0880.     

Global optimization and simulated annealing

In this paper we are concerned with global optimization, which can be defined as the problem of finding points on a bounded subset of ⁿ in which some real valued functionf assumes its optimal (maximal or minimal) value.We present a stochastic approach which is based on the simulated annealing algorithm. The approach closely follows the formulation of the simulated annealing algorithm as originally given for discrete optimization problems. The mathematical formulation is extended to continuous optimization problems, and we prove asymptotic convergence to the set of global optima. Furthermore, we discuss an implementation of the algorithm and compare its performance with other well-known algorithms. The performance evaluation is carried out for a standard set of test functions from the literature.     

Infeasibility spheres for finding robust solutions of blending problems with quadratic constraints

The blending problem is studied as a problem of finding cheap robust feasible solutions on the unit simplex fulfilling linear and quadratic inequalities. Properties of a regular grid over the unit simplex are discussed. Several tests based on spherical regions are described and evaluated to check the feasibility of subsets and robustness of products. These tests have been implemented into a Branch-and-Bound algorithm that reduces the set of points evaluated on the regular grid. The whole is illustrated numerically.     

Dominators for Multiple-objective Quasiconvex Maximization Problems

In this paper we address the problem of finding a dominator for a multiple-objective maximization problem with quasiconvex functions. The one-dimensional case is discussed in some detail, showing how a Branch-and-Bound procedure leads to a dominator with certain minimality properties. Then, the well-known result stating that the set of vertices of a polytope S contains an optimal solution for single-objective quasiconvex maximization problems is extended to multiple-objective problems, showing that, under upper-semicontinuity assumptions, the set of (k 21)-dimensional faces is a dominator for k-objective problems. In particular, for biobjective quasiconvex problems on a polytope S, the edges of S constitute a dominator, from which a dominator with minimality properties can be extracted by Branch-and Bound methods.     

On local search for the generalized graph coloring problem

Given an edge-weighted graph and an integer k, the generalized graph coloring problem is the problem of partitioning the vertex set into k subsets so as to minimize the total weight of the edges that are included in a single subset. We recall a result on the equivalence between Karush-Kuhn-Tucker points for a quadratic programming formulation and local optima for the simple flip-neighborhood. We also show that the quality of local optima with respect to a large class of neighborhoods may be arbitrarily bad and that some local optima may be hard to find.     

Controlled rounding for tables with subtotals

The problem of rounding in statistical tables to protect confidentiality is an important problem in the area of data publication, especially for official statistics. Controlled rounding involves rounding the table data to a prespecified base while ensuring additivity to totals. Previous research provided a formulation of the controlled rounding problem of a simple two-way table as a transportation problem. This paper extends that work to tables with subtotals by using a capacitated transshipment formulation. It is shown that some forms of tables with subtotals always have a controlled rounding solution. Other table structures cannot be guaranteed such a solution under zero-restrictedness. Initial computational experience suggests that the method is viable for use in practical situations.     

A differential equation approach to nonlinear programming

A new method is presented for finding a local optimum of the equality constrained nonlinear programming problem. A nonlinear autonomous system is introduced as the base of the theory instead of usual approaches. The relation between critical points and local optima of the original optimization problem is proved. Asymptotic stability of the critical points is also proved. A numerical algorithm which is capable of finding local optima systematically at the quadratic rate of convergence is developed from a detailed analysis of the nature of trajectories and critical points. Some numerical results are given to show the efficiency of the method.     

Reverse Convex Programming Approach in the Space of Extreme Criteria for Optimization over Efficient Sets

The problem of minimizing a convex function over the difference of two convex sets is called ‘reverse convex program’. This is a typical problem in global optimization, in which local optima are in general different from global optima. Another typical example in global optimization is the optimization problem over the efficient set of a multiple criteria programming problem. In this article, we investigate some special cases of optimization problems over the efficient set, which can be transformed equivalently into reverse convex programs in the space of so-called extreme criteria of multiple criteria programming problems under consideration. A suitable algorithm of branch and bound type is then established for globally solving resulting problems. Preliminary computational results with the proposed algorithm are reported.