Using Surrogate Constraints in a Lagrangian Relaxation Approach to Set-Covering Problems

Lagrangian relaxations have been used in a variety of IP problem settings. The main thrust of such efforts is to obtain bounding information for use in a branch-and-bound procedure. This paper examines the effect of adding a single surrogate constraint to Lagrangian subproblems in an attempt to improve upon the bounds produced by conventional Lagrangian relaxation. Computational results on some randomly generated set-covering problems are reported.     

Using Laplacian Eigenvalues and Eigenvectors in the Analysis of Frequency Assignment Problems

A Frequency Assignment Problem (FAP) is the problem that arises when frequencies have to be assigned to a given set of transmitters so that spectrum is used efficiently and the interference between the transmitters is minimal. In this paper we see the frequency assignment problem as a generalised graph colouring problem, where transmitters are presented by vertices and interaction between two transmitters by a weighted edge. We generalise some properties of Laplacian matrices that hold for simple graphs. We investigate the use of Laplacian eigenvalues and eigenvectors as tools in the analysis of properties of a FAP and its generalised chromatic number (the so-called span).     

Testing the Exactness of Convex Relaxations for Robust LMI Problems

We consider non‐convex robust linear matrix inequality problems and general families of convex relaxations based on multipliers that cover a whole variety of known concrete versions. In this framework we provide new tests for when these relaxations are exact that go beyond a recently suggested rank‐one principle, and we reveal applicability to an asymptotically exact relaxation sequence.     

Two classes of Quadratic Assignment Problems that are solvable as Linear Assignment Problems

The Quadratic Assignment Problem is one of the hardest combinatorial optimization problems known. We present two new classes of instances of the Quadratic Assignment Problem that can be reduced to the Linear Assignment Problem and give polynomial time procedures to check whether or not an instance is an element of these classes.     

Decomposition-based Method for Sparse Semidefinite Relaxations of Polynomial Optimization Problems

We consider polynomial optimization problems pervaded by a sparsity pattern. It has been shown in Lasserre (SIAM J. Optim. 17(3):822–843, 2006) and Waki et al. (SIAM J. Optim. 17(1):218–248, 2006) that the optimal solution of a polynomial programming problem with structured sparsity can be computed by solving a series of semidefinite relaxations that possess the same kind of sparsity. We aim at solving the former relaxations with a decomposition-based method, which partitions the relaxations according to their sparsity pattern. The decomposition-based method that we propose is an extension to semidefinite programming of the Benders decomposition for linear programs (Benders, Comput. Manag. Sci. 2(1):3–19, 2005).     

Assignment Using Choice Lists

This paper examines the problem of assigning items to people, given that each person lists the items in the order in which he would prefer them. Three types of assignment function are examined, namely stable, bottleneck and numerical, and the advantages and disadvantages of each are discussed. The effect of allowing equal choices in the lists (weak preference ordering) is also examined.     

Solution of Two-Point Boundary-Value Problems Using the Differential Transformation Method

This paper considers two-point boundary-value problems using the differential transformation method. An iterative procedure is proposed for both the linear and nonlinear cases. Using the proposed approach, an analytic solution of the two-point boundary-value problem, represented by an mth-order Taylor series expansion, can be obtained throughout the prescribed range.     

The Solution of Two-Dimensional Oseen Flow Problems Using Integral Conditions

A general method of solving Oseen's linearized equations fortwo-dimensional steady flow of a viscous incompressible fluidpast a cylinder in an unbounded field is developed. The analysisis developed in terms of the scalar vorticity and stream functionand it is shown that the vorticity for Oseen flow problems canbe obtained separately from the stream function. The determinationof the vorticity can be effected using conditions of an integralcharacter deduced from the no-slip condition at the cylindersurface together with the conditions at large distances. Theindependent determination of the vorticity seems to be a newstep in Oseen theory. The method enables one to obtain manyproperties of the flow in terms ofthe Reynolds number by usingonly the vorticity without the necessity of finding the streamfunction. The use of integral conditions makes the detailedcalculations straightforward, systematic, and elementary. Themethod is tested by applying it to the case of uniform flowpast an elliptic cylinder at an arbitrary angle of incidenceand also to cases of symmetrical and asymmetrical flows pastcircular cylinders. The leading approximation for small Reynoldsnumber is obtained where possible. In the case of flow pasta rotating cylinder, the only possible solution is the Oseensolution for the nonrotating case with the addition of a potentialvortex.     

