In the deregulated power systems setting, the realization of the significant demand flexibility potential should be coupled with its integration in electricity markets. Centralized market mechanisms raise communication, computational and privacy issues while existing dynamic pricing schemes fail to realize the actual value of demand flexibility. In this two-part paper, a novel day-ahead pool market mechanism is proposed, combining the solution optimality of centralized mechanisms with the decentralized demand participation structure of dynamic pricing schemes and based on Lagrangian relaxation (LR) principles. Part I presents the theoretical background, algorithmic approaches and suitable examples to address challenges associated with the application of the mechanism and provides an implementation framework. Non-convexities in reschedulable demand participants' price response and their impacts on the ability of the basic LR structure to reach feasible market clearing solutions are identified and a simple yet effective LR heuristic method is developed to produce both feasible and high quality solutions by limiting the concentrated shift of reschedulable demand to the same low-priced time periods.