Linear programming for the 0–1 quadratic knapsack problem

In this paper we consider the quadratic knapsack problem which consists in maximizing a positive quadratic pseudo-Boolean function subject to a linear capacity constraint. We propose a new method for computing an upper bound. This method is based on the solution of a continuous linear program constructed by adding to a classical linearization of the problem some constraints rebundant in 0–1 variables but nonredundant in continuous variables. The obtained upper bound is better than the bounds given by other known methods. We also propose an algorithm for computing a good feasible solution. This algorithm is an elaboration of the heuristic methods proposed by Chaillou, Hansen and Mahieu and by Gallo, Hammer and Simeone. The relative error between this feasible solution and the optimum solution is generally less than 1%. We show how these upper and lower bounds can be efficiently used to determine the values of some variables at the optimum. Finally we propose a branch-and-bound algorithm for solving the quadratic knapsack problem and report extensive computational tests.     

Valid inequalities for the multi-dimensional multiple-choice 0–1 knapsack problem

This paper presents a study of the polytope defined by the minimizing form of the binary knapsack inequality, which is a greater-than-or-equal-to constraint, augmented by disjoint generalized upper bound constraints. A set of valid inequalities, called $\alpha$-cover inequalities, is characterized and dominance relationships among them are established. Both sequential and sequence-independent lifting procedures are presented to tighten an $\alpha$-cover inequality that is not facet defining. Computational results aimed at evaluating the strength of the non-dominated, sequentially, and sequence-independent lifted $\alpha$-cover inequalities are provided.     

An exact algorithm for the 0–1 linear knapsack problem with a single continuous variable

The 0–1 linear knapsack problem with a single continuous variable (KPC) is an extension of the binary knapsack problem (KP). It is an NP-hard problem. In this paper, we show that KPC can be reduced to KP and a pseudo-knapsack problem (PKP), which is similar to the traditional knapsack problem except that the profits of items may be non-positive, and the weight sum has two sided limits on capacity. We use the Dynamic Programming algorithm COMBO (Martello et al., Manag Sci 45(3):414–424, 1999) to solve KP, and modify the branch and bound method EXPKNAP (Pisinger, Eur J Oper Res 87:175–187, 1995) for KP to solve the PKP. Numerical experiments show the efficiency of our method.     

Implementing an efficient fptas for the 0–1 multi-objective knapsack problem

In the present work, we are interested in the practical behavior of a new fully polynomial time approximation schemes (fptas) to solve the approximation version of the 0–1 multi-objective knapsack problem. The proposed methodology makes use of very general techniques (such as dominance relations in dynamic programming) and thus may be applicable in the implementation of fptas for other problems as well.     

An evolutionary heuristic for quadratic 0–1 programming

In this paper we present a heuristic algorithm for the well-known Unconstrained Quadratic 0–1 Programming Problem. The approach is based on combining solutions in a genetic paradigm and incorporates intensification algorithms used to improve solutions and speed up the method. Extensive computational experiments on instances with up to 500 variables are presented and we compare our approach both with powerful heuristic and exact algorithms from the literature establishing the effectiveness of the method in terms of solutions quality and computing time.     

On surrogating 0–1 knapsack constraints

In this note, we present a scheme for tightening 0–1 knapsack constraints based on other knapsack constraints surrogating. The preparation of this paper was partially supported by DGICYT through grant N. PB95-0407     

An application of the fixed point theorem to the inverse sturm–liouville problem

The Sturm–Liouville operators −y″ + v(x)y on [0, 1] with Dirichlet boundary conditions y(0) = y(1) = 0 are considered. For any 1 ≤ p < ∞, a short proof of the characterization theorem for the spectral data corresponding to v ∈ L^p(0, 1) is given. Bibliography: 10 titles.     

Some computational results on real 0–1 knapsack problems

The most recent algorithms to solve binary knapsack problems employ Lagrangean based reduction schemes to fix on or off a significant portion of the variables. This paper points out that, on hard problems encountered in practice, the repeated. application of an LP-based reduction on the pivot variable can greatly shorten solution times     

An application of a qd-type discrete hungry Lotka–Volterra equation over finite fields to a decoding problem

In this paper, the decoding problem for multiple Bose–Chaudhuri–Hocquenghem (BCH)-Goppa codes over the same finite field is investigated. A new iterative decoding algorithm is proposed based on the quotient difference (qd)-type discrete hungry Lotka–Volterra equation over finite fields. Compared with certain existing algorithms, the proposed algorithm manifests its advantage in computational complexity. A few of examples are presented to demonstrate its efficiency.     

