The process of extracting coal from underground mines produces toxic and explosive gases that cause negative health effects of the miners. Monitoring the concentration of gases in underground coal mines is a mandatory process that may save lives. The health and safety of miners improves when technologies are implemented to monitor gas concentrations and provide early alarms. Wireless Sensor Networks (WSNs) can alert mine personnel when dangerous levels of gases are detected, such as methane, carbon monoxide and hydrogen sulfide, which are highly explosive and highly toxic to humans. However, the design of a WSN is not trivial, it is necessary to find the number of nodes, node location, and data routing to address two important objectives: maximizing the WSN lifetime and minimizing the costs related with the number of sensors deployed. We propose an integer optimization approach to assist the design of WSNs for gas monitoring, that allows users to address both the cost of installation and the WSN lifetime. The proposed methodology was implemented in Python, using Gurobi as our optimization solver. We developed a software to graphically represent the obtained solutions in order to facilitate stakeholders' analysis and decision making. The software uses images of the mine's layout and use the Pillow library to draw nodes and edges of the WSN. The algorithm has been applied to three case studies of mines located in Boyacá (Colombia). We also use the Networkx Python package to design random graphs and simulate larger mines to test the performance of the algorithm.