𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Solving the generalized knapsack problem with variable coefficients

✍ Scribed by Kaj Holmberg; Kurt Jörnsten

Publisher
John Wiley and Sons
Year
1996
Tongue
English
Weight
1012 KB
Volume
43
Category
Article
ISSN
0894-069X

No coin nor oath required. For personal study only.

✦ Synopsis

In this article we present methods based on Lagrangian duality and decomposition techniques for the generalized knapsack problem with variable coefficients. The Lagrangian dual is solved with subgradient optimization or interval bisection. We also describe a heuristic that yields primal feasible solutions. Combining the Lagrangian relaxation with a primal (Benders) subproblem yields the subproblem phase in cross decomposition. By using averages in this procedure, we get the new mean-value cross-decomposition method. Finally, we describe how to insert this into a globally convergent generalized Benders decomposition framework, in the case that there is a duality gap. Encouraging computational results for the optimal generating unit commitment problem are presented.

📜 SIMILAR VOLUMES

A domain decomposition method for solvin
A domain decomposition method for solving thin film elliptic interface problems with variable coefficients
✍ Weizhong Dai; Raja Nassar 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 100 KB 👁 2 views

A domain decomposition method is developed for solving thin "lm elliptic interface problems with variable coe$cients. In this study, the elliptic equation with variable coe$cients is discretized using second-order "nite di!erences while a discrete interface equation is obtained using the immersed in

Generalized Binomial Coefficients and th
Generalized Binomial Coefficients and the Subset–Subspace Problem
✍ John Konvalina 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 150 KB

Generalized binomial coefficients of the first and second kind are defined in terms of object selection with and without repetition from weighted boxes. The combinatorial definition unifies the binomial coefficients, the Gaussian coefficients, and the Stirling numbers and their recurrence relations

Mixing cell method for solving the solut
Mixing cell method for solving the solute transport equation with spatially variable coefficients
✍ Guang-Te Wang; V. P. Singh; Shulin Chen 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 183 KB 👁 2 views

The advection±dispersion equation with spatially variable coecients does not have an exact analytical solution and is therefore solved numerically. However, solutions obtained with several of the traditional ®nite dierence or ®nite element techniques typically exhibit spurious oscillation or numeric