Runners for optimization solvers and simulators

Technologies for creating and executing a runnable that includes a decision diagram (DD)-based optimization function are capable of configuring the runnable based on runnable options data passed by the client program to a runner function, creating an executable version of the configured runnable based on context data associated with the client program, using input data read from the data source, creating a decision model and executing the executable version of the configured runnable using the decision model, and writing output produced by the executing of the executable version of the configured runnable to the data source.

TECHNICAL FIELD

A technical field to which the present disclosure relates is application programming interfaces and software development kits for state-based decision diagram optimization solvers and simulators.

BACKGROUND

In computing, an application programming interface (API) is an interface that specifies the software mechanism by which two different computer programs may communicate data and/or instructions. The API may include programming code and specifications for data exchange between the programs. For example, a calling program calls the API to request data and/or functionality provided by a called program. The API facilitates the transmission of the request to the called program and the return of data and/or functionality to the calling program.

A software development kit (SDK) is a collection of software development tools that can be used to create software applications using APIs and other pre-built components such as libraries and code samples.

DETAILED DESCRIPTION

Overview

As used herein, a decision diagram (DD) may refer to a graph-based representation of a feasible solution set for an optimization problem. For instance, a DD may be described as a layered, directed, multi-graph diagram. Examples of optimization problems are routing, scheduling, and assignment problems, such as the classic vehicle routing problem and the knapsack problem. To solve a particular optimization problem, the problem is represented by an optimization function, which may be referred to as an objective function, which may change based on a transition from one state (node on the DD) to another state (another node on the DD), and a set of optimization parameters, also known as constraints or options.

Mathematical techniques such as dynamic programming are used to model the optimization function. The resulting modeling framework can then be used to generate a feasible solution set for a given set of inputs and options. An example of a feasible solution set is a set of routes, a set of assignments, or a set of schedules that satisfies the optimization parameters for a specified set of inputs.

Software tools known as solvers and simulators can help developers automate the optimization of routing, scheduling, and assignment decisions. A solver can automate decision modeling and optimization using a decision model to generate a feasible solution set for a particular set of options. More particularly, a solver includes an algorithm that searches a state space that is represented by a decision model. The model is a representation of a state space that can be searched by a solver to find a feasible solution. Solver as used herein may refer to a particular configuration of an optimization function with a given set of options, which ingests input data, creates a decision model based on the input data and the optimization function, and outputs a feasible solution set. A simulator enables a solver to be tested and validated over a variety of use cases and execution environments.

It has been a technical challenge for decision science-based optimization software tools to accommodate dynamic routing, scheduling, and assignment problems that are subject to fluid conditions over time. Examples of fluid conditions include but are not limited to constantly changing numbers and locations of vehicles, tasks, and task participants. Existing static decision models that cannot be easily or dynamically updated to reflect these and other fluid conditions produce sub-optimal solution sets.

One example of a decision modeling and optimization tool for developers, which includes a solver that is capable of modeling and solving dynamic optimization problems, is HOP, available from nextmv.io. An example of a simulation tool that includes simulation modeling interfaces and components that can test and validate decision models produced by HOP is DASH, also available from nextmv.io. As used herein, the term runnable may be used to refer individually or collectively to a solver, a simulator, or another software tool used in conjunction with a solver and/or a simulator, or another type of state-based DD optimization program.

Software developers responsible for maintaining a computer-implemented decision science-based modeling infrastructure often experience frustration with the process of testing and deploying DD optimization solvers. Syntactic differences, nested dependencies, and inconsistencies across execution environments and platforms can cause programs not to compile, or compiled code not to link, or linked code not to import, and so on. These deployment challenges are not unique to DD optimization but the complexities inherent in DD optimization tools can render these issues computationally intractable.

As described in more detail below, the disclosed technologies facilitate the creation and use of DD-based software tools such as state-based decision diagram optimization solvers and simulators. The disclosed technologies automate and simplify the testing and deployment of DD solvers and simulators across software execution environments and hardware platforms. For example, the disclosed technologies make it easy for developers to experiment with a DD solver and/or simulator in one execution environment and then deploy the DD solver and/or simulator in a different execution environment with confidence that it will operate as expected in the new environment. Examples of execution environments and hardware platforms, which may be referred to collectively as execution environments, across which the disclosed technologies may be enabled include but are not limited to: command line interface (CLI), hypertext transfer protocol (HTTP), AWS LAMBDA and S3, GOOGLE CLOUD, and MICROSOFT AZURE. Alternatively or in addition, as used herein, execution environment may refer to a platform-independent purpose of an execution environment, such as development, testing, continuous integration, and production environments.