Exact Solutions of Some Nonconvex Quadratic Optimization Problems via SDP and SOCP Relaxations

We show that SDP (semidefinite programming) and SOCP (second order cone programming) relaxations provide exact optimal solutions for a class of nonconvex quadratic optimization problems. It is a generalization of the results by S. Zhang for a subclass of quadratic maximization problems that have nonnegative off-diagonal coefficient matrices of quadratic objective functions and diagonal coefficient matrices of quadratic constraint functions. A new SOCP relaxation is proposed for the class of nonconvex quadratic optimization problems by extracting valid quadratic inequalities for positive semidefinite cones. Its effectiveness to obtain optimal values is shown to be the same as the SDP relaxation theoretically. Numerical results are presented to demonstrate that the SOCP relaxation is much more efficient than the SDP relaxation.     

有资格限制的指派问题的求解方法

在实际的指派工作中，常会遇到某个人有没有资格去承担某项工作的问题，因此，本建立了有资格限制的指派问题的数学模型。在此数学模型中，将效益矩阵转化为判定矩阵，由此给出了判定此种指派问题是否有解的方法；在有解的情况下，进一步将效益矩阵转化为求解矩阵，从而将有资格限制的指派问题化为传统的指派问题来求解。最后给出了一个数值例子来说明这样的处理方法是有效的。     

Least Squares Solution of Bivariate Surface Fitting Problems Using Tensor Product Splines

The paper treats bivariate surface fitting problems, where the data points lie on lines parallel to one of the axes. The associated bivariate collocation matrix is investigated as a block Kronecker product of univariate collocation matrices. Based on various properties of this block Kronecker product, such scattered data are characterized where the associated interpolation problem using tensor product splines admits a unique solution.     

Asymptotic Properties of Random Multidimensional Assignment Problems

The multidimensional assignment problem (MAP) is a NP-hard combinatorial optimization problem, occurring in many applications, such as data association. In this paper, we prove two conjectures made in Ref. 1 and based on data from computational experiments on MAPs. We show that the mean optimal objective function cost of random instances of the MAP goes to zero as the problem size increases, when assignment costs are independent exponentially or uniformly distributed random variables. We prove also that the mean optimal solution goes to negative infinity when assignment costs are independent normally distributed random variables.     

平衡和不平衡运输问题与分配问题的通用迭代算法

将不平衡运输问题转化成网络最短路问题,利用Floyd算法规则,给出了一种既可以解平衡和不平衡运输问题,又可以解平衡和不平衡分配问题的通用迭代算法。与专门用于解运输问题的闭合回路法和专门用于解分配问题的匈牙利法相比,这种算法不但具有通用的优点,而且更便于在计算机上运行。     

Lower Bounds from State Space Relaxations for Concave Cost Network Flow Problems

In this paper we obtain Lower Bounds (LBs) to concave cost network flow problems. The LBs are derived from state space relaxations of a dynamic programming formulation, which involve the use of non-injective mapping functions guaranteing a reduction on the cardinality of the state space. The general state space relaxation procedure is extended to address problems involving transitions that go across several stages, as is the case of network flow problems. Applications for these LBs include: estimation of the quality of heuristic solutions; local search methods that use information of the LB solution structure to find initial solutions to restart the search (Fontes et al., 2003, Networks, 41, 221–228); and branch-and-bound (BB) methods having as a bounding procedure a modified version of the LB algorithm developed here, (see Fontes et al., 2005a). These LBs are iteratively improved by penalizing, in a Lagrangian fashion, customers not exactly satisfied or by performing state space modifications. Both the penalties and the state space are updated by using the subgradient method. Additional constraints are developed to improve further the LBs by reducing the searchable space. The computational results provided show that very good bounds can be obtained for concave cost network flow problems, particularly for fixed-charge problems.     

