Constraint solver execution service and infrastructure therefor

Patent metadata

Field	Value
Publication number	US-10977111-B2
Application number	US-201816115408-A
Country	US
Kind code	B2
Filing date	Aug 28, 2018
Priority date	Aug 28, 2018
Publication date	Apr 13, 2021
Grant date	Apr 13, 2021

Abstract

A constraint solver service of a computing resource service provider performs evaluations of logic problems provided by the service provider's users and/or services by deploying a plurality of constraint solvers to concurrently evaluate the logic problem. Each deployed solver has, or is configured with, different characteristics and/or capabilities than the other solvers; thus, the solvers can have varying execution times and ways of finding a solution. The service may control execution of the solvers using virtual computing resources, such as by installing and configuring a solver to execute in a software container instance. The service receives solver results and delivers them according to a solution strategy such as “first received” to reduce latency or “check for agreement” to validate the solution. An interface allows the provider of the logic problem to select and configure solvers, issue commands and modifications during solver execution, select the solution strategy, and receive the solution.

First claim

What is claimed is:

1. A system, comprising one or more processors and memory storing computer-executable instructions that, when executed by the one or more processors, cause the system to:
receive a first request to evaluate a logic problem associated with a problem source, wherein the problem source is one of a user of a computing resource service provider, and a service of the computing resource service provider;
determine that the first request includes a first set of problem statements describing at least a first portion of the logic problem;
select, based at least in part on the first request, one or more solvers from a plurality of available constraint solvers configured to be installed by the system;
communicate with a container management system of the computing resource service provider to cause the container management system to:
obtain one or more container images each associated with a corresponding solver of the one or more solvers, the one or more container images each comprising software and data needed to install the corresponding solver;
provision available virtual computing resources of the computing resource service provider as a plurality of container instances;
install one of the one or more container images into each of the plurality of container instances to produce a plurality of solver instances each configured to operate one of the one or more solvers as an executable program, such that each of the one or more solvers corresponds to at least one of the plurality of solver instances; and
deploy the plurality of solver instances into a virtual computing environment of the computing resource service provider;

send the first set of problem statements to each of the plurality of solver instances;
send to each of the plurality of solver instances a solve command that causes the corresponding solver operated by the solver instance to evaluate the logic problem and produce a corresponding result;
obtain a first result produced by a first solver of the one or more solvers, the first solver operated by a first solver instance of the plurality of solver instances; and
perform an action associated with obtaining the first result.

2. The system of claim 1 , wherein to perform the action, the instructions, when executed, cause the system to:
determine that the first result is produced before the corresponding result of any other solver instance of the plurality of solver instances;
send a notification to the problem source indicating that the first result is available; and
send, to each of the plurality of solver instances other than the first solver instance, a terminate command that causes the corresponding solver operated by the solver instance to stop evaluating the logic problem.

3. The system of claim 1 , wherein operation of the first solver is configurable by setting values of a set of configuration parameters, and prior to sending the solve command to the plurality of solver instances, the instructions, when executed, further cause the system to:
determine, based at least in part on the first request, a first configuration of the set of configuration parameters and a second configuration of the set of configuration parameters;
determine that a second solver instance of the plurality of solver instances is configured to operate the first solver;
cause the first solver instance to operate the first solver using the first configuration; and
cause the second solver instance to operate the first solver using the second configuration.

4. The system of claim 1 , wherein the user is the problem source and the instructions, when executed, further cause the system to:
provide, to a computing device associated with the user and in communication with the system via the internet, a web interface that enables the user to transmit, to the system as a first user input, the first set of problem statements and settings identifying the one or more solvers;
receive the first user input as the first request; and
select the one or more solvers using the settings.

5. The system of claim 1 , wherein:
the web interface further enables the user to transmit to the system:
as a second user input, a second set of problem statements describing a second portion of the logic problem; and
the solve command as a third user input; and

the instructions, when executed, further cause the system to:
receive the second user input;
determine, based on the second user input, that the second set of problem statements is associated with the logic problem;
send, to each of the plurality of solver instances:
the second set of problem statements; and
an append command that causes the solver instance to combine the first and second sets of problems statements as the logic problem to be evaluated; and

receive the third user input, wherein the system sends the solve command to the plurality of solver instances in response to receiving the third user input.

6. A system, comprising one or more processors and memory storing, for each of a plurality of available constraint solvers configured to be installed by the system, corresponding software resources needed to install the available constraint solver as an executable program, the memory further storing computer-executable instructions that, when executed by the one or more processors, cause the system to:
obtain a logic problem;
determine a number N of solver instances to be used to evaluate the logic problem;
determine, based on requirements associated with at least one of the plurality of available constraint solvers, one or more encodings of the logic problem;
select one or more solvers from the plurality of available constraint solvers;
using the corresponding software resources of the one or more solvers, instantiate N solver instances in a virtual computing environment, each solver instance of the N solver instances comprising virtual computing resources configured to execute a corresponding solver of the one or more solvers and storing a corresponding encoding, of the one or more encodings, that is readable by the corresponding solver;
send to each of the N solver instances a solve command that causes the corresponding solver executing on the solver instance to evaluate the corresponding encoding and produce a corresponding result describing one of a plurality of solutions to the logic problem;
obtain a first result produced by a first solver of the one or more solvers from a first encoding of the one or more encodings; and
perform an action associated with obtaining the first result.

7. The system of claim 6 , wherein executing the instructions further causes the system to:
generate the first encoding as a first set of problem statements representing the logic problem and formatted in a first format readable by the first solver; and
generate a second encoding of the one or more encodings, the second encoding comprising a second set of problem statements representing the logic problem and formatted in a second format readable by a second solver of the one or more solvers, the second solver executing on a second solver instance of the N solver instances, the second solver instance storing the second encoding.

8. The system of claim 6 , wherein executing the instructions further causes the system to:
generate the first encoding as a first set of problem statements representing the logic problem and formatted in a first format readable by the first solver; and
generate a second encoding of the one or more encodings, the second encoding comprising a second set of problem statements representing the logic problem and formatted in the first format, the second set of problem statements being different from the first set of problem statements, the second encoding being eval

Assignees

• Amazon Tech Inc

Inventors

• Rungta Neha
• Kahsai Azene Temesghen
• Bolignano Pauline Virginie
• Luckow Kasper Soe
• Mclaughlin Sean
• Dodge Catherine
• Gacek Andrew Jude
• Varming Carsten
• Cook John Byron
• Schwartz-Narbonne Daniel
• Hortala Juan Rodriguez

Classifications

• G06F8/60

  Software deployment · CPC title

• G06F11/3672

  Test management · CPC title

• G06F9/5077

  Logical partitioning of resources; Management or configuration of virtualized resources (specific details on emulation or internal functioning of virtual machines G06F9/455) · CPC title

• G06F9/45558 Primary

  Hypervisor-specific management and integration aspects · CPC title

• G06F2009/45562

  Creating, deleting, cloning virtual machine instances · CPC title