Example Use Case

The disclosed technologies may be described with reference to an example use case of dynamic fleet routing. For example, the disclosed technologies may be described in the context of a DD solver and/or simulator that has been configured for the classic vehicle routing problem in which the solver, given a set of dynamically changing inputs such as routes, vehicles, delivery requests, and options, creates a dynamic, state-based decision model and uses the decision model to generate and dynamically update optimized route plans for vehicles delivering items to various locations. In the vehicle routing context, examples of configurable options include vehicle carrying capacity, duration of each stop, pickup and delivery precedence, and cost functions.

The following is a brief overview of a solver, using the state-based decision diagram solver as an example. This description is provided only to illustrate the context in which some embodiments of the disclosed technologies may be used, and not to limit the scope of this disclosure.

A generic implementation of a solver is an unconfigured solver, which may be referred to as a ‘default’ solver. A default solver provides one or more solver functions, e.g., for maximization, minimization, and satisfaction of decision models, and a solver interface. A default solver may allow for other, e.g., non-DD, solver types.

The default solver implements a solver interface that can be used to define a particular implementation of the default solver. The solver interface, and thus the definition of the particular solver implementation, is contained within the default solver. This approach provides the developer with flexibility to connect different solvers and runners together. Similarly, a simulator implements a simulator interface.

A DD solver is a type of solver that searches a diagram space for feasible states (e.g., solutions), and returns either a sequence of such states or a single state at the end of the search. The disclosed technologies may be used with pre-built solvers for maximization, minimization, and satisfaction which take in a root state and solver options. The solution returned by a DD solver may contain the current incumbent state as well as solver statistics pertaining to the time that incumbent is found. If the search is not interrupted, then the final solution may be an optimal state.

A solver may be created using pre-packaged modeling primitives that are needed for building and solving decision diagrams. Solvers may operate by maintaining a queue of decision diagrams to search. Each decision diagram may be constructed top-down into a restriction of exact nodes selected at each layer by a restrictor. The remaining nodes may be deferred to search later. Solver behavior and components may be controlled and overridden by setting the values of solver options. Examples of solver options include but are not limited to diagram reducer, diagram restrictor, diagram width, duration limit, nodes limit, solutions limit, queue depth, and random seed.

A solver searches the space of decision diagrams. The solver may start the search at a root state. The search function returns the current incumbent solution at a given state, as well as solver statistics, and a flag indicating if the search function may be called again to improve the incumbent solution or prove its optimality. Other functions can be called to return all solutions and search statistics found in the search or only the last solutions found.

The searchable space of decision diagrams may represent or be referred to as a decision model. Decision models may be represented and solved using states. A state is a collection of data that represents a system and a set of decisions or choices needed to be made with respect to that system. Some decision models are defined on a root state, which corresponds to the system before making decisions, and a transition function, which makes decisions and creates new states resulting from those decisions. States may be expected to satisfy the constraints of a system.

The root state is a state that is defined assuming no decisions have been made with respect to a current search. That is, a root state may contain decisions that have already been made from a previous optimization, or from a manual operator. For example, a root path may visit only the first node, and the domain of next nodes may contain all nodes that must be visited. A solver can be used to find all feasible paths through the model. A solution may be considered feasible if all nodes are included in the path, e.g., the domain of nodes left to visit is empty.

A solver may be instructed to terminate using one or more of the limits options, which can stop the solver after a time duration, or after a number of nodes, or after a number of incumbent solutions have been found.

Other Use Cases

The disclosed technologies are not limited to vehicle routing use cases, but can be applied to routing, or scheduling, or assignment optimization problems across a number of different use cases and industries, including information technology (IT) infrastructure management, e-commerce, and on-demand delivery. In the context of IT infrastructure management, the disclosed technologies can be applied to facilitate the generation and use of solvers and simulators for optimizing job scheduling and assignments of jobs to computing resources where the computing resources may be coming online and going offline dynamically.

In the e-commerce context, the disclosed technologies can facilitate the generation and use of solvers and simulators for optimizing inventory decision-making, such as determining optimal pricing or optimal delivery windows. In the on-demand delivery context, the disclosed technologies can facilitate the generation and use of solvers and simulators for optimizing delivery schedules, task assignments, and routes for couriers. A delivery task can involve the transport of any tangible, movable item. Couriers can be any type of transporter of tangible, movable items Examples of couriers include human couriers alone or operating any type of vehicle. Other examples of couriers include any type of vehicle operating autonomously or semi-autonomously, including motorized and non-motorized vehicles, as well as ground-based and aerial vehicles.

