SOLVER DEVICES AND METHODS

A system includes an agent engine, an encoder, a general-purpose solver engine, and an orchestrator. The orchestrator is configured to receive a first problem instance corresponding to a learned policy that is based on auto reinforcement learning, and provide the first problem instance to the general-purpose solver engine, which is configured to execute based on the first problem instance to determine a solver state. The orchestrator is configured to extract, from the general-purpose solver engine, the solver state, and to provide the solver state to the encoder. The encoder is configured to query the agent engine for a best action according to the learned policy and an encoded solver state. The agent engine is configured to determine the best action according to the learned policy and the encoded solver state. The orchestrator is configured to receive the best action, and direct the general-purpose solver to implement the best action.

BACKGROUND

Decision optimization seeks to optimize metrics through a formulation of objectives, constraints, and variables (decisions) which are then solved to determine the optimal decision in this setting. Example of decision optimization include: inventory management (e.g., a decision is how much stock to order at any given time); supply chain (e.g., a decision is how to fulfill some orders); and logistics (e.g., a decision is how to route vehicles to service deliveries).

The typical work flow in this setting includes determining a business problem specification (e.g., what to optimize, what key performance indicators (KPIs) to consider, what is the decision space, how often, and are all factors known or uncertain). The work flow also includes an operations research specialist defines a mathematical formulation (e.g., how can the problem be modeled in terms of constraints, variables and objectives). The work flow also includes the specialist working with data providers to implement a model/solution using existing solvers. The work flow also includes evaluating the model/solution to determine how well the metrics can be improved. The work flow also includes iteratively refining the model/solution until the model/solution can be deployed for use.

However, non-experts do not have the ability of adjust optimization models, existing solvers have a large configuration space (hundreds of parameters) that is hard to tune for specific applications, and solvers make several choices during optimization that are driven by general-purpose heuristics aimed at broad applicability.

SUMMARY

Embodiments of this disclosure include a system that includes an agent engine, an encoder, a general-purpose solver engine, and an orchestrator. The orchestrator is configured to receive a first problem instance corresponding to a learned policy that is based on auto reinforcement learning, and provide the first problem instance to the general-purpose solver engine, which is configured to execute based on the first problem instance to determine a solver state. The orchestrator is configured to extract, from the general-purpose solver engine, the solver state, and to provide the solver state to the encoder. The encoder is configured to query the agent engine for a best action according to the learned policy and an encoded solver state. The agent engine is configured to determine the best action according to the learned policy and the encoded solver state. The orchestrator is configured to receive the best action, and direct the general-purpose solver to implement the best action.

In some embodiments of the system, the best action corresponds to one or more branching policies.

In some embodiments of the system, the solver state includes a number of fixed variables and a depth of a search tree.

In some embodiments of the system, the learned policy is configured to use the number of fixed variables and the depth to establish one or more variables to branch on.

In some embodiments of the system, the one or more branching policies include the one or more variables.

In some embodiments of the system, the orchestrator is configured to direct the general-purpose solver to implement the best action comprises the orchestrator being configured to direct the general-purpose solver to branch on the one or more variables.

In some embodiments of the system, the system further includes an automated policy search engine configured to receive rollout data from the encoder, determine the learned policy using the rollout data and via offline learning, and provide the learned policy to the agent engine.

Embodiments of this disclosure include a computer-implemented method that includes: receiving, by an orchestrator, a first problem instance corresponding to a learned policy that is based on auto reinforcement learning; providing, by the orchestrator, the first problem instance to a general-purpose solver engine; executing, by the general-purpose solver engine, based on the first problem instance to determine a solver state; extracting, by the orchestrator and from the general-purpose solver engine, the solver state; providing, by the orchestrator and to an encoder, the solver state; querying, by the encoder, the agent engine for a best action according to the learned policy and an encoded solver state; determining, by the agent engine, the best action according to the learned policy and the encoded solver state; receiving, by the orchestrator, the best action; and directing, by the orchestrator, the general-purpose solver engine to implement the best action.

In some embodiments of the computer-implemented method, the best action corresponds to one or more branching policies.

In some embodiments of the computer-implemented method, the solver state includes a number of fixed variables and a depth of a search tree.

