Cogeneration of heat and electricity is an important pillar of energy and climate policy. To plan the production and distribution system of combined heat and power (CHP) systems for residential heating, suitable methods for decision support are needed. For a comprehensive feasibility analysis, the integration of the location and capacity planning of the power plants, the choice of customers, and the network planning of the heating network into one optimization model are necessary. Thus, we develop an optimization model for electricity generation and heat supply. This mixed integer linear program (MILP) is based on graph theory for network flow problems. We apply the network location model for the optimization of district heating systems in the City of Osorno in Chile, which exhibits the “checkerboard layout” typically found in many South American cities. The network location model can support the strategic planning of investments in renewable energy projects because it permits the analysis of changing energy prices, calculation of break-even prices for heat and electricity, and estimation of greenhouse gas emission savings.