Exact MAX-2SAT solution via lift-and-project closure

We present a new approach for exact solution of MAX-2SAT problems based on a strong reformulation deduced from an optimal continuous solution over the elementary closure of lift-and-project cuts. Computational results show that this formulation leads to a reduced number of nodes in the branch-and-bound tree and short computing times.     

抛物型时间周期问题的Schwarz波形松驰方法

周期稳态是科学和工程系统中一类重要的运行状态,其计算复杂度远高于相应的初值问题,因此有更迫切的并行计算需要.我们提出了计算抛物型方程时间周期解的并行方法—基于区域分解(又称Schwarz方法)的波形松驰方法,该方法只需在子区域上求解较低维的周期问题.我们分析了两种不同的传输条件下方法的收敛性,并用数值实验支持了理论结果.     

A Lagrangean heuristic for the maximal covering location problem

We develop a Lagrangean heuristic for the maximal covering location problem. Upper bounds are given by a vertex addition and substitution heuristic and lower bounds are produced through a subgradient optimization algorithm. The procedure was tested in networks of up to 150 vertices. A duality gap was generally present at the end of the heuristic for the larger problems. The test problems were run in an IBM 3090-600J ‘super-computer’; the maximum computing time was kept below three minutes of CPU.     

Some Fundamental Properties of Successive Convex Relaxation Methods on LCP and Related Problems

General successive convex relaxation methods (SRCMs) can be used to compute the convex hull of any compact set, in an Euclidean space, described by a system of quadratic inequalities and a compact convex set. Linear complementarity problems (LCPs) make an interesting and rich class of structured nonconvex optimization problems. In this paper, we study a few of the specialized lift-and-project methods and some of the possible ways of applying the general SCRMs to LCPs and related problems.     

Approximate formulations for 0-1 knapsack sets

We show that for each 0<?≤1 there exists an extended formulation for the knapsack problem, of size polynomial in the number of variables, whose value is at most (1+?) times the value of the integer program.     

Using rank-1 lift-and-project closures to generate cuts for 0–1 MIPs, a computational investigation

Various techniques for building relaxations and generating valid inequalities for pure or mixed integer programming problems without special structure are reviewed and compared computationally. Besides classical techniques such as Gomory cuts, Mixed Integer Rounding cuts, lift-and-project and reformulation–linearization techniques, a new variant is also investigated: the use of the relaxation corresponding to the intersection of simple disjunction polyhedra (i.e. the so-called elementary closure of lift-and-project cuts). Systematic comparative computational results are reported on series of test problems including multidimensional knapsack problems (MKP) and MIPLIB test problems. From the results obtained, the relaxation based on the elementary closure of lift-and-project cuts appears to be one of the most promising.     

A new exact algorithm for the vehicle routing problem based onq-paths andk-shortest paths relaxations

We consider the basic Vehicle Routing Problem (VRP) in which a fleet ofM identical vehicles stationed at a central depot is to be optimally routed to supply customers with known demands subject only to vehicle capacity constraints. In this paper, we present an exact algorithm for solving the VRP that uses lower bounds obtained from a combination of two relaxations of the original problem which are based on the computation ofq-paths andk-shortest paths. A set of reduction tests derived from the computation of these bounds is applied to reduce the size of the problem and to improve the quality of the bounds. The resulting lower bounds are then embedded into a tree-search procedure to solve the problem optimally. Computational results are presented for a number of problems taken from the literature. The results demonstrate the effectiveness of the proposed method in solving problems involving up to about 50 customers and in providing tight lower bounds for problems up to about 150 customers.     

Lift-and-project cuts and perfect graphs

We analyze the application of lift-and-project to the clique relaxation of the stable set polytope. We characterize all the inequalities that can be generated through the application of the lift-and-project procedure, introduce the concept of 1-perfection and prove its equivalence to minimal imperfection. This characterization of inequalities and minimal imperfection leads to a generalization of the Perfect Graph Theorem of Lovász, as proved by Aguilera, Escalante and Nasini [1].Mathematics Subject Classification:05C17, 90C57     

Computations with disjunctive cuts for two-stage stochastic mixed 0-1 integer programs

Two-stage stochastic mixed-integer programming (SMIP) problems with recourse are generally difficult to solve. This paper presents a first computational study of a disjunctive cutting plane method for stochastic mixed 0-1 programs that uses lift-and-project cuts based on the extensive form of the two-stage SMIP problem. An extension of the method based on where the data uncertainty appears in the problem is made, and it is shown how a valid inequality derived for one scenario can be made valid for other scenarios, potentially reducing solution time. Computational results amply demonstrate the effectiveness of disjunctive cuts in solving several large-scale problem instances from the literature. The results are compared to the computational results of disjunctive cuts based on the subproblem space of the formulation and it is shown that the two methods are equivalently effective on the test instances.     

A comparison of heuristics and relaxations for the capacitated plant location problem

Approaches proposed in the literature for the Capacitated Plant Location Problem are compared. The comparison is based on new theoretical and computational results. The main emphasis is on relaxations. In particular, dominance relations among the various relaxations found in the literature are identified. In the computational study, the relaxations are compared as a function of various characteristics of the test problems. Several of these relaxations can be used to generate heuristic feasible solutions that are better than the classical greedy or interchange heuristics, both in computing time and in the quality of the solutions found.     

An Approximate Probabilistic Model for Structured Gaussian Elimination