Additionally, the disclosed technologies are not limited to the particular examples of state-based decision modeling that are described but are applicable to alternative forms and designs.

Example Computing System

FIG.1illustrates a computing system in which embodiments of the features described in this document can be implemented. In the embodiment ofFIG.1, computing system100includes a client system110, runner services130, runnable services160, and data stores170.

Client system110includes at least one computing device, such as a personal computing device, a server, a mobile computing device, or a smart appliance. Client system110includes at least one software application, including a client program112, installed on or accessible by a network to a computing device. Client program112is any type of application software system that may use functionality provided by runnable services160. For example, portions of client program112may be implemented using or include a command line interface, an AWS LAMBDA interface, or another type of interface or front-end software tool implemented using any suitable software execution environment and/or hardware platform.

Client program112may be used to create and execute runnable services160using runner services130and data obtained from data stores170. For example, client program112may include a mechanism for specifying a runnable service160to a runner service130along with input data172and options data174, a mechanism for executing runner services130and runnable services160, and mechanisms for reading data from data stores170and writing data to data stores170.

Runner services130may be implemented as callable functions that create, configure, and execute runnable services160using the approaches described herein. Example implementations of the functions and components of runner services130are shown in the drawings that follow and are described in more detail below. Portions of runner services130may be part of or accessed by or through another system, such as client program112.

Runnable services160include various types of runnable programs and associated data, which may be configured and executed by runner services. Examples of runnable services include but are not limited to solvers162and simulators168. An individual solver162has an associated decision model164and an associated optimization function166.

Examples of optimization functions166include optimization algorithms implemented in computer programming code, such as state-based DD minimizers, state-based DD maximizers, and state-based DD satisfiers. Example implementations of optimization functions166may be obtained from nextmv.io. Portions of runnable services160may be part of or accessed by or through another system, such as data stores170.

A decision model164is created by the execution of an optimization function166on a particular set of input data172given a particular set of options data174. An example of input data172is a set of possible routes through a geographic area. An example of options data174is a set of constraints for a vehicle routing problem. Decision model164may be created and deployed, into a production environment, for example, using runner services130.

An example of a simulator168is a program that ingests one or more test data sets of input data and uses the test data set(s) to evaluate the performance of a solver162by creating a software simulation of the results that would be obtained given a particular feasible solution set output by the solver. For example, a solver162may produce a set of feasible routes for a given test data set. A simulator168may generate statistical predictions relating to the feasibility of the set of feasible routes produced by the solver under various conditions.

Data stores170includes at least one digital data store, which stores digital data including input data172, options data174, and output data176. Portions of data stores170may be implemented using a combination of disk-based processing and in-memory processing. For example, portions of data stores170may be implemented as an in-memory data structure. The in-memory data structure may be configured according to a schema that is common across multiple different execution environments. In this way, the configuration of data stores170may simplify and facilitate the ingestion of input data across execution environments, thereby avoiding the need to create different, separate data ingestion programs for each individual execution environment.

Data stores170individually or collectively may reside on at least one persistent and/or volatile storage device that may reside within the same local network as at least one other device of computing system100and/or in a network that is remote relative to at least one other device of computing system100. Thus, although depicted as being included in computing system100, portions of data stores170may be part of computing system100or accessed by computing system100over a network, such as network120.

While not specifically shown, it should be understood that any of client system110, runner services130, runnable services160, and data stores170includes an interface embodied as computer programming code stored in computer memory that when executed causes a computing device to enable bidirectional communication between any of client system110, runner services130, runnable services160, and data stores170using a communicative coupling mechanism. Examples of communicative coupling mechanisms include network interfaces, inter-process communication (IPC) interfaces and application program interfaces (APIs).

A client portion of runner services130may operate in client system110, for example as a plugin or widget in a graphical user interface of a software application or as a web browser executing client program112. In an embodiment, a web browser may transmit an HTTP request over a network (e.g., the Internet) in response to user input that is received through a user interface provided by the web application and displayed through the web browser. A server running runner services130may receive the input, perform at least one operation using the input, and return output using an HTTP response that the web browser receives and processes.

Each of client system110, runner services130, runnable services160, and data stores170is implemented using at least one computing device that is communicatively coupled to electronic communications network120. Runner services130may be bidirectionally communicatively coupled to any of client system110, runnable services160, and data stores170by network120. Client system110as well as one or more different client systems (not shown) may be bidirectionally communicatively coupled to any of runner services130, runnable services160, and data stores170.

