Warehouses are nowadays the scene of complex logistic problems integrating different decision layers. In this paper we address the Joint Order Batching, Picker Routing and Sequencing Problem with Deadlines in rectangular warehouses. To tackle the problem we propose an exponential linear programming formulation that is solved with a column generation heuristic able to provide lower and upper bounds. We show that the problem is related to the bin-packing problem rather than a scheduling problem. We take advantage to this aspect to derive a number of valid inequalities that enhance the resolution of the Master Problem. The proposed algorithm is evaluated on publicly available data-sets. It is able to optimally solve instances with up to 18 orders and to provide high-quality lower bounds or even to prove optimality for larger instances of 100 orders. A key interest is to assert the quality of the numerous heuristics proposed in this area.