In the U.S., total 94,000 crashes (Fatal 710, Injury 36,290, and PDO 57,000) occurred in work zones in 2017. The economic cost to these crashes is estimated at nearly $17.5 billion. Data revealed that there is a greater risk of injury crashes on interstate highways compared to other functional classification of roadways. In order to improve work zone safety on interstate highways, this study proposed an optimization methodology that basically identifies a best subset of safety countermeasures in each work zone of a network. The subset of safety countermeasures was selected based on several factors including crash modification factors, safety benefits, traffic counts, implementation costs, benefit-to-cost ratio (BCR), and most importantly limited budget. Linear integer optimization technique was utilized to identify the best subset of safety countermeasures. The methodology was implemented successfully on a dataset to verify the applicability of the model.