The increasing popularity of social networks has initiated a fertile research area in information extraction and data mining. Although such analysis can facilitate better understanding of sociological, behavioral, and other interesting phenomena, there is growing concern about personal privacy being breached, thereby requiring effective anonymization techniques. If we consider the social graph to be a weighted graph, then the problem of anonymization can be of various types: node identity anonymization, structural anonymization, or edge weight anonymization. In this paper, we consider edge weight anonymization. Our approach builds a linear programming (LP) model which preserves properties of the graph that are expressible as linear functions of the edge weights. Such properties form the foundations of many important graph-theoretic algorithms such as single source shortest paths tree, all-pairs shortest paths, k-nearest neighbors, minimum cost spanning tree, etc. Off-the-shelf LP solvers can then be used to find solutions to the resulting model where the computed solution forms the weights of the anonymized graph. As a proof of concept, we choose the shortest paths problem and its extensions, prove the correctness of the constructed models, analyze their complexity, and experimentally evaluate the proposed techniques using real social network data sets. Our experiments demonstrate that not only does the proposed technique anonymize the weights, but it also improves the k-anonymity of the graphs while scrambling the relative ordering of the edge-weights, thereby providing robust and effective anonymization of the sensitive edge-weights.