  In automated decision making processes in the online fashion industry, the
'predict-then-optimize' paradigm is frequently applied, particularly for
markdown pricing strategies. This typically involves a mixed-integer
optimization step, which is crucial for maximizing profit and merchandise
volume. In practice, the size and complexity of the optimization problem is
prohibitive for using off-the-shelf solvers for mixed integer programs and
specifically tailored approaches are a necessity. Our paper introduces specific
heuristics designed to work alongside decomposition methods, leading to
almost-optimal solutions. These heuristics, which include both primal heuristic
methods and a cutting plane generation technique within a Lagrangian
decomposition framework, are the core focus of the present paper. We provide
empirical evidence for their effectiveness, drawing on real-world applications
at Zalando SE, one of Europe's leading online fashion retailers, highlighting
the practical value of our work. The contributions of this paper are deeply
ingrained into Zalando's production environment to its large-scale catalog
ranging in the millions of products and improving weekly profits by millions of
Euros.