Comparison of Two Reformulation-Linearization Technique Based Linear Programming Relaxations for Polynomial Programming Problems

In this paper, we compare two strategies for constructing linear programmingrelaxations for polynomial programming problems using aReformulation-Linearization Technique (RLT). RLT involves an automaticreformulation of the problem via the addition of certain nonlinear impliedconstraints that are generated by using the products of the simple boundingrestrictions (among other products), and a subsequent linearization based onvariable redefinitions. We prove that applying RLT directly to the originalpolynomial program produces a bound that dominates in the sense of being atleast as tight as the value obtained when RLT is applied to the jointcollection of all equivalent quadratic problems that could be constructed byrecursively defining additional variables as suggested by Shor.     

An Extension of Sums of Squares Relaxations to Polynomial Optimization Problems Over Symmetric Cones

This paper is based on a recent work by Kojima which extended sums of squares relaxations of polynomial optimization problems to polynomial semidefinite programs. Let and be a finite dimensional real vector space and a symmetric cone embedded in ; examples of and include a pair of the N-dimensional Euclidean space and its nonnegative orthant, a pair of the N-dimensional Euclidean space and N-dimensional second-order cones, and a pair of the space of m × m real symmetric (or complex Hermitian) matrices and the cone of their positive semidefinite matrices. Sums of squares relaxations are further extended to a polynomial optimization problem over , i.e., a minimization of a real valued polynomial a(x) in the n-dimensional real variable vector x over a compact feasible region , where b(x) denotes an - valued polynomial in x. It is shown under a certain moderate assumption on the -valued polynomial b(x) that optimal values of a sequence of sums of squares relaxations of the problem, which are converted into a sequence of semidefinite programs when they are numerically solved, converge to the optimal value of the problem. Research supported by Grant-in-Aid for Scientific Research on Priority Areas 16016234.     

Relaxations of vertex packing

A polynomially computable upper bound for the weighted independence number of a graph is studied. This gives rise to a convex body containing the vertex packing polytope of the graph. This body is a polytope if and only if the graph is perfect. As an application of these notions, we show that the maximum weight independent set of an h-perfect graph can be found in polynomial time.     

Using Improved Directions of Negative Curvature for the Solution of Bound-Constrained Nonconvex Problems

In this work, we describe the efficient use of improved directions of negative curvature for the solution of bound-constrained nonconvex problems. We follow an interior-point framework, in which the key point is the inclusion of computational low-cost procedures to improve directions of negative curvature obtained from a factorisation of the KKT matrix. From a theoretical point of view, it is well known that these directions ensure convergence to second-order KKT points. As a novelty, we consider the convergence rate of the algorithm with exploitation of negative curvature information. Finally, we test the performance of our proposal on both CUTEr/st and simulated problems, showing empirically that the enhanced directions affect positively the practical performance of the procedure.     

Solving Large Quadratic Assignment Problems in Parallel

Quadratic Assignment problems are in practice among the mostdifficult to solve in the class of NP-complete problems. Theonly successful approach hitherto has been Branch-and-Bound-basedalgorithms, but such algorithms are crucially dependent on good boundfunctions to limit the size of the space searched. Much work hasbeen done to identify such functions for the QAP, but with limitedsuccess.Parallel processing has also been used in order to increase the sizeof problems solvable to optimality. The systems used have, however, oftenbeen systems with relatively few, but very powerful vector processors, andhave hence not been ideally suited for computations essentially involving non-vectorizable computations on integers.In this paper we investigate the combination of one of the best bound functions for a Branch-and-Bound algorithm (the Gilmore-Lawler bound) and various testing, variable binding and recalculation of bounds between branchings when used in aparallel Branch-and-Bound algorithm. The algorithm has been implemented on a 16-processor MEIKO Computing Surface with Intel i860processors. Computational results from the solution of a number of large QAPs, including the classical Nugent 20 are reported.