This article investigates the construction of linkage maps by means of the reconstruction of hidden inheritance vectors. An inheritance vector provides a description of the origin of marker alleles in an individual in terms of a binary code indicating the grandparental origin of the alleles. The practical application that is considered is the full-sib family of a diploid outbreeding species. Essentially, map construction is considered as an optimization problem in which marker data are used as restrictions on hidden inheritance vectors. Simulated annealing, a form of combinatorial optimization, is used to minimize the number of recombinations between adjacent markers. The new algorithm is applied to simulated data as well as to practical data obtained from a cross between two apple cultivars. For the practical data, a detailed procedure for examining the reliability of individual markers and their positions on the map is presented. Extensions of the method for more complicated population structures are discussed.