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)