Many processor architectures provide a set of addressing modes in their address generation units. For example DSPs (digital signal processors) have powerful addressing modes for efficiently implementing numerical algorithms. Typical addressing modes of DSPs are auto post-modification and indexing for address registers. The selection of he optimal addressing modes in the means of minimal code size and minimal execution time depends on many parameters and is NP complete in general. In this work we present a new approach for solving the addressing mode selection (AMS) problem. We provide a method for modeling the target architecture?s addressing modes as cost functions for a partitioned boolean quadratic optimization problem (PBQP). For solving the PBQP we present an efficient and effect way to implement large matrices for modeling the cost model. We have integrated the addressing mode selection with the Atair C-Compiler for the uPD7705x DSP from NEC. In our experiments we show hat the addressing mode selection can be optimally solved for almost all benchmark programs and the compile-time overhead of the address mode selection is within acceptable bounds for a production DSP compiler.