Electric dipole moments (EDM) of fundamental particles inherently violate time-reversal (T) and the combined charge-conjugation and parity symmetry (CP). We aim to measure the EDM of the muon using the frozen-spin technique within a compact storage trap. This method exploits the high effective electric field, E≈165MV/m, experienced in the rest frame of the muon with a momentum of about 23MeV/c when it passes through a solenoidal magnetic field of |B→|=2.5T. In this paper, we outline the fundamental considerations for a muon EDM search and present a conceptual design for a demonstration experiment to be conducted at secondary muon beamlines of the Paul Scherrer Institute in Switzerland. In Phase I, with an anticipated data acquisition period of 200 days, the expected sensitivity to a muon EDM is σ(d)≤4E-21e·cm. In a subsequent phase, Phase II, we propose to improve the sensitivity to σ(d)≤6E-23e·cm using a dedicated instrument installed on a different beamline that produces muons of momentum 125 MeV/c.