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.     

Polynomial size IP formulations of knapsack may require exponentially large coefficients

A desirable property of integer formulations is to consist of few inequalities having small coefficients. We show that these targets are conflicting by proving the existence of knapsack sets that need exponentially many inequalities or exponentially large coefficients in any integer formulation. Moreover, we show that there exist undirected graphs such that (in a natural model) every integer formulation of stable sets requires exponentially large coefficients if the number of non-trivial inequalities is bounded by a constant.     

Lifting the knapsack cover inequalities for the knapsack polytope

Valid inequalities for the knapsack polytope have proven to be very useful in exact algorithms for mixed-integer linear programming. In this paper, we focus on the knapsack cover inequalities, introduced in 2000 by Carr and co-authors. In general, these inequalities can be rather weak. To strengthen them, we use lifting. Since exact lifting can be time-consuming, we present two fast approximate lifting procedures. The first procedure is based on mixed-integer rounding, whereas the second uses superadditivity.     

Threshold arrangements and the knapsack problem

We show that a combinatorial question which has been studied in connection with lower bounds for the knapsack problem by V.E. Brimkov and S.S. Dantchev [An alternative to Ben-Or’s lower bound for the knapsack problem complexity, Applied Mathematics Letters 15 (2) (2002) 187–191] is related to threshold graphs, threshold arrangements, and other well-studied combinatorial objects, and we correct an error in the analysis given in that paper.     

A class of nonlinear nonseparable continuous knapsack and multiple-choice knapsack problems

This paper considers a general class of continuous, nonlinear, and nonseparable knapsack problems, special cases of which arise in numerous operations and financial contexts. We develop important properties of optimal solutions for this problem class, based on the properties of a closely related class of linear programs. Using these properties, we provide a solution method that runs in polynomial time in the number of decision variables, while also depending on the time required to solve a particular one-dimensional optimization problem. Thus, for the many applications in which this one-dimensional function is reasonably well behaved (e.g., unimodal), the resulting algorithm runs in polynomial time. We next develop a related solution approach to a class of continuous, nonlinear, and nonseparable multiple-choice knapsack problems. This algorithm runs in polynomial time in both the number of variables and the number of variants per item, while again dependent on the complexity of the same one-dimensional optimization problem as for the knapsack problem. Computational testing demonstrates the power of the proposed algorithms over a commercial global optimization software package.     

Verification and reformulation of the competitive exclusion principle

Biodiversity conservation is becoming increasingly urgent. It is important to find mechanisms of competitive coexistence of species with different fitness in especially difficult circumstances – on one limiting resource, in isolated stable uniform habitat, without any trade-offs and cooperative interactions. Here we show a such mechanism of competitive coexistence based on a soliton-like behaviour of population waves. We have modelled it by the logical axiomatic deterministic individual-based cellular automata method. Our mechanistic models of population and ecosystem dynamics are of white-box type and so they provide direct insight into mechanisms under study. The mechanism provides indefinite coexistence of two, three and four competing species. This mechanism violates the known formulations of the competitive exclusion principle. As a consequence, we propose a fully mechanistic and most stringent formulation of the principle.     

The discretized sum-product and projection theorems

We give a new presentation of the discrete ring theorem for sets of real numbers [B]. Special attention is given to the relation between the various parameters. As an application, new Marstrand type projection theorems are obtained and formulated either in terms of box or Hausdorff dimension. It is shown that the dimension of the projections satisfies a nontrivial lower bound outside a very sparse set of exceptional directions.     

On the equilibria of finely discretized curves and surfaces

Our goal is to identify the type and number of static equilibrium points of solids arising from fine, equidistant n-discretizations of smooth, convex surfaces. We assume uniform gravity and a frictionless, horizontal, planar support. We show that as n approaches infinity these numbers fluctuate around specific values which we call the imaginary equilibrium indices associated with the approximated smooth surface. We derive simple formulae for these numbers in terms of the principal curvatures and the radial distances of the equilibrium points of the solid from its center of gravity. Our results are illustrated on a discretized ellipsoid and match well the observations on natural pebble surfaces.     

On the supermodular knapsack problem

In this paper we introduce binary knapsack problems where the objective function is nonlinear, and investigate their Lagrangean and continuous relaxations. Some of our results generalize previously known theorems concerning linear and quadratic knapsack problems. We investigate in particular the case in which the objective function is supermodular. Under this hypothesis, although the problem remains NP-hard, we show that its Lagrangean dual and its continuous relaxation can be solved in polynomial time. We also comment on the complexity of recognizing supermodular functions. The particular case in which the knapsack constraint is of the cardinality type is also addressed and some properties of its optimal value as a function of the right hand side are derived.Work done while the authors were visiting Rutgers University.     