An application of weighted Hardy spaces to the Navier–Stokes equations

In this article, we consider the mapping properties of convolution operators with smooth functions on weighted Hardy spaces H^p(w)$H^p(w)$ with w   belonging to Muckenhoupt class _A∞$A_{\infty }$. As a corollary, one obtains decay estimates of heat semigroup on weighted Hardy spaces. After a weighted version of the div–curl lemma is established, these estimates on weighted Hardy spaces are applied to the investigation of the decay property of global mild solutions to Navier–Stokes equations with the initial data belonging to weighted Hardy spaces.     

Fractional 0–1 programming: applications and algorithms

We consider a class of nonlinear integer optimization problems commonly known as fractional 0–1 programming problems (also, often referred to as hyperbolic 0–1 programming problems), where the objective is to optimize the sum of ratios of affine functions subject to a set of linear constraints. Such problems arise in diverse applications across different fields, and have been the subject of study in a number of papers during the past few decades. In this survey we overview the literature on fractional 0–1 programs including their applications, related computational complexity issues and solution methods including exact, approximation and heuristic algorithms.     

An algorithm to perform a complete right-hand-side parametrical analysis for a 0–1-integer linear programming problem

We designed and implemented an algorithm to solve the continuous right-hand side parametric 0–1-Integer Linear Programming (ILP) problem, that is to solve a family of 0–1-ILP problems in which the problems are related by having identical objective and matrix coefficients. Our algorithm works by choosing an appropiate finite sequence of non-parametric 0–1-Mixed Integer Linear Programming (MILP) problems in order to obtain a complete parametrical analysis. The algorithm may be implemented by using any software capable of solving MILP problems.     

Optimization of chance constraint programming with sum-of-fractional objectives – An application to assembled printed circuit board problem

This paper presents a procedure to solve a chance constraint programming problem with sum-of-fractional objectives. The problem and the solution procedure are described with the help of a practical problem – assembled printed circuit boards (PCBs). Errors occurring during assembling PCBs are in general classified into three kinds, viz. machine errors, manual errors and other errors. These errors may lead to the rejection of the major portion of the production and hence result the manufacturer a huge loss. The problem is decomposed to have two objective functions; one is a sum-of-fractional objectives and the other is a non-linear objective with bounded constraints. The interest is to maximize the sum-of-fractional objectives and to minimize the non-linear objective, subject to stochastic and non-stochastic bounded environment. The first problem deals with the maximization of the profit (maximizing sum-of-fractional objectives) and the second deals with the minimization of the loss (errors), so as to obtain the maximum profit after removing the number of defective PCBs.     

About the stability of the inverse problem in 1-D wave equations—application to the interpretation of seismic profiles

This paper is devoted to the study of the following inverse problem: Given the 1-D wave equation: (1) $$\begin{gathered} \rho (z)\frac{{\partial ^2 y}}{{\partial t^2 }} - \frac{\partial }{{\partial z}}\left( {\mu (z)\frac{{\partial y}}{{\partial z}}} \right) = 0 z > 0,t > 0 \hfill \\ + boundary excitation at z = 0 + zero initial conditons \hfill \\ \end{gathered} $$ how to determine the parameter functions (ρ(z),μ(z)) from the only boundary measurementY(t) ofy(z, t)/z=0. This inverse problem is motivated by the reflection seismic exploration techniques, and is known to be very unstable. We first recall in §1 how to constructequivalence classes σ(x) of couples (ρ(z),ρ(z)) that areundistinguishable from the givenboundary measurements Y(t). Then we give in §2 existence theorems of the solutiony of the state equations (1), and study the mappingσ→Y: We define on the set of equivalence classes Σ={σ(x)|σ _min ?σ(x) ? σ _max for a.e.x} (σ _min andσ _max a priori given) a distanced which is weak enough to make Σ compact, but strong enough to ensure the (lipschitz) continuity of the mappingσ→Y. This ensures the existence of a solution to the inverse problem set as an optimization problem on Σ. The fact that this distanced is much weaker than the usualL ² norm explains the tendency to unstability reported by many authors. In §3, the case of piecewise constant parameter is carefully studied in view of the numerical applications, and a theorem of stability of the inverse problem is given. In §4, numerical results on simulated but realistic datas (300 unknown values forσ) are given for the interpretation of seismic profiles with the above method.