The use of optimal ATM menu structuring for different customer profiles is essential because of usability, efficiency, and customer satisfaction. Especially in competitive industries such as banking, having optimal user interface (UI) is a must. Determining the optimal menu structure is generally accomplished through manual adjustment of the menu elements. However, such an approach is inherently flawed due to the overwhelming size of the optimization variables' search space. Previous studies on menu optimization either are based on customer questionnaires or made for only a specific menu type using heuristic approaches (i.e., not generic). In this paper, we propose an systematic optimization method for menu structuring problem through a novel Mixed Integer Programming (MIP) framework. Our optimization approach is not specific to a predetermined menu class, on the contrary, the MIP model is designed to be a generic optimization framework that can be applied to a wide range of menu optimization problems. We evaluated the performance gains on a dataset of actual ATM usage logs for a period of 18 months consisting of 40 million transactions. We validated our results with both simulation application and mining of existing data logs. The results show that the proposed optimization approach provides significant reduction in the average transaction completion time and the overall click count.