In some embodiments of the computer-implemented method, the learned policy is configured to use the number of fixed variables and the depth to establish one or more variable to branch on.

In some embodiments of the computer-implemented method, the one or more branching policies comprise the one or more variables.

In some embodiments of the computer-implemented method, directing the general-purpose solver engine to implement the best action comprises the orchestrator directing the general-purpose solver engine to branch on the one or more variables.

In some embodiments of the computer-implemented method, the computer-implemented method further includes receiving, by an automated policy search engine, rollout data from the encoder; determining, by the automated policy search engine, the learned policy using the rollout data and via offline learning; and providing, by the automated policy search engine, the learned policy to the agent engine.

Embodiments of this disclosure include a non-transitory computer-readable medium storing instructions that when executed by one or more processors, cause a solver device to: receive, by an orchestrator of the solver device, a first problem instance corresponding to a learned policy that is based on auto reinforcement learning; provide, by the orchestrator, the first problem instance to a general-purpose solver engine of the solver device; execute, by the general-purpose solver engine, based on the first problem instance to determine a solver state; extract, by the orchestrator and from the general-purpose solver engine, the solver state; provide, by the orchestrator and to an encoder of the solver device, the solver state; query, by the encoder, the agent engine for a best action according to the learned policy and an encoded solver state; determine, by the agent engine, the best action according to the learned policy and the encoded solver state; receive, by the orchestrator, the best action; and direct, by the orchestrator, the general-purpose solver engine to implement the best action.

In some embodiments of the non-transitory computer-readable medium, the best action corresponds to one or more branching policies.

In some embodiments of the non-transitory computer-readable medium, the solver state comprises a number of fixed variables and a depth of a search tree.

In some embodiments of the non-transitory computer-readable medium, the learned policy is configured to use the number of fixed variables and the depth to establish one or more variable to branch on.

In some embodiments of the non-transitory computer-readable medium, the one or more branching policies comprise the one or more variables.

In some embodiments of the non-transitory computer-readable medium, when executed by the one or more processors, the instructions are configured to direct the general-purpose solver engine to implement the best action by causing the orchestrator to direct the general-purpose solver engine to branch on the one or more variables.

DETAILED DESCRIPTION

As used within the written disclosure and in the claims, the terms “including” and “comprising” are used in an open-ended fashion, and thus should be interpreted to mean “including, but not limited to”. Unless otherwise indicated, as used throughout this document, “or” does not require mutual exclusivity, and the singular forms “a”, “an” and “the” are intended to include the plural forms as well, unless the context clearly indicates otherwise.

An engine as referenced herein may comprise of software components such as, but not limited to, computer-executable instructions, data access objects, service components, user interface components, application programming interface (API) components; hardware components such as electrical circuitry, processors, and memory; and/or a combination thereof. The memory may be volatile memory or non-volatile memory that stores data and computer executable instructions. The computer-executable instructions may be in any form including, but not limited to, machine code, assembly code, and high-level programming code written in any programming language. The engine may be configured to use the data to execute one or more instructions to perform one or more tasks.

Inference embodiments of the disclosure include devices, systems, methods, and/or computer-readable mediums that include an agent engine, an encoder, a general-purpose solver engine, and an orchestrator coupled to the agent engine, the general-purpose solver engine, and the encoder. The orchestrator is configured to interact with the general-purpose solver engine and the encoder so that the encoder queries the agent engine for a best action based on a solver state, the agent engine is configured to determine the best action based on a learned policy, and the orchestrator is configured to direct the general-purpose solver engine based on the best action.

FIG.1illustrates an example embodiment of a solver device100that coordinates a solver process and incorporates agent logic in an optimization process. The solver device100illustrates example components of a solver used during an inference phase (e.g., after auto reinforcement learning training is performed to determine a learned policy114) of the solver. The solver device100includes one or more processors101and a memory103coupled to the one or more processors103. The one or more processors101, in conjunction with the memory103(e.g., instructions stored in/on the memory), are configured to implement an agent engine102, an encoder104, a general-purpose solver engine106, and an orchestrator108coupled to the agent engine102, the encoder104, and the general-purpose solver engine106.