The features and functionality of client system110, runner services130, runnable services160, and data stores170are implemented using computer software, hardware, or software and hardware, and may include combinations of automated functionality, data structures, and digital data, which are represented schematically in the figures. Client system110, runner services130, runnable services160, and data stores170are shown as separate elements inFIG.1for ease of discussion but the illustration is not meant to imply that separation of these elements is required. The illustrated systems and data stores (or their functionality) may be divided over any number of physical systems, including a single physical computer system, and can communicate with each other in any appropriate manner.

Network120may be implemented on any medium or mechanism that provides for the exchange of data, signals, and/or instructions between the various components of computing system100. Examples of network120include, without limitation, a Local Area Network (LAN), a Wide Area Network (WAN), an Ethernet network or the Internet, or at least one terrestrial, satellite or wireless link, or a combination of any number of different networks and/or communication links.

It should be understood that computing system100is just one example of an implementation of the technologies disclosed herein. While the description may refer toFIG.1or to “system100” for ease of discussion, other suitable configurations of hardware and software components may be used to implement the disclosed technologies. Likewise, the particular embodiments shown in the subsequent drawings and described below are provided only as examples, and this disclosure is not limited to these exemplary embodiments.

Example Runtime Flow

FIG.2is a simplified flow diagram of an embodiment of operations and components of a computing system capable of performing aspects of the disclosed technologies. The operations of a flow200as shown inFIG.2can be implemented using processor-executable instructions that are stored in computer memory. For purposes of providing a clear example, the operations ofFIG.2are described as performed by computing system100, but other embodiments may use other systems, devices, or implemented techniques.

In flow200, a runner204is called by a calling program such as client program112. Runner204interacts with and creates an executable version of runnable202. Runnable202is one of runnable services160; e.g., a solver162or a simulator168. Runner204is one of runner services130. Runner option data214and runnable option data216are examples of options data174. Runner option data214and/or runnable option data216may be implemented using, e.g., environment variables or command line flags or data files, e.g., JSON (JavaScript Object Notation) files, or strings (e.g., sequences of text characters). Input data218is an example of input data172. For example, where runnable202is a solver, input data172is model input data, which is used to create a decision model. Output data220is an example of output data176. For example, where runnable202is a solver, output data220is a set of feasible solutions.

Runner204configures and executes runnable202. In doing so, runner204is designed to decouple the input/output processing for runnable202from the runtime program behavior of runnable202. To do this, runner204is made up of computer programming code portions including a config208, a reader210, and a writer212.

Config208reads runner options data214and configures runner204using runner option data214. Config208also reads runnable option data216and configures runnable202using runnable option data216. As a result, the configured runnable202is ready for runtime execution206by the configured runner204in response to the ingestion of input data218by reader210.

Runner and runnable option data214,216may be provided through, e.g., environment variables and/or command-line flags and/or data files and/or strings. Examples of runner option data214include but are not limited to specifications for how the runner will configure and execute the runnable, such as input data path (identifies the directory with input files), output data path (identifies the directory for storing output files), output solutions (identifies whether to output all or only the last solution). Examples of runnable option data216include but are not limited to specifications for how a runnable is to perform its task, e.g., for a solver, decision diagram width, decision diagram expansion limit.

In the implementation shown inFIG.2, runner option data214is decoupled from runnable option data216. In other implementations, runner option data214and runnable option data216are not decoupled. That is, in some implementations, runner option data214and runnable option data216may be grouped together and read from the same input.

Also, in some embodiments, runner and runnable option data214,216are read into one or more data structures that each have an appropriately defined schema that is common across multiple execution environments.

Reader210reads input data218into a data structure. In an embodiment, input data218may be in the form of a JSON file and reader210may automatically parse the JSON file into an in-memory data structure having an appropriately-defined schema. An example of an appropriately-defined schema is a schema for a dynamic routing problem. An example of a schema for a dynamic routing problem may contain, for unassigned requests, request locations and estimated times of arrival (ETAs) for drivers to reach the locations of unassigned requests; and, for assigned requests, current locations of drivers or vehicles assigned to the requests and backlog data indicating the number of assigned but uncompleted requests for a given driver or vehicle). The schema may specify that location data is provided in longitude and latitude, for example.

The data structure populated as a result of reader210reading input data218is provided or made accessible to runtime execution206along with the configured runnable202. The configured runnable202is configured according to runnable option data216by the configured runner204. The configured runner204is configured according to runner option data214.

Runtime execution206includes the creation and execution of an executable binary of the configured runnable202, where the executable binary is created using the data structure containing the automatically-parsed input data218provided by reader210. Runtime execution206outputs the results of execution of the executable binary of the configured runnable202to writer212using a data structure that has an appropriately-defined schema.