Facets of the knapsack polytope

A necessary and sufficient condition is given for an inequality with coefficients 0 or 1 to define a facet of the knapsack polytope, i.e., of the convex hull of 0–1 points satisfying a given linear inequality. A sufficient condition is also established for a larger class of inequalities (with coefficients not restricted to 0 and 1) to define a facet for the same polytope, and a procedure is given for generating all facets in the above two classes. The procedure can be viewed as a way of generating cutting planes for 0–1 programs.     

离散的Burgers-Ginzburg-Landau方程组的吸引子

文章通过对空间变量的有限差分方法离散了具有周期边值的Ｂｕｒｇｅｒｓ Ｇｉｎｚｂｕｒｇ Ｌａｎｄａｕ方程组．研究了这个离散方程组初值问题解的适定性．证明了当差分网格足够大时离散方程组存在吸引子，并得到了吸引子的Ｈａｕｓｄｏｒｆｆ维数和分形维数的上界估计．这个上界不会随着网格的加细而无限增大，因此数值分析离散的有限维系统的吸引子可以近似探讨原无限维系统的吸引子．     

Cyclic group and knapsack facets

 Any integer program may be relaxed to a group problem. We define the master cyclic group problem and several master knapsack problems, show the relationship between the problems, and give several classes of facet-defining inequalities for each problem, as well as a set of mappings that take facets from one type of master polyhedra to another. Received: May 24, 2001 / Accepted: August 2002 Published online: March 21, 2003 Mathematics Subject Classification (1991): 20E28, 20G40, 20C20     

Global optimization and multi knapsack: A percolation algorithm

Since the standard multi knapsack problem, may be rewritten as a reverse convex problem, we present a global optimization approach. It is known from solving high dimensional nonconvex problems that pure cutting plane methods may fail and branch-and-bound is impractical, due to a large duality gap. On the other hand, a strategy based on some sufficient optimality condition does not help much because it requires generating all level set points, an intractable problem. Therefore, we propose to combine both a cutting plane method and a sufficient optimality condition together with a random generation of level set points where the number of points is limited by a tabu list to prevent re-examination of the same level set area. Experiments show that we end up with a small duality gap allowing a subsequent branch-and-bound approach to prove optimality.     

On the continuous quadratic knapsack problem

We introduce a new algorithm for the continuous bounded quadratic knapsack problem. This algorithm is motivated by the geometry of the problem, is based on the iterative solution of a series of simple projection problems, and is easy to understand and implement. In practice, the method compares favorably to other well-known algorithms (some of which have superior worst-case complexity) on problem sizes up ton = 4000.     

Multi-Standard Quadratic Optimization: interior point methods and cone programming reformulation

A Standard Quadratic Optimization Problem (StQP) consists of maximizing a (possibly indefinite) quadratic form over the standard simplex. Likewise, in a multi-StQP we have to maximize a (possibly indefinite) quadratic form over the Cartesian product of several standard simplices (of possibly different dimensions). Among many other applications, multi-StQPs occur in Machine Learning Problems. Several converging monotone interior point methods are established, which differ from the usual ones used in cone programming. Further, we prove an exact cone programming reformulation for establishing rigorous yet affordable bounds and finding improving directions.     

The vertices of the knapsack polytope

The number of vertices of a polytope associated to the Knapsack integer programming problem is shown to be small. An algorithm for finding these vertices is discussed.     

Solving the knapsack problem via -transform

Given vectors and , we consider the (unbounded) knapsack optimization problem . We compute the minimum value p^* using techniques from complex analysis, namely Cauchy's Residue Theorem to integrate a function in , and the -transform of an appropriate function related to . The computational complexity depends on s ∑_j=1ⁿa_j, not on the magnitude of b as in dynamic programming based approaches. We also completely characterize the number of solutions with value less than p, as a function of p.     

Model theoretic reformulation of the Baum-Connes and Farrell-Jones conjectures

The Isomorphism Conjectures are translated into the language of homotopical algebra, where they resemble Thomason's descent theorems.     

Note on the knapsack Markov chain

We show that for sufficiently large knapsacks the associated Markov chain on the state space of the admissible packings of the knapsack is rapidly mixing. Our condition basically states that at least half of all items should fit into the knapsack. This is much weaker than the condition assumed by Saloff-Coste (1997).