The orchestrator108is configured to receive a first problem instance110corresponding to the learned policy114that is based on auto reinforcement learning. The first problem instance110is an instance of a mathematical model (defined by an objective function, decision variables and constraints) for a realization of data. In some examples, the problem instance110is in the form of a mixed integer program. The learned policy114is a reinforcement learning algorithm that is learned or selected for one or more solver related tasks. The learned policy114may include tuning of one or many hyperparameters of the general-purpose solver engine106(such as, for example, which exploration strategy or feasibility-optimality tradeoff) or may be a policy for determining which branching variable to use at each step of the general-purpose solver engine106, and is based on auto reinforcement learning. Any auto reinforcement learning technique can be used to determine the learned policy114. As described in more detail below with reference toFIG.2, the learned policy114ofFIG.1is determined during a training phase.

Again with reference toFIG.1, the orchestrator108is further configured to provide the first problem instance110to the general-purpose solver engine106. The general-purpose solver engine106is a program that solves a range of mathematical optimization problems including linear programs and mixed-integer programs. The general-purpose solver engine106takes as input a definition of a mathematical optimization problem, i.e., a model. A model consists minimally of an objective function, decision variables, and sets of constraints. The aim of the general-purpose solver engine106is to determine the value of decision variables that maximize a stated objective. A model instance is an instantiation of the model with specific data. Once defined, the general-purpose solver engine106is configured to run an optimization algorithm and to returns the optimal objective function value and associated decision variables. As some examples, the general-purpose solver engine106may be international business machines (IBM®) ILOG CPLEX, CVXPY, or SCIP.

The general-purpose solver engine106is configured to execute based on the first problem instance110. During execution the solver state112, which captures attributes of the general-purpose solver engine106during the solution process, is determined. In some examples, the solver state112includes a number of fixed variables and a depth of a search tree.

The orchestrator108is configured to extract, from the general-purpose solver engine106, the solver state112, and provide the solver state112to the encoder104.

The encoder104is configured to encode the solver state112to generate an encoded solver state113and to query the agent engine102for a best action116according to the learned policy114. The encoded solver state113is a learnt representation of the solver state112and is used for training and inference of the learned policy114. In some examples, the encoder104is configured to encode the solver state112by generating a fixed length embedding or a graph representation of the solver state112using any technique. In some examples, the best action116corresponds to one or more branching policies. In some examples, the encoder104is configured to query the agent engine102by sending the agent engine102the encoded solver state113.

The agent engine102is configured to determine the best action116according to the learned policy114and the encoded solver state113. In an example in which the solver state112includes the number of fixed variables and the depth of the search tree and the best action116corresponds to one or more branching policies, the agent engine102may be configured to implement the learned policy114to use the number of fixed variables and the depth of the search tree to establish one or more variables to branch on. In this example, the best action116corresponds to the one or more variables to branch on that are established via the learned policy114.

The orchestrator108is further configured to receive the best action116from the agent engine102and direct the general-purpose solver engine106to implement the best action116. The orchestrator108may direct the general-purpose solver engine106to implement the best action116by sending the general-purpose solver engine106an instruction118to implement the best action116. In the example in which the best action116corresponds to the one or more variables to branch on that are established via the learned policy114, the orchestrator108is configured to direct the general-purpose solver engine106to implement the best action116at least in part by directing the general-purpose solver engine106to branch on the one or more variables. In this example, the instruction118may identify the one or more variables and may instruct the general-purpose solver engine106to branch on the one or more variables.

FIG.2illustrates an example embodiment of a solver device200for determining a learned policy214(which may correspond to the learned policy114ofFIG.1) that can be used during an inference phase. The solver device200includes one or more processors201and a memory203coupled to the one or more processors203. The one or more processors201, in conjunction with the memory203(e.g., instructions stored on the memory203) are configured to implement an agent engine202, an encoder204, a general-purpose solver engine206, an auto policy search engine220coupled to the encoder204and the agent engine202, and an orchestrator108coupled to the agent engine202, the encoder204, and the general-purpose solver engine206.

During the training phase, the orchestrator208is configured to receive a plurality of problem instances210, and provide the plurality of problem instances210to the general-purpose solver engine206(which may correspond to the general-purpose solver engine106described above with reference toFIG.1). The general-purpose solver engine206is configured to execute based on the plurality of problem instances210to determine representation of effectiveness212of the general-purpose solver engine206for the plurality of problem instances210. In some examples, the representation of the effectiveness212of the general-purpose solver engine206corresponds to a respective solver state-action-reward for each respective instance of the plurality of problem instances210.