Writer212prepares output data220in a format that is compatible with or expected by the calling program, e.g., client program112. For example, writer212may produce a JSON file containing output data220. In this way, using intermediate input and output data structures, the input and output operations of runner204can be standardized across execution environments irrespective of the format in which input data218is received from the calling program and without regard for the format in which output data220is to be provided to the calling program. It should be noted that options data, such as runner options, solver options, or simulator options, may be handled using a data structure similar to the above-described manner. For example, runner and solver or simulator options may be read from one or more JSON files into an intermediate data structure and/or written from an intermediate data structure to one or more JSON files.

For example, runner204may be configured to read model input data from standard in and write solutions to standard out, in a command line execution environment. In an HTTP execution environment, runner204may be configured to read model input data from POST requests and to read option data from environment variables. In an AWS LAMBDA environment, runner204may be configured to read option data from environment variables and to read model input data from AWS LAMBDA. In an AWS LAMBDA environment with S3 triggers, runner204may be configured to read model input from an S3 input bucket and write output to an S3 output bucket, and to read option data from environment variables.

In some embodiments, the type of execution environment is parameterized. For example, an indicator of the target execution environment in which the runnable202is desired to be created, tested or deployed is passed to runner204, e.g., as a part of runner option data214. In these embodiments, runner204includes computer program code that implements logic for determining how to adapt the runner204to the target execution environment indicated by the execution type parameter.

It should be noted that adapting runner204to different execution environments does not change the inner workings of runnable202, itself. For example, runner204may be adapted to different execution environments by specifying different path names at which input data or options may be found, without altering or affecting runnable202. This is because the intermediate data structures used in the configuration and execution of runnable202are agnostic to or independent of the execution environments.

Example Runner Flow

FIG.3is a simplified flow diagram of an embodiment of operations that can be performed by at least one device of a computing system. The operations of a flow300as shown inFIG.3can be implemented using processor-executable instructions that are stored in computer memory. For purposes of providing a clear example, the operations ofFIG.3are described as performed by computing system100, but other embodiments may use other systems, devices, or implemented techniques.

In particular,FIG.3illustrates the operational phases of runner204, in one implementation. In the implementation ofFIG.3, the operational phases of runner204include an initialize phase310, a configure phase312, a prepare input phase314, a run phase316, and a prepare output phase318.

In the initialize phase310, flow300instantiates the runner by reading in context data302and runnable202. Context data302includes, for example, control data that defines how a solver or simulator program should execute. Alternatively or in addition, context data302includes configuration data, such as how long the solver or simulator program should run for (e.g., a number of iterations), the location from which the program should read input data (e.g., a file path or file system location), and the location to which the program should write output data. In this way, context data302may encompass a combination of runner options and solver options or simulator options.

InFIG.3, runnable202is an intermediate interface that encapsulates runnable options308separate from the runner behavior. Runnable202is, for example, a solver or a simulator. Runnable options308are, for example, solver options or simulator options.

In the configure phase312, flow300examines runner options data304. Runner options data304includes, for example, runtime specifications, environment variables, and any other supported configuration methods (for example, headers for HTTP). Runner options data304can change the behavior of the runnable202and runner to, for example, stream the output (e.g., feasible solutions) as they are found or use a different diagram queue.

If configure phase312completes successfully, flow300proceeds to the prepare input phase314. In prepare input phase314, flow300prepares the input data by reading from the reader210(fetching from S3, for example).

After the input data is read from reader210, flow300proceeds to run phase316. In run phase316, flow300executes the runnable (e.g., by running the solver or simulator). In run phase316, a decision model is built into a binary executable, which reads input and writes solutions to output. The binary can be called directly to solve its associated decision model.

Output of the run phase316is prepared for the calling program by prepare output phase318. In prepare output phase318, the runner options data304may specify the form of output. For example, based on runner options data304, prepare output phase318may stream the output or simply write the output bytes. An example of output that may be produced by prepare output phase318, in one implementation in which runnable202is a solver, is a set of feasible solutions written in JSON bytes. An example of output that may be produced by prepare output phase318, in one implementation in which runnable202is a simulator, is a list of output measures.

In some implementations, finer-grained control over the lifecycle of a runner can be achieved by instantiating the runner before executing. Also, in some implementations, a variadic options pattern may be introduced to allows full or partial initialization of a runner. For example, some runners are built on top of others and as a result, can override the behavior of the runners on top of which they are built. For example, a LAMBDA runner may be built for use in AWS LAMBDA. The LAMBDA runner can read input data from a request payload and write output to a response. A LAMBDA/S3 runner can be provided “on top” of the LAMBDA runner. The LAMBDA/S3 runner can override the input and output of the LAMBDA runner to instead read and write data from and to S3 buckets based on data in the request payload. This allows the runner architecture to handle large inputs and outputs in serverless environments.

