Melody harmonization through Integer programming

This work presents a model that utilizes exact combinatorial optimization methods to generate the harmonization of a given four-four melody in the key of C major/A from a proposed set of chords. A linear programming formulation has been developed with the objective of identifying the most favorable sequence of chords from a given set. This is achieved by considering a matrix of transition costs based on rules of harmony theory and commonly used chord progressions in Pop music. The resulting musical accompaniment is integrated with the melody and visualized using MuseScore4. To assess the model’s outputs, a comparison has been conducted between the chords used in well-known songs and the chords chosen by the model for those songs. If developed, the proposed model could serve as an educational tool for composers and provide support in discovering new ideas for accompaniment to complement their melodies.