On characterizing tighter formulations for 0–1 programs

We present two approaches for 0–1 program model tightening. They are based on increasing and reducing knapsack constraint coefficients, respectively. Both approaches make use of information from cover structures implied by the original constraint system. The formulations that they provide are 0–1 equivalent and as tight as the original model. We also present some characterizations for the new formulations to be tighter than the original model.     

A constrained nonlinear 0–1 program for data allocation

This paper analyzes the problem of allocating copies of relations from a global database to the sites of a geographically distributed communication network. The objective of the allocation is to minimize the total cost due to transmissions generated by queries from the various sites, including queries that access multiple relations. This allocation problem is modeled as a constrained nonlinear 0–1 subproblems generated during subgradient optimization are solved as optimization. Some of the unconstrained quadratic 0–1 subproblems generated during subgradient optimization are solved as maximum flow problems, while the others require implicit enumeration, depending on the nature of the objective function coefficients of the subproblems. Our solution approach is tested extensively on data allocation problems with as many as 100 sites and 20 relations. On a set of randomly generated test problems our approach was close to two orders of magnitude faster than the general purpose integer programming code OSL.     

A scenario decomposition algorithm for 0–1 stochastic programs

We propose a scenario decomposition algorithm for stochastic 0–1 programs. The algorithm recovers an optimal solution by iteratively exploring and cutting-off candidate solutions obtained from solving scenario subproblems. The scheme is applicable to quite general problem structures and can be implemented in a distributed framework. Illustrative computational results on standard two-stage stochastic integer programming and nonlinear stochastic integer programming test problems are presented.     

A compact variant of the QCR method for quadratically constrained quadratic 0–1 programs

Quadratic Convex Reformulation (QCR) is a technique that was originally proposed for quadratic 0–1 programs, and then extended to various other problems. It is used to convert non-convex instances into convex ones, in such a way that the bound obtained by solving the continuous relaxation of the reformulated instance is as strong as possible. In this paper, we focus on the case of quadratically constrained quadratic 0–1 programs. The variant of QCR previously proposed for this case involves the addition of a quadratic number of auxiliary continuous variables. We show that, in fact, at most one additional variable is needed. Some computational results are also presented.     

Solving a Class of Multiplicative Programs with 0–1 Knapsack Constraints

We develop a branch-and-bound algorithm to solve a nonlinear class of 0–1 knapsack problems. The objective function is a product of m2 affine functions, whose variables are mutually exclusive. The branching procedure in the proposed algorithm is the usual one, but the bounding procedure exploits the special structure of the problem and is implemented through two stages: the first stage is based on linear programming relaxation; the second stage is based on Lagrangian relaxation. Computational results indicate that the algorithm is promising.     

A parallel interior point decomposition algorithm for block angular semidefinite programs

We present a two phase interior point decomposition framework for solving semidefinite (SDP) relaxations of sparse maxcut, stable set, and box constrained quadratic programs. In phase 1, we suitably modify the matrix completion scheme of Fukuda et al. (SIAM J. Optim. 11:647–674, 2000) to preprocess an existing SDP into an equivalent SDP in the block-angular form. In phase 2, we solve the resulting block-angular SDP using a regularized interior point decomposition algorithm, in an iterative fashion between a master problem (a quadratic program); and decomposed and distributed subproblems (smaller SDPs) in a parallel and distributed high performance computing environment. We compare our MPI (Message Passing Interface) implementation of the decomposition algorithm on the distributed Henry2 cluster with the OpenMP version of CSDP (Borchers and Young in Comput. Optim. Appl. 37:355–369, 2007) on the IBM Power5 shared memory system at NC State University. Our computational results indicate that the decomposition algorithm (a) solves large SDPs to 2–3 digits of accuracy where CSDP runs out of memory; (b) returns competitive solution times with the OpenMP version of CSDP, and (c) attains a good parallel scalability. Comparing our results with Fujisawa et al. (Optim. Methods Softw. 21:17–39, 2006), we also show that a suitable modification of the matrix completion scheme can be used in the solution of larger SDPs than was previously possible.     

Dynamic Lagrangian dual and reduced RLT constructs for solving 0–1 mixed-integer programs

In this paper, we consider a dynamic Lagrangian dual optimization procedure for solving mixed-integer 0–1 linear programming problems. Similarly to delayed relax-and-cut approaches, the procedure dynamically appends valid inequalities to the linear programming relaxation as induced by the Reformulation-Linearization Technique (RLT). A Lagrangian dual algorithm that is augmented with a primal solution recovery scheme is applied implicitly to a full or partial first-level RLT relaxation, where RLT constraints that are currently being violated by the primal estimate are dynamically generated within the Lagrangian dual problem, thus controlling the size of the dual space while effectively capturing the strength of the RLT-enhanced relaxation. We present a preliminary computational study to demonstrate the efficacy of this approach.     

A completely positive representation of 0–1 linear programs with joint probabilistic constraints

In this paper, we study 0–1 linear programs with joint probabilistic constraints. The constraint matrix vector rows are assumed to be independent, and the coefficients to be normally distributed. Our main results show that this non-convex problem can be approximated by a convex completely positive problem. Moreover, we show that the optimal values of the latter converge to the optimal values of the original problem. Examples randomly generated highlight the efficiency of our approach.     

A cutting-plane approach to mixed 0–1 stochastic integer programs