Example Configure Flow

FIG.4is a flow diagram of a process that may be used to implement a portion of the computing system ofFIG.1. More specifically, flow400is an example of a process that may be used to implement the configure phase312ofFIG.3.

In flow400, a registry interface is instantiated at operation402. The registry interface allows the runner to, at operations404,406,408, delegate the configuration of the runtime program behavior of the runnable prior to execution. Operations404,406,408,410can be implemented as optional interfaces that superset other interfaces such as the runnable interface or can be added via context values. Flow400allows a runner to define its needed configuration, and allows a solver to add or override a configuration and specify that all parsing is to take place in one location (e.g., command line flags, environment variables, etc.).

For example, a solver may have a number of different interfaces that allow it to solve optimization problems across different implementations. These interfaces may include, for example, node queues, search algorithms, and node restriction and expansion algorithms. The solver may provide multiple different implementations of these interfaces, which are configurable through the solver options.

Similarly, a simulator may have a number of different interfaces for an event ledger, which make the event ledger configurable through the simulator options. Likewise, a solver such as a maximizer or minimizer may provide engine-specific interfaces, such as measures (which specify the cost of connecting two points), to make the engine configurable for different implementations. The various different interfaces may be pre-built and obtained from a library, for example, or a developer or user may supply its own specific implementations of those interfaces.

Since different implementations may require different data, the component registry allows a runner to instantiate arbitrary implementations of the required interfaces for solvers, simulators, and engines using a common schema using, for example, just JSON.

Example of Multiple Runners

FIG.5is a flow diagram of a process that may be used to implement a portion of the computing system ofFIG.1. More specifically, flow500is an example of a process that may be used to implement multiple different runners serially. An arrangement of runners such as shown inFIG.5may be useful, for example, for implementing a complex pipeline of decision modeling.

In flow500, a decision modeling pipeline includes N runners506,510,514, each configured to execute a runnable for a particular Task N, where N is a positive integer. Runners506,510,514are arranged serially so that the output of one runner is the input to the next runner. Each runner executes a different type of modeling task. For example, runner506may execute a runnable that performs clustering of input data, runner510may execute a runnable that performs routing optimization using the output of the clustering, and runner514may execute a runnable that performs time estimation optimization using the output of the route optimization. In another example, runner506may execute a runnable that runs a forecasting model; runner510may execute a runnable that executes a scheduling optimization model using the output of the forecasting model, and runner514may execute a runnable that performs business logic such as market management, driver recruitment, etc. using the output of the scheduling model.

InFIG.5, flow500is initiated by an initial event504, which is input to runner506. Runner506executes its runnable for Task1and produces output508. Runner510processes output508and executes its runnable for Task2produces output512. Runner514processes output512and executes its runnable for Task N, and produces the final output516.

Each runner506,510,514engages in input/output (I/O) operations via one or more I/O channels518and interfaces with data storage service502, to read input data and options data and write output data via the I/O channel518. Data storage service502may include one or more in-memory data structures.

In another implementation, runners are arranged in parallel so that each runner executes a runnable configured with a different objective function for the same task, using the same input data. For example, suppose there are five different possible objective functions for a routing optimization problem, and it is unknown which objective function will produce the optimal solution. A parallel, or concurrent, runner execution framework allows the same input data to be used by each of the runners executing different objective functions to produce respective sets of feasible solutions, and the framework may also provide an interface for performing AB testing on the models or otherwise evaluating and comparing the outputs of the parallel runners.

Example Hardware Architecture

According to one embodiment, the techniques described herein are implemented by at least one special-purpose computing device. The special-purpose computing device may be hard-wired to perform the techniques, or may include digital electronic devices such as at least one application-specific integrated circuit (ASIC) or field programmable gate array (FPGA) that is persistently programmed to perform the techniques, or may include at least one general purpose hardware processor programmed to perform the techniques pursuant to program instructions in firmware, memory, other storage, or a combination. Such special-purpose computing devices may also combine custom hard-wired logic, ASICs, or FPGAs with custom programming to accomplish the techniques. The special-purpose computing devices may be desktop computer systems, portable computer systems, handheld devices, mobile computing devices, wearable devices, networking devices or any other device that incorporates hard-wired and/or program logic to implement the techniques.

Computer system600and further includes a read only memory (ROM)608or other static storage device coupled to bus602for storing static information and instructions for processor604. A storage device610, such as a magnetic disk or optical disk, is provided and coupled to bus602for storing information and instructions.

