Methods, systems, and apparatus, including computer programs encoded on computer storage media, for re-ranking a collection of documents according to a first metric and subject to a constraint on a function of one or more second metrics. One of the methods includes: obtaining, for each document in the first collection of documents, a respective first metric value corresponding to the first metric and respective one or more second metric values corresponding to the one or more second metrics; re-ranking the first collection of documents, comprising: determining the constraint on the function of one or more second metrics by computing a first threshold value using a variable threshold function that takes as input second metric values for the documents in the first collection of documents; and determining the re-ranking for the first collection of documents by solving a constrained optimization for the first metric constrained by the first threshold value.