The orchestrator208is configured to extract the representation of the effectiveness212of the general-purpose solver engine206for the plurality of problem instances210(e.g., the respective solver state-action-rewards for the plurality of problem instances210), and provide the representation of the effectiveness212to the encoder204. The encoder204is configured to encode the representation of the effectiveness212into rollout data222using any technique, and to provide the rollout data222to the auto policy search engine220.

The auto policy search engine220is configured to receive the rollout data222(from the encoder204) and a plurality of reinforcement learning algorithms224(e.g., N reinforcement learning algorithms including a first reinforcement learning algorithm230. . . an Nth reinforcement learning algorithm232), determine (e.g., via a policy search function228) a learned policy214from the plurality of reinforcement learning algorithms224(and comprising tuned hyperparameters) using the rollout data222and via offline learning226. As an example, the auto policy search engine220may determine the first reinforcement learning algorithm230with tuned hyperparameters as the learned policy214. In some examples, the auto policy search engine220is configured to employ a two-level limited discrepancy search technique, which at the first level selects a policy algorithm (e.g., the first reinforcement learning algorithm230) from the plurality of reinforcement learning algorithms224, and at the second level determines associated hyperparameters of the selected reinforcement learning algorithm. In some examples, the auto policy search engine220is configured to determine the learned policy214according to IBM's® automated decision optimization system called AutoDO.

The auto policy search engine220provides the learned policy214to the agent engine202, which stores the learned policy214for use during an inference phase.

FIG.3illustrates an example flowchart of a computer-implemented method300. The computer-implemented method300may be performed by the system100ofFIG.1after being trained using the system200ofFIG.2.

The computer-implemented method300ofFIG.3includes, at302, receiving, by an orchestrator, a first problem instance corresponding to a learned policy that is based on auto reinforcement learning. For example, the orchestrator may correspond to the orchestrator108described above with reference toFIG.1, the first problem instance may correspond to the first problem instance110described above with reference toFIG.1, and the learned policy may correspond to the learned policy114described above with reference toFIG.1.

In some examples, the learned policy of the computer-implemented method300is determined during a training phase as described above with reference to the learned policy214ofFIG.2. For example, the learned policy of the computer-implemented method300may be determined (as described above with reference toFIG.2) at least in part by receiving, by an automated policy search engine, rollout data from the encoder; determining, by the automated policy search engine, the learned policy using the rollout data and via offline learning; and providing, by the automated policy search engine, the learned policy to the agent engine.

The computer-implemented method300ofFIG.3further includes, at304, providing, by the orchestrator, the first problem instance to a general-purpose solver engine. For example, the orchestrator108ofFIG.1may provide the first problem instance110to the general-purpose solver engine106as described above with reference toFIG.1.

The computer-implemented method300ofFIG.3further includes, at306, executing, by the general-purpose solver engine, based on the first problem instance to determine a solver state. For example, the general-purpose solver engine106ofFIG.1may execute based on the first problem instance110ofFIG.1to determine the solver state112ofFIG.1as described above with reference toFIG.1. In some examples, the solver state of the computer-implemented method300includes a number of fixed variables and a depth of the search tree as described above with reference toFIG.1.

The computer-implemented method300ofFIG.3further includes, at308, extracting, by the orchestrator and from the general-purpose solver engine, the solver state. For example, the orchestrator108ofFIG.1may extract the solver state112ofFIG.1from the general-purpose solver engine106as described above with reference toFIG.1.

The computer-implemented method300ofFIG.3further includes, at310, providing, by the orchestrator and to the encoder, the solver state. For example, the orchestrator108ofFIG.1may provide the solver state112ofFIG.1to the encoder104ofFIG.1as described above with reference toFIG.1.

The computer-implemented method300ofFIG.3further includes, at312, querying, by the encoder, the agent engine for a best action according to the learned policy and an encoded solver state. For example, the encoder104ofFIG.1may provide the encoded solver state113ofFIG.1to the agent engine102ofFIG.1as described above with reference toFIG.1.