Computer system600may be coupled via bus602to an output device612, such as a display, such as a liquid crystal display (LCD) or a touchscreen display, for displaying information to a computer user, or a speaker, a haptic device, or another form of output device. An input device614, including alphanumeric and other keys, is coupled to bus602for communicating information and command selections to processor604. Another type of user input device is cursor control616, such as a mouse, a trackball, or cursor direction keys for communicating direction information and command selections to processor604and for controlling cursor movement on display612. This input device typically has two degrees of freedom in two axes, a first axis (e.g., x) and a second axis (e.g., y), that allows the device to specify positions in a plane.

Computer system600may implement the techniques described herein using customized hard-wired logic, at least one ASIC or FPGA, firmware and/or program logic which in combination with the computer system causes or programs computer system600to be a special-purpose machine. According to one embodiment, the techniques herein are performed by computer system600in response to processor604executing at least one sequence of instructions contained in main memory606. Such instructions may be read into main memory606from another storage medium, such as storage device610. Execution of the sequences of instructions contained in main memory606causes processor604to perform the process steps described herein. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions.

Computer system600also includes a communication interface618coupled to bus602. Communication interface618provides a two-way data communication coupling to a network link620that is connected to a local network622. For example, communication interface618may be an integrated-services digital network (ISDN) card, cable modem, satellite modem, or a modem to provide a data communication connection to a corresponding type of telephone line. As another example, communication interface618may be a local area network (LAN) card to provide a data communication connection to a compatible LAN. Wireless links may also be implemented. In any such implementation, communication interface618sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information.

Network link620typically provides data communication through at least one network to other data devices. For example, network link620may provide a connection through local network622to a host computer624or to data equipment operated by an Internet Service Provider (ISP)626. ISP626in turn provides data communication services through the world-wide packet data communication network commonly referred to as the “Internet”628. Local network622and Internet628both use electrical, electromagnetic or optical signals that carry digital data streams. The signals through the various networks and the signals on network link620and through communication interface618, which carry the digital data to and from computer system600, are example forms of transmission media.

Computer system600can send messages and receive data, including program code, through the network(s), network link620and communication interface618. In the Internet example, a server630might transmit a requested code for an application program through Internet628, ISP626, local network622and communication interface618. The received code may be executed by processor604as it is received, and/or stored in storage device610, or other non-volatile storage for later execution.

ADDITIONAL EXAMPLES

Illustrative examples of the technologies disclosed herein are provided below. An embodiment of the technologies may include any of the examples or a combination of the described below.

In an example 1, a method includes establishing a communicative coupling between a client program and a data source; using the communicative coupling, by a runner function called by the client program, (i) configuring a runnable based on runnable options data passed by the client program to the runner function, (ii) creating an executable version of the configured runnable based on context data associated with the client program, (iii) using input data read from the data source, creating a decision model and executing the executable version of the configured runnable using the decision model, and (iv) writing output produced by the executing of the executable version of the configured runnable to the data source; the runnable including a decision diagram (DD)-based optimization function.

An example 2 includes the subject matter of example 1, further including configuring the runner function based on runner options data passed by the client program to the runner function. An example 3 includes the subject matter of example 1 or example 2, further including reading the runnable options data into an in-memory data structure and passing the in-memory data structure to the runnable; the runnable options data including at least one command line flag or at least one environment variable or at least one data file or at least one string. An example 4 includes the subject matter of any of examples 1-3, further including reading the input data into an in-memory data structure configured according to a schema that is common across a plurality of execution environments. An example 5 includes the subject matter any of examples 1-4, further including parsing the context data to determine an execution environment and executing the executable version of the configured runnable in the execution environment. An example 6 includes the subject matter of any of examples 1-5, further including passing the output to a second runner function to be used as input to the second runner function. An example 7 includes the subject matter of any of examples 1-6, further including comparing the output to output of a second runner function executed concurrently with the runner function; the runner function and the second runner functions executing different runnables. An example 8 includes the subject matter of any of examples 1-7, the runnable including a state-based decision diagram optimization solver, the input data including decision model data, and the output including a subset of the decision model data including at least one feasible route, or at least one feasible assignment, or at least one feasible schedule. An example 9 includes the subject matter of any of examples 1-8, the runnable including a state-based minimizer, or a state-based maximizer, or a state-based satisfier. An example 10 includes the subject matter of any of examples 1-9, the runnable including a simulator for a state-based decision diagram optimization solver, the input data including decision model testing data and the output including at least one performance indicator for the state-based decision diagram optimization solver based on the decision model testing data.