Many of the fast methods for factoring integers and computing discrete logarithms require the solution of large sparse linear systems of equations over finite fields. Structured Gaussian elimination has been proposed as a first step in solving such sparse systems. It is a method for selecting pivots in an attempt to preserve the sparseness of the coefficient matrix. Eventually it terminates with a (smaller) residual linear system which must be solved by some other method. In many cases, the original column density is roughly proportional to the reciprocal of the of the column index. We discuss the asymptotic behavior of structured Gaussian elimination for this situation. One result is the observation that, for the column density just mentioned, the size of the residual system grows linearly with the size of the problem. This makes it possible to extrapolate the results of Monte Carlo simulation to much larger problems.     

An extension of Gilbert's algorithm for computing optimal controls

Gilbert's algorithm for computing optimal controls for systems with lumped parameters is extended to a class of control problems for systems with distributed parameters. It is also shown that the algorithm can be used to solve a larger class of problems in systems with lumped parameters than was originally considered by Gilbert.     

Overlapping Schwarz waveform relaxation method for the solution of the reaction-diffusion equation

We are interested in solving time dependent problems using domain decomposition methods. In the classical approach, one discretizes first the time dimension and then one solves a sequence of steady problems by a domain decomposition method. In this article, we treat directly the time dependent problem and we study a Schwarz waveform relaxation algorithm for the convection diffusion equation. We study the convergence of the overlapping Schwarz waveform relaxation method for solving the reaction-diffusion equation over multi-overlapped subdomains. Also we will show that the method converges linearly and superlinearly over long and short time intervals, and the convergence depends on the size of overlap. Numerical results are presented from solutions of a specific model problems to demonstrate the convergence, linear and superlinear, and the role of the overlap size.     

A Practical Algorithm for Computing a Subadditive Dual Function for Set Partitioning

Recently, a new algorithm for computing an optimal subadditive dual function to an integer program has been proposed. In this paper we show how to apply the algorithm to the set partitioning problem. We give several enhancements to the algorithm and we report computational experiments. The results show that it is tractable to obtain an optimal subadditive function for small and medium size problems. To the best of our knowledge this is the first work that reports computational experiments on computing an optimal subadditive dual function.     

试探算法与SSOR预处理共轭梯度算法的拟最佳因子

1引言在求解系数矩阵为对称正定的大型线性代数方程组Au=b (1．1)的迭代法方面,七十年代以来发展了各种预处理共轭梯度法．由于SSOR分裂中具有对称因子,可用于加速共轭梯度法,称为SSOR预处理共轭梯度法(简记为;SSORPCG．同时,由于当松弛因子ω∈(0,2)时,SSOR迭代法收敛,从而进一步发展了m步SSOR预处理共轭梯度法(简记为:m-step SSORPCG．胡家赣证明,经过最优的SSOR预条件,预优     

A branch-and-price algorithm for the capacitated facility location problem

The capacitated facility location problem (CFLP) is a well-known combinatorial optimization problem with applications in distribution and production planning. It consists in selecting plant sites from a finite set of potential sites and in allocating customer demands in such a way as to minimize operating and transportation costs. A number of solution approaches based on Lagrangean relaxation and subgradient optimization has been proposed for this problem. Subgradient optimization does not provide a primal (fractional) optimal solution to the corresponding master problem. However, in order to compute optimal solutions to large or difficult problem instances by means of a branch-and-bound procedure information about such a primal fractional solution can be advantageous. In this paper, a (stabilized) column generation method is, therefore, employed in order to solve a corresponding master problem exactly. The column generation procedure is then employed within a branch-and-price algorithm for computing optimal solutions to the CFLP. Computational results are reported for a set of larger and difficult problem instances.     

Lift-and-project for general two-term disjunctions

In this paper we generalize the cut strengthening method of Balas and Perregaard for 0/1 mixed-integer programming to disjunctive programs with general two-term disjunctions. We apply our results to linear programs with complementarity constraints.     

基于DNA计算的Hamilton图

DNA computing is a novel method for solving a class of intractable computationalproblems in which the computing can grow exponentially with problem size. Up to now, manyaccomplishments have been achieved to improve its performance and increase its reliability.Hamilton Graph Problem has been solved by means of molecular biology techniques. A smallgraph was encoded in molecules of DNA, and the “operations” of the computation wereperformed with standard protocols and enzymes. This work represents further evidence forthe ability of DNA computing to solve NP-complete search problems.     

Surrogate Gradient Algorithm for Lagrangian Relaxation

The subgradient method is used frequently to optimize dual functions in Lagrangian relaxation for separable integer programming problems. In the method, all subproblems must be solved optimally to obtain a subgradient direction. In this paper, the surrogate subgradient method is developed, where a proper direction can be obtained without solving optimally all the subproblems. In fact, only an approximate optimization of one subproblem is needed to get a proper surrogate subgradient direction, and the directions are smooth for problems of large size. The convergence of the algorithm is proved. Compared with methods that take effort to find better directions, this method can obtain good directions with much less effort and provides a new approach that is especially powerful for problems of very large size.     

A perturbation scheme for spherical arrangements with application to molecular modeling

We describe a software package for computing and manipulating the subdivision of a sphere by a collection of (not necessarily great) circles and for computing the boundary surface of the union of spheres. We present problems that arise in the implementation of the software and the solutions that we have found for them. At the core of the paper is a novel perturbation scheme to overcome degeneracies and precision problems in computing spherical arrangements while using floating point arithmetic. The scheme is relatively simple, it balances between the efficiency of computation and the magnitude of the perturbation, and it performs well in practice. In one O(n) time pass through the data, it perturbs the inputs necessary to insure no potential degeneracies and then passes the perturbed inputs on to the geometric algorithm. We report and discuss experimental results. Our package is a major component in a larger package aimed to support geometric queries on molecular models; it is currently employed by chemists working in “rational drug design”. The spherical subdivisions are used to construct a geometric model of a molecule where each sphere represents an atom.