The computer-implemented method300ofFIG.3further includes, at314, determining, by the agent engine, the best action according to the learned policy and the encoded solver state. For example, the agent engine102ofFIG.1may determine the best action116ofFIG.1according to the learned policy114and the encoded solver state113as described above with reference toFIG.1. In some example, the best action116is one or more branching policies. In some examples, when the solver state of the computer-implemented method300ofFIG.1includes a number of fixed variables to branch on and a depth of a search tree, the learned policy of the computer-implemented method300is configured to use the number of fixed variables and the depth of the search tree to establish one or more variables to branch on. In this example, the one or more branching policies include the one or more variables.

The computer-implemented method300ofFIG.3further includes, at316, receiving, by the orchestrator, the best action. For example, the orchestrator108ofFIG.1may receive the best action116ofFIG.1as described above with reference toFIG.1.

The computer-implemented method300ofFIG.3further includes, at318, directing, by the orchestrator, the general-purpose solver engine to implement the best action. For example, the orchestrator108ofFIG.1may direct the general-purpose solver engine106ofFIG.1to implement the best action116ofFIG.1as described above with reference toFIG.1. As an example, the orchestrator108ofFIG.1may send the general-purpose solver engine106ofFIG.1the instruction118ofFIG.1. In some examples, directing the general-purpose solver engine to implement the best action includes the orchestrator directing the general-purpose solver engine to branch on the one or more variables.

FIG.4illustrates an example embodiment of a computing environment400. Computing environment400contains an example of an environment for the execution of at least some of the computer code involved in performing the inventive methods, such as solver445. In addition to block445, computing environment400includes, for example, computer401, wide area network (WAN)402, end user device (EUD)403, remote server404, public cloud405, and private cloud406. In this embodiment, computer401includes processor set410(including processing circuitry420and cache421), communication fabric411, volatile memory412, persistent storage413(including operating system422and block200, as identified above), peripheral device set414(including user interface (UI), device set423, storage424, and Internet of Things (IoT) sensor set425), and network module415. Remote server404includes remote database430. Public cloud405includes gateway440, cloud orchestration module441, host physical machine set442, virtual machine set443, and container set444.

Computer401may take the form of a desktop computer, laptop computer, tablet computer, smart phone, smart watch or other wearable computer, mainframe computer, quantum computer or any other form of computer or mobile device now known or to be developed in the future that is capable of running a program, accessing a network or querying a database, such as remote database430. As is well understood in the art of computer technology, and depending upon the technology, performance of a computer-implemented method may be distributed among multiple computers and/or between multiple locations. On the other hand, in this presentation of computing environment400, detailed discussion is focused on a single computer, specifically computer401, to keep the presentation as simple as possible. Computer401may be located in a cloud, even though it is not shown in a cloud inFIG.4. On the other hand, computer401is not required to be in a cloud except to any extent as may be affirmatively indicated.

Processor set410includes one, or more, computer processors of any type now known or to be developed in the future. Processing circuitry420may be distributed over multiple packages, for example, multiple, coordinated integrated circuit chips. Processing circuitry420may implement multiple processor threads and/or multiple processor cores. Cache421is memory that is located in the processor chip package(s) and is typically used for data or code that should be available for rapid access by the threads or cores running on processor set410. Cache memories are typically organized into multiple levels depending upon relative proximity to the processing circuitry. Alternatively, some, or all, of the cache for the processor set may be located “off chip.” In some computing environments, processor set410may be designed for working with qubits and performing quantum computing.

Communication Fabric411is the signal conduction paths that allow the various components of computer401to communicate with each other. Typically, this fabric is made of switches and electrically conductive paths, such as the switches and electrically conductive paths that make up busses, bridges, physical input/output ports and the like. Other types of signal communication paths may be used, such as fiber optic communication paths and/or wireless communication paths.

Volatile Memory412is any type of volatile memory now known or to be developed in the future. Examples include dynamic type random access memory (RAM) or static type RAM. Typically, the volatile memory is characterized by random access, but this is not required unless affirmatively indicated. In computer401, the volatile memory412is located in a single package and is internal to computer401, but, alternatively or additionally, the volatile memory may be distributed over multiple packages and/or located externally with respect to computer401.

