This paper describes a negotiation application where one of the parties has products and services as described by a catalog. In such an environment, the final deal must be based on actual entries in the catalog. However, negotiation can be performed, at least partially, on hypothetical entries. The method described herein is based on a general e-commerce framework that employs goal programming (GoP) models to describe deals (including constraints, preferences and tradeoffs) as well as for automating activities such as deal valuation, negotiations, auctions, etc.