This paper proposes a novel method for preference relaxation in online product search, which enables consumers to make quality choices without suffering from the commonly experienced information overload. In online shopping scenarios that involve multi-attribute choice tasks, it can be difficult for consumers to process the vast amounts of information available and to make satisfactory buying decisions. In such situations consumers are likely to eliminate potentially good choices early on, using hard-constraint filtering tools. Our approach uses edge sets to identify the alternatives on the soft boundary and the principle of alternative domination to suppress the alternatives on this boundary that are irrelevant. We demonstrate how our approach outperforms existing methods for product search in a set of simulations using two sets of 2650 car advertisements and 1813 digital cameras gathered from a popular online store. (c) 2012 Elsevier Ltd. All rights reserved.