In an example 11, a device includes at least one computer memory; the at least one computer memory including instructions that when executed by at least one processor are capable of causing the at least one processor to perform operations including: establishing a communicative coupling between a client program and a data source; using the communicative coupling, by a runner function called by the client program, (i) configuring a runnable based on runnable options data passed by the client program to the runner function, (ii) creating an executable version of the configured runnable based on context data associated with the client program, (iii) using input data read from the data source, creating a decision model and executing the executable version of the configured runnable using the decision model, and (iv) writing output produced by the executing of the executable version of the configured runnable to the data source; the runnable including a decision diagram (DD)-based optimization function.

An example 12 includes the subject matter of example 11, where the instructions, when executed by the at least one processor, are capable of causing the at least one processor to perform operations further including configuring the runner function based on runner options data passed by the client program to the runner function. An example 13 includes the subject matter of example 11 or example 12, where the instructions, when executed by the at least one processor, are capable of causing the at least one processor to perform operations further including reading the runnable options data into an in-memory data structure and passing the in-memory data structure to the runnable; the runnable options data including at least one command line flag or at least one environment variable or at least one data file or at least one string. An example 14 includes the subject matter of any of examples 11-13, where the instructions, when executed by the at least one processor, are capable of causing the at least one processor to perform operations further including reading the input data into an in-memory data structure configured according to a schema that is common across a plurality of execution environments. An example 15 includes the subject matter of any of examples 11-14, where the instructions, when executed by the at least one processor, are capable of causing the at least one processor to perform operations further including parsing the context data to determine an execution environment and executing the executable version of the configured runnable in the execution environment. An example 16 includes the subject matter of any of examples 11-15, where the instructions, when executed by the at least one processor, are capable of causing the at least one processor to perform operations further including passing the output to a second runner function to be used as input to the second runner function. An example 17 includes the subject matter of any of examples 11-16, where the instructions, when executed by the at least one processor, are capable of causing the at least one processor to perform operations further including comparing the output to output of a second runner function executed concurrently with the runner function; the runner function and the second runner function each executing different runnables. An example 18 includes the subject matter of any of examples 11-17, the runnable including a state-based decision diagram optimization solver, the input data including decision model data, and the output including a subset of the decision model data including at least one feasible route, or at least one feasible assignment, or at least one feasible schedule. An example 19 includes the subject matter of any of examples 11-18, the runnable including a state-based minimizer, or a state-based maximizer, or a state-based satisfier. An example 20 includes the subject matter of any of examples 11-19, the runnable including a simulator for a state-based decision diagram optimization solver, the input data including decision model testing data and the output including at least one performance indicator for the state-based decision diagram optimization solver based on the decision model testing data.

In the foregoing specification, embodiments of the invention have been described with reference to numerous specific details that may vary from implementation to implementation. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense. The sole and exclusive indicator of the scope of the invention, and what is intended by the applicants to be the scope of the invention, is the literal and equivalent scope of the set of claims that issue from this application, in the specific form in which such claims issue, including any subsequent correction. Any definitions set forth herein for terms contained in the claims may govern the meaning of such terms as used in the claims. No limitation, element, property, feature, advantage or attribute that is not expressly recited in a claim should limit the scope of the claim in any way. The specification and drawings are to be regarded in an illustrative rather than a restrictive sense.

Terms such as “computer-generated” and “computer-selected” as may be used herein may refer to a result of an execution of one or more computer program instructions by one or more processors of, for example, a server computer, a network of server computers, a client computer, or a combination of a client computer and a server computer.

As used here, “online” may refer to a particular characteristic of a connections network-based system. For example, many connections network-based systems are accessible to users via a connection to a public network, such as the Internet. However, certain operations may be performed while an “online” system is in an offline state. As such, reference to a system as an “online” system does not imply that such a system is always online or that the system needs to be online in order for the disclosed technologies to be operable.

As used herein the terms “include” and “comprise” (and variations of those terms, such as “including,” “includes,” “comprising,” “comprises,” “comprised” and the like) are intended to be inclusive and are not intended to exclude further features, components, integers or steps.

Various features of the disclosure have been described using process steps. The functionality/processing of a given process step potentially could be performed in different ways and by different systems or system modules. Furthermore, a given process step could be divided into multiple steps and/or multiple steps could be combined into a single step. Furthermore, the order of the steps can be changed without departing from the scope of the present disclosure.

It will be understood that the embodiments disclosed and defined in this specification extend to alternative combinations of the individual features mentioned or evident from the text or drawings. These different combinations constitute various alternative aspects of the embodiments.