Primal cutting plane algorithms revisited

Dual fractional cutting plane algorithms, in which cutting planes are used to iteratively tighten a linear relaxation of an integer program, are well-known and form the basis of the highly successful branch-and-cut method. It is rather less well-known that various primal cutting plane algorithms were developed in the 1960s, for example by Young. In a primal algorithm, the main role of the cutting planes is to enable a feasible solution to the original problem to be improved. Research on these algorithms has been almost non-existent.  In this paper we argue for a re-examination of these primal methods. We describe a new primal algorithm for pure 0-1 problems based on strong valid inequalities and give some encouraging computational results. Possible extensions to the case of general mixed-integer programs are also discussed.     

The Action Functional for Moyal Planes

Modulo some natural generalizations to noncompact spaces, we show in this Letter that Moyal planes are nonunital spectral triples in the sense of Connes. The action functional of these triples is computed, and we obtain the expected result, i.e. the noncommutative Yang–Mills action associated with the Moyal product. In particular, we show that Moyal gauge theory naturally fits into the rigorous framework of noncommutative geometry.     

A constructive characterization of the split closure of a mixed integer linear program

Two independent proofs of the polyhedrality of the split closure of mixed integer linear program have been previously presented. Unfortunately neither of these proofs is constructive. In this paper, we present a constructive version of this proof. We also show that split cuts dominate a family of inequalities introduced by Köppe and Weismantel.     

Generic Transport Aft-body Drag Reduction using Active Flow Control

Active flow-separation control is an effective and efficient mean for drag reduction and unsteady load alleviation resulting from locally or massively separated flow. Such a situation occurs in configurations where the aerodynamic performance is of secondary importance to functionality. The performance of heavy transport helicopters and aeroplanes, having a large, and almost flat, aft loading ramp suffer from the poor aerodynamics of the aft body. Hence, a combined experimental and numerical investigation was undertaken on a generic transport aeroplane/helicopter configuration. The experimental study provided surface pressures, direct drag measurements, surface and smoke flow visualization. The baseline flow was numerically analyzed, using finite volume solutions of the RANS equations. The baseline flow around the model was insensitive to the Reynolds number in the range it was tested. The flow separating from the aft body was characterized by two main sources of drag and unsteadiness. The first is a separation bubble residing at the lower ramp corner and the second is a pair of vortex systems developing and separating from the sides of the ramp. As the model incidence is decreased, the pair of vortex systems also penetrates deeper towards the centerline of the ramp, decreasing the pressure and increasing the drag. As expected, the ramp lower corner bubble was highly receptive to periodic excitation introduced from four addressable piezo-fluidic actuators situated at the ramp lower corner. Total drag was reduced by 3–11%, depending on the model incidence. There are indications that the flow in the wake of the model is also significantly steadier when the bubble at the lower ramp corner is eliminated. The vortex system is tighter and steadier when the ramp-corner bubble is eliminated.     

A Liouville type theorem for polyharmonic elliptic systems

In this paper, we consider the polyharmonic system m(−Δ)U=Vq,m(−Δ)V=Up in RN, for m>1, N>2m, with p?1, q?1, but not both equal to 1, where m(−Δ) is the polyharmonic operator. Set α=2m(q+1)/(pq−1), β=2m(p+1)/(pq−1), for α,β∈[(N−2)/2,N−2m), we prove the nonexistence of positive solutions.     

Generalised 2-circulant inequalities for the max-cut problem

The max-cut problem is a fundamental combinatorial optimisation problem, with many applications. Poljak and Turzik found some facet-defining inequalities for the associated polytope, which we call 2-circulant inequalities. We present a more general family of facet-defining inequalities, an exact separation algorithm that runs in polynomial time, and some computational results.     

Representations of unbounded optimization problems as integer programs

Any optimization problem in a finite structure can be represented as an integer or mixed-integer program in integral quantities.We show that, when an optimization problem on an unbounded structure has such a representation, it is very close to a linear programming problem, in the specific sense described in the following results. We also show that, if an optimization problem has such a representation, no more thann+2 equality constraints need be used, wheren is the number of variables of the problem.We obtain a necessary and sufficient condition for a functionf:SZ, withS Z ⁿ , to have a rational model in Meyer's sense, and show that Ibaraki models are a proper subset of Meyer models.This research was supported by NSF Grant No. GP-37510X1 and ONR Contract No. N00014-75-C0621, NR047-048.     

An evaluation of semidefinite programming based approaches for discrete lot-sizing problems

The present work is intended as a first step towards applying semidefinite programming models and tools to discrete lot-sizing problems including sequence-dependent changeover costs and times. Such problems can be formulated as quadratically constrained quadratic binary programs. We investigate several semidefinite relaxations by combining known reformulation techniques recently proposed for generic quadratic binary problems with problem-specific strengthening procedures developed for lot-sizing problems. Our computational results show that the semidefinite relaxations consistently provide lower bounds of significantly improved quality as compared with those provided by the best previously published linear relaxations. In particular, the gap between the semidefinite relaxation and the optimal integer solution value can be closed for a significant proportion of the small-size instances, thus avoiding to resort to a tree search procedure. The reported computation times are significant. However improvements in SDP technology can still be expected in the future, making SDP based approaches to discrete lot-sizing more competitive.     

On the minimal sum of Betti numbers of an almost complex manifold

We show that the only rational homology spheres which can admit almost complex structures occur in dimensions two and six. Moreover, we provide infinitely many examples of six-dimensional rational homology spheres which admit almost complex structures, and infinitely many which do not. We then show that if a closed almost complex manifold has sum of Betti numbers three, then its dimension must be a power of two.