Low latency multi-constraint ranking of content items

A system comprising one or more computers and one or more storage devices storing instructions that when executed by the one or more computers cause the one or more computers to perform operations comprising:

• receiving a request to rank a plurality of content items for presentation to a user to maximize a primary objective subject to a plurality of constraints, wherein the primary objective is based on respective primary metric values for each of the content items, and wherein each of the constraints corresponds to a respective second metric and is imposed based on respective second metric values for each of the content items;
• initializing a dual variable vector that includes respective values for each of a plurality of dual variables that each correspond to a different one of the constraints that are imposed based on the respective second metric values for each of the content items, wherein:
• the dual variable vector defines a ranking of the plurality of content items according to ranking scores computed using the dual variable vector, and
• the ranking score for a given content item is based on (i) a primary metric value for the given content item and (ii) a weighted sum of second metric values for the given content item, with each second metric value weighted by the value for the dual variable corresponding to the corresponding second metric in the dual variable vector;
• updating the dual variable vector, comprising, one or more iterations:
• determining an overall objective score for the dual variable vector that measures an overall performance on the primary objective and the constraints of a ranking that is generated based on the dual variable vector;
• identifying a plurality of candidate dual variable vectors that includes one or more neighboring node dual variable vectors, wherein each neighboring node dual variable vector is a different vector with respective values for the dual variables for the constraints;
• determining respective overall objective scores for each of the one or more candidate dual variable vectors;
• identifying the candidate dual variable vector with a best overall objective score;
• determining whether the identified candidate dual variable vector has a better overall objective score than the dual variable vector;
• and
• in response to determining that the identified candidate dual variable vector has a better overall objective score than the dual variable vector, updating the dual variable vector to be the identified candidate dual variable vector;
• after updating the dual variable vector, determining a final ranking for the content items based on the dual variable vector;
• and
• providing the content items for presentation to the user according to the final ranking.

One or more non-transitory computer-readable storage media storing instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

• receiving a request to rank a plurality of content items for presentation to a user to maximize a primary objective subject to a plurality of constraints, wherein the primary objective is based on respective primary metric values for each of the content items, and wherein each of the constraints corresponds to a respective second metric and is imposed based on respective second metric values for each of the content items;
• initializing a dual variable vector that includes respective values for each of a plurality of dual variables that each correspond to a different one of the constraints that are imposed based on the respective second metric values for each of the content items, wherein:
• the dual variable vector defines a ranking of the plurality of content items according to ranking scores computed using the dual variable vector, and
• the ranking score for a given content item is based on (i) a primary metric value for the given content item and (ii) a weighted sum of second metric values for the given content item, with each second metric value weighted by the value for the dual variable corresponding to the corresponding second metric in the dual variable vector;
• updating the dual variable vector, comprising, one or more iterations:
• determining an overall objective score for the dual variable vector that measures an overall performance on the primary objective and the constraints of a ranking that is generated based on the dual variable vector;
• identifying a plurality of candidate dual variable vectors that includes one or more neighboring node dual variable vectors, wherein each neighboring node dual variable vector is a different vector with respective values for the dual variables for the constraints;
• determining respective overall objective scores for each of the one or more candidate dual variable vectors;
• identifying the candidate dual variable vector with a best overall objective score;
• determining whether the identified candidate dual variable vector has a better overall objective score than the dual variable vector;
• and
• in response to determining that the identified candidate dual variable vector has a better overall objective score than the dual variable vector, updating the dual variable vector to be the identified candidate dual variable vector;
• after updating the dual variable vector, determining a final ranking for the content items based on the dual variable vector;
• and
• providing the content items for presentation to the user according to the final ranking.