Abstract Combined heat and power (CHP) production is an increasingly important energy production technology. CHP production is usually applied in back pressure plants, where the heat and power generation follows a joint characteristic. A CHP system may also comprise separate heat and power production facilities. Cost-efficient operation of a CHP system can be planned using an optimisation model based on hourly load forecasts. A long-term optimisation model decomposes into thousands of hourly models, which can be formulated as linear programming (LP) problems. We model the hourly CHP operation as an LP problem with a special structure and present the specialised Power Simplex algorithm that utilises this structure efficiently. The basis can be organised as an identity matrix and a small block of non-zero coefficients. There are only a few different types of non-zero blocks, and extremely fast inversion procedures have been designed for each type. The performance of Power Simplex is compared with realistic models against a non-sparse tabular Simplex algorithm and the LP2 software based on the sparse Revised Simplex algorithm using the product form of inverse. At its best, Power Simplex performs from 21 to 190 times faster than the tabular Simplex. Power Simplex has been implemented as part of the EHTO NEXUS energy optimisation system, which is in commercial use at several Finnish energy companies.