We consider a mixed 0–1 integer programming problem with dual block-angular structure arising in two-stage stochastic programming. A relaxation is proposed such that the problem is decomposed into subproblems each corresponding to the outcomes of the random variable. The convex hull of feasible solutions for the relaxation is characterized using results from disjunctive programming and it is shown how Lift-and-Project cuts can be generated for one subproblem and made valid for different outcomes.     

On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0–1 quadratic problems leading to quasi-Newton methods

This article presents a family of semidefinite programming bounds, obtained by Lagrangian duality, for 0–1 quadratic optimization problems with linear or quadratic constraints. These bounds have useful computational properties: they have a good ratio of tightness to computing time, they can be optimized by a quasi-Newton method, and their final tightness level is controlled by a real parameter. These properties are illustrated on three standard combinatorial optimization problems: unconstrained 0–1 quadratic optimization, heaviest $k$ -subgraph, and graph bisection.     

The Chebyshev–Shamanskii Method for Solving Systems of Nonlinear Equations

We present a method, based on the Chebyshev third-order algorithm and accelerated by a Shamanskii-like process, for solving nonlinear systems of equations. We show that this new method has a quintic convergence order. We will also focus on efficiency of high-order methods and more precisely on our new Chebyshev–Shamanskii method. We also identify the optimal use of the same Jacobian in the Shamanskii process applied to the Chebyshev method. Some numerical illustrations will confirm our theoretical analysis.     

Lyapunov-barrier characterization of robust reach–avoid–stay specifications for hybrid systems

Stability, reachability, and safety are crucial properties of dynamical systems. While verification and control synthesis of reach–avoid–stay objectives can be effectively handled by abstraction-based formal methods, such approaches can be computationally expensive due to the use of state–space discretization. In contrast, Lyapunov methods qualitatively characterize stability and safety properties without any state–space discretization. Recent work on converse Lyapunov-barrier theorems also demonstrates an approximate completeness for verifying reach–avoid–stay specifications of systems modeled by nonlinear differential equations. In this paper, based on the topology of hybrid arcs, we extend the Lyapunov-barrier characterization to more general hybrid systems described by differential and difference inclusions. We show that Lyapunov-barrier functions are not only sufficient to guarantee reach–avoid–stay specifications for well-posed hybrid systems, but also necessary for arbitrarily slightly perturbed systems under mild conditions. Numerical examples are provided to illustrate the main results.     

Quantitative stability analysis for vector problems of 0–1 programming

We consider multiple objective 0–1 programming problems in the situation where parameters of objective functions and linear constraints are exposed to independent perturbations. We study quantitative characteristics of stability (stability radii) of problem solutions. An approach to deriving formulae and estimations of stability radii is presented. This approach is applied to stability analysis of the linear 0–1 programming problem and problems with two types of nonlinear objective functions: linear absolute value and quadratic.     

A new class of polynomial primal–dual methods for linear and semidefinite optimization

We propose a new class of primal–dual methods for linear optimization (LO). By using some new analysis tools, we prove that the large-update method for LO based on the new search direction has a polynomial complexity of O(n^4/(4+ρ)log(n/ε)) iterations, where ρ∈[0,2] is a parameter used in the system defining the search direction. If ρ=0, our results reproduce the well-known complexity of the standard primal–dual Newton method for LO. At each iteration, our algorithm needs only to solve a linear equation system. An extension of the algorithms to semidefinite optimization is also presented.     

A “joint?+?marginal” heuristic for 0/1 programs

We propose a heuristic for 0/1 programs based on the recent “joint?+?marginal” approach of the first author for parametric polynomial optimization. The idea is to first consider the n-variable (x ₁, . . . , x _n ) problem as a (n ? 1)-variable problem (x ₂, . . . , x _n ) with the variable x ₁ being now a parameter taking value in {0, 1}. One then solves a hierarchy of what we call “joint?+?marginal” semidefinite relaxations whose duals provide a sequence of polynomial approximations ${x_1\mapsto J_k(x_1)}$ that converges to the optimal value function J (x ₁) (as a function of the parameter x ₁). One considers a fixed index k in the hierarchy and if J _k (1) >?J _k (0) then one decides x ₁ =?1 and x ₁ = 0 otherwise. The quality of the approximation depends on how large k can be chosen (in general, for significant size problems, k = 1 is the only choice). One iterates the procedure with now a (n ? 2)-variable problem with one parameter ${x_2 \in \{0, 1\}}$ , etc. Variants are also briefly described as well as some preliminary numerical experiments on the MAXCUT, k-cluster and 0/1 knapsack problems.     

Nonmonotone Self-adaptive Levenberg–Marquardt Approach for Solving Systems of Nonlinear Equations

The well-known Levenberg–Marquardt method is used extensively to solve systems of nonlinear equations. An extension of the Levenberg–Marquardt method based on new nonmonotone technique is described. To decrease the total number of iterations, this method allows the sequence of objective function values to be nonmonotone, especially in the case where the objective function is ill-conditioned. Moreover, the parameter of Levenberg–Marquardt is produced according to the new nonmonotone strategy to use the advantages of the faster convergence of the Gauss–Newton method whenever iterates are near the optimizer, and the robustness of the steepest descent method in the case in which iterates are far away from the optimizer. The global and quadratic convergence of the proposed method is established. The results of numerical experiments are reported.