Stochastic Lagrangean Heuristics for the Knapsack Problem

This paper describes a stochastic gradient method for combinatorial optimization and its application to the knapsack problem. The method approximates derivatives by sampling and searches in a continuous space defined by Lagrangean heuristics. Firstly, the Lagrangean heuristics for the knapsack problem are proposed based on Lagrangean relaxation and repair heuristics. A stochastic gradient approximation technique and a solution framework of the stochastic gradient method are then introduced and applied to the Lagrangean heuristics. Their convergence behaviors are discussed based on numerical study. Roughness of the solution space defined by the proposed formulation is discussed using a fractalness measure. (in preparation)

By: Hiroyuki Okano

Published in: RT0600 in 2007

This Research Report is not available electronically. Please request a copy from the contact listed below. IBM employees should contact ITIRC for a copy.

Questions about this service can be mailed to .