Improved dynamic programming and approximation results for the knapsack problem with setups

In this paper, we consider the 0–1 knapsack problem with setups. Items are grouped into families and if any items of a family are packed, this induces a setup cost as well as a setup resource consumption. We introduce a new dynamic programming algorithm that performs much better than a previous dynamic program and turns out to be also a valid alternative to an exact approach based on the use of an Integer Linear Programming (ILP) solver. Then we present a general inapproximability result. Furthermore, we investigate several relevant special cases that still permit fully polynomial‐time approximation schemes and others where the problem remains hard to approximate.     

The covering problem for linear context-free grammars

Language equivalence, grammatical covering and structural equivalence are all notions of similarity defined on context-free grammars. We show that the problem of determining whether an arbitrary linear context-free grammar covers another is complete for the class of languages accepted by polynomially space bounded Turing machines. We then compare the complexity of this problem with the analogous problems for language equivalence and structural equivalence, not only for linear grammars, but also for regular grammars and unrestricted context-free grammars. As a step in obtaining the main result of this paper, we show that the equivalence problem for linear s-grammars is decidable in polynomial time.     

The Turing degree of the inherent ambiguity problem for context-free languages

The inherent ambiguity question for context-free languages is shown to be in the Turing degree of unsolvability O”. The method used is to show that the inherent ambiguity question is equivalent to the finiteness question for r.e. sets which is in degree O”. The proof associates a context-free language with each Turing machine. The language has a natural closed-form definition in terms of the Turing machine. The associated language is inherently ambiguous precisely iof the Turing machine accepts an infinite set.     

A dynamic programming method with lists for the knapsack sharing problem

In this paper, we propose a method to solve exactly the knapsack sharing problem (KSP) by using dynamic programming. The original problem (KSP) is decomposed into a set of knapsack problems. Our method is tested on correlated and uncorrelated instances from the literature. Computational results show that our method is able to find an optimal solution of large instances within reasonable computing time and low memory occupancy.     

A subclass of deterministic context-free languages with a decidable inclusion problem

A new subclass of deterministic context-free languages with a decidable inclusion problem is described in terms of finite automata on the direct product of free semigroups. The decidability proof exploits the structural properties of the automata.Translated from Kibernetika, No. 2, pp. 12–17, March–April, 1990.     

一种求解线性约束的非线性规划神经网络方法

针对线性约束的非线性规划的求解问题,利用罚函数求解优化问题的思想将其转化为二次凸规划,基于神经网络的结构特性,定义所需的能量函数,从而使网络收敛于唯一稳定点最终实现线性约束的非线性规划的求解。实验仿真结果表明,该方法是有效和正确的,且能推广到含参的非线性规划和多目标规划中去。     

On the generalized Wolf problem: Preprocessing of nonnegative large-scale linear programming problems with group constraints

Nonnegative large-scale linear programming problems with group constraints are extremely important for different applications in economics, technology, and other spheres. In this paper, we describe a new approach to preprocessing of these problems so that to reduce their dimensions considerably by defining and removing redundant constraints and variables.     

Closure properties of linear context-free tree languages with an application to optimality theory

Context-free tree grammars, originally introduced by Rounds [Math. Systems Theory 4(3) (1970) 257–287], are powerful grammar devices for the definition of tree languages. The properties of the class of context-free tree languages have been studied for more than three decades now. Particularly important here is the work by Engelfriet and Schmidt [J. Comput. System Sci. 15(3) (1977) 328–353, 16(1) (1978) 67–99]. In the present paper, we consider a subclass of the class of context-free tree languages, namely the class of linear context-free tree languages. A context-free tree grammar is linear, if no rule permits the copying of subtrees. For this class of linear context-free tree languages we show that the grammar derivation mode, which is very important for the general class of context-free tree languages, is immaterial. The main result we present is the closure of the class of linear context-free tree languages under linear frontier-to-root tree transduction mappings. Two further results are the closure of this class under linear root-to-frontier tree transduction mappings and under intersection with regular tree languages.     

A projective method for linear programming with box-type constraints

A specialization of the projective method for linear programming to problems with lower and upper bounds on the variables is proposed.     

A computational study on the quadratic knapsack problem with multiple constraints

The quadratic knapsack problem (QKP) has been the subject of considerable research in recent years. Despite notable advances in special purpose solution methodologies for QKP, this problem class remains very difficult to solve. With the exception of special cases, the state-of-the-art is limited to addressing problems of a few hundred variables and a single knapsack constraint.In this paper we provide a comparison of quadratic and linear representations of QKP based on test problems with multiple knapsack constraints and up to eight hundred variables. For the linear representations, three standard linearizations are investigated. Both the quadratic and linear models are solved by standard branch-and-cut optimizers available via CPLEX. Our results show that the linear models perform well on small problem instances but for larger problems the quadratic model outperforms the linear models tested both in terms of solution quality and solution time by a wide margin. Moreover, our results demonstrate that QKP instances larger than those previously addressed in the literature as well as instances with multiple constraints can be successfully and efficiently solved by branch and cut methodologies.     

A projective method for linear programming with box-type constraints

A specialization of the projective method for linear programming to problems with lower and upper bounds on the variables is proposed.This work was done while the author was visiting New York University.     

On the equivalence and containment problems for context-free languages

LetG andG ₀ be context-free grammars. Necessary and sufficient conditions onG ₀ are obtained for the decidability ofL(G ₀) L((G) It is also shown that it is undecidable for whichG ₀,L(G) is decidable. Furthermore, given thatL(G) is decidable for a fixedG ₀, there is no effective procedure to determine the algorithm which decidesL(G) IfL(G ₀) is a regular set,L(G) = L(G ₀) is decidable if and only ifL(G ₀) is bounded. However, there exist non-regular, unboundedL(G ₀) for whichL(G) = L(G ₀) is decidable.     

Approximation for knapsack problems with multiple constraints

1IntroductionTheknapsackproblemisawelLknowncombinatorialoptimizationproblemthatfindsapplicationstocapitalbudgeting,loadingproblems,solutionoflargeoptimizationproblems,andcomputersystems.Anextensiveliteratureexistsonapproximationalgorithmsforvariousformsofknapsackproblems['--'l.Inthispaper,westudytheapproximationforfourkindsofknapsackproblemswithmultipleconstraints:0/1MultipleConstraintKnapsackProblem(0/1MCKP),IntegerMultipleConstraintKnapsackProblem(IntegerMCKP),0/1k-ConstraintKnapsack…     

A linear programming approach for multivariable feedback control with inequality constraints

A multivariable control scheme which explicitly includes inequality constraints on the state, control and output variables is developed using a linear programming (LP) formulation. A suboptimal feedback control policy results since the LP calculations are repeated at each sampling instant. A number of important properties related to the LP control problem are obtained from a theoretical analysis. Simulation results illustrate that the on-line computational requirements are modest and that the new LP approach compares favourably with existing methods such as optimal feedback control