Persistent Storage413is any form of non-volatile storage for computers that is now known or to be developed in the future. The non-volatility of this storage means that the stored data is maintained regardless of whether power is being supplied to computer401and/or directly to persistent storage413. Persistent storage413may be a read only memory (ROM), but typically at least a portion of the persistent storage allows writing of data, deletion of data and re-writing of data. Some familiar forms of persistent storage include magnetic disks and solid state storage devices. Operating system422may take several forms, such as various known proprietary operating systems or open source Portable Operating System Interface type operating systems that employ a kernel. The code included in block200typically includes at least some of the computer code involved in performing the inventive methods.

Peripheral Device Set414includes the set of peripheral devices of computer401. Data communication connections between the peripheral devices and the other components of computer401may be implemented in various ways, such as Bluetooth connections, Near-Field Communication (NFC) connections, connections made by cables (such as universal serial bus (USB) type cables), insertion type connections (for example, secure digital (SD) card), connections made though local area communication networks and even connections made through wide area networks such as the internet. In various embodiments, UI device set423may include components such as a display screen, speaker, microphone, wearable devices (such as goggles and smart watches), keyboard, mouse, printer, touchpad, game controllers, and haptic devices. Storage424is external storage, such as an external hard drive, or insertable storage, such as an SD card. Storage424may be persistent and/or volatile. In some embodiments, storage424may take the form of a quantum computing storage device for storing data in the form of qubits. In embodiments where computer401is required to have a large amount of storage (for example, where computer401locally stores and manages a large database) then this storage may be provided by peripheral storage devices designed for storing very large amounts of data, such as a storage area network (SAN) that is shared by multiple, geographically distributed computers. IoT sensor set425is made up of sensors that can be used in Internet of Things applications. For example, one sensor may be a thermometer and another sensor may be a motion detector.

End User Device (EUD)403is any computer system that is used and controlled by an end user (for example, a customer of an enterprise that operates computer401), and may take any of the forms discussed above in connection with computer401. EUD403typically receives helpful and useful data from the operations of computer401. For example, in a hypothetical case where computer401is designed to provide a recommendation to an end user, this recommendation would typically be communicated from network module415of computer401through WAN402to EUD403. In this way, EUD403can display, or otherwise present, the recommendation to an end user. In some embodiments, EUD403may be a client device, such as thin client, heavy client, mainframe computer, desktop computer and so on.

Remote Server404is any computer system that serves at least some data and/or functionality to computer401. Remote server404may be controlled and used by the same entity that operates computer401. Remote server404represents the machine(s) that collect and store helpful and useful data for use by other computers, such as computer401. For example, in a hypothetical case where computer401is designed and programmed to provide a recommendation based on historical data, then this historical data may be provided to computer401from remote database430of remote server404.

Public Cloud405is any computer system available for use by multiple entities that provides on-demand availability of computer system resources and/or other computer capabilities, especially data storage (cloud storage) and computing power, without direct active management by the user. Cloud computing typically leverages sharing of resources to achieve coherence and economies of scale. The direct and active management of the computing resources of public cloud405is performed by the computer hardware and/or software of cloud orchestration module441. The computing resources provided by public cloud405are typically implemented by virtual computing environments that run on various computers making up the computers of host physical machine set442, which is the universe of physical computers in and/or available to public cloud405. The virtual computing environments (VCEs) typically take the form of virtual machines from virtual machine set443and/or containers from container set444. It is understood that these VCEs may be stored as images and may be transferred among and between the various physical machine hosts, either as images or after instantiation of the VCE. Cloud orchestration module441manages the transfer and storage of images, deploys new instantiations of VCEs and manages active instantiations of VCE deployments. Gateway440is the collection of computer software, hardware, and firmware that allows public cloud405to communicate through WAN402.

Private Cloud406is similar to public cloud405, except that the computing resources are only available for use by a single enterprise. While private cloud406is depicted as being in communication with WAN402, in other embodiments a private cloud may be disconnected from the internet entirely and only accessible through a local/private network. A hybrid cloud is a composition of multiple clouds of different types (for example, private, community or public cloud types), often respectively implemented by different vendors. Each of the multiple clouds remains a separate and discrete entity, but the larger hybrid cloud architecture is bound together by standardized or proprietary technology that enables orchestration, management, and/or data/application portability between the multiple constituent clouds. In this embodiment, public cloud405and private cloud406are both part of a larger hybrid cloud.