The concept of bandwidth adaptation which additionally allocates the terminated bandwidth to ongoing calls is one of the promising methods to reduce the new call blocking and handoff call dropping probabilities. In this paper, we formulate the bandwidth allocation problem for the bandwidth adaptation as a binary linear integer program which maximizes the satisfaction degree of customers. Since this optimization should be performed in real time, we presented a computationally efficient heuristic algorithm for the problem based on the Lagrangean relaxation procedure. Our simulation test shows that the algorithm finds a sub-optimal solution within 0.5% in average from the true optimal solution. The solutions of our scheme show better performance than other scheme in both handoff call dropping and new call blocking probabilities.