# US 12,118,482 B2 · Method and system for optimizing an objective having discrete constraints > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,118,482 B2 - Document ID: US12118482B2 - Status: Granted - Kind: B2 - Application number: 17/153,257 - Filed: 2021-01-20 - Published: 2021-07-22 - Granted: 2024-10-15 - Earliest claimed: 2020-01-21 - Applicants: Kinaxis Inc. - Inventors: Brian Keng; Anneya Golob; Yifeng He - Web page: https://patentgrep.com/patent/US12118482B2 ## CPC - G06Q 10/04: Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" (market predictions or forecasting for commercial activities G06Q30/0202) - G06F 17/11: for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)} - G06F 18/217: {Validation; Performance evaluation; Active pattern learning techniques} - G06F 18/24143: {Distances to neighbourhood prototypes, e.g. restricted Coulomb energy networks [RCEN]} - G06F 18/24317: {Piecewise classification, i.e. whereby each classification requires several discriminant rules} - G06N 3/006: based on simulated virtual individual or collective life forms, e.g. social simulations or particle swarm optimisation [PSO] - G06N 3/092: Reinforcement learning - G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks - G06N 20/00: Machine learning - G06N 3/045: Combinations of networks - G06N 3/08: Learning methods - G06Q 10/0637: Strategic management or analysis, e.g. setting a goal or target of an organisation; Planning actions based on goals; Analysis or evaluation of effectiveness of goals - G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS ## Abstract A system and method for optimizing an objective having discrete constraints using a dataset, the dataset including a plurality of aspects associated with the objective. The method comprising: receiving the dataset, the objective, and constraints, at least one of the constraints comprising discrete values; receiving a seed solution comprising initial values for the at least the constraints; iteratively performing until a predetermined threshold is reached: determining a constraint space for each of the constraints have discrete values using a determination of a constraint satisfaction problem; determining an optimized value of the objective using an optimization model, the optimization model taking as input the dataset and the constraint space; and outputting the optimized objective. ## Claims ### Claim 1 A method for optimizing a retail promotion having discrete constraints using a dataset, the dataset comprising a plurality of aspects associated with the retail promotion including historical sales data, the method executed on at least one processing unit, the method comprising: receiving the dataset, the retail promotion, and constraints, the constraints comprising a set of discrete constraints, wherein the set of discrete constraints comprises one or more of which products to put on promotion, promotion mechanics, product attributes and store attributes; receiving a seed solution to an optimization model based on an objective, the seed solution based on the discrete constraints in view of the retail promotion, wherein the seed solution comprises a previous year's promotion schedule or a pre-developed future promotion schedule; iteratively performing an optimization iteration until a criteria is reached, the optimization iteration comprising: generating a constraint space that comprises a range or set of options for at least one of the discrete constraints and that defines a closeness to values provided in the seed solution, wherein the range or set of options are determined by a constraint satisfaction problem, and determining an optimized value of at least one variable of the optimized model based on the objective that is within the constraint space, the optimization model taking as input the dataset and the constraint space; outputting an optimized retail promotion based on the optimized value once the criteria is reached; and, determining how many units for each of the products put on promotion should be purchased from vendors based on the optimized retail promotion. ### Claim 2 (depends on 1) The method of claim 1, wherein the constraint satisfaction problem is a Boolean satisfiability problem or a satisfiability modulo theories solver. ### Claim 3 (depends on 1) The method of claim 1, wherein the optimization model uses a sequential optimization technique or a reinforcement learning technique. ### Claim 4 (depends on 3) The method of claim 3, wherein the optimization model uses a Tree of Parzen Estimators technique. ### Claim 5 (depends on 3) The method of claim 3, wherein the optimization model uses an asynchronous advantage actor-critic (A3C) approach, or an A3C approach with advantage estimation. ### Claim 6 (depends on 1) The method of claim 1, wherein the optimization model comprises continuous features of the dataset. ### Claim 7 (depends on 1) The method of claim 1, wherein the criteria is either a predetermined number of iterations or an optimized objective, the optimized objective being either a minimization of a loss function below a first predetermined threshold, or a maximization of reward above a second predetermined threshold. ### Claim 8 A computing apparatus for optimizing a retail promotion having discrete constraints using a dataset, the dataset comprising a plurality of aspects associated with the retail promotion including historical sales data, the apparatus comprising: a processor; and a memory storing instructions that, when executed by the processor, configure the apparatus to: receive the dataset, the retail promotion, and constraints, the constraints comprising a set of discrete constraints, wherein the set of discrete constraints comprising one or more of which products to put on promotion, promotion mechanics, product attributes and store attributes; receive a seed solution to an optimization model based on an objective, the seed solution based on the discrete constraints in view of the retail promotion, wherein the seed solution comprises a previous year's promotion schedule or a pre-developed future promotion schedule; iteratively perform an optimization iteration until a criteria is reached, the optimization iteration comprising: generate a constraint space that comprises a range or set of options for at least one of the discrete constraints and that defines a closeness to values provided in the seed solution, wherein the range or set of options are determined by a constraint satisfaction problem, and determine an optimized value of at least one variable of the optimized model based on the objective that is within the constraint space, the optimization model taking as input the dataset and the constraint space; output an optimized retail promotion based on the optimized value once the criteria is reached; and determine how many units for each of the products put on promotion should be purchased from vendors based on the optimized retail promotion. ### Claim 9 (depends on 8) The computing apparatus of claim 8, wherein the constraint satisfaction problem is a Boolean satisfiability problem or a satisfiability modulo theories solver. ### Claim 10 (depends on 8) The computing apparatus of claim 8, wherein the optimization model uses a sequential optimization technique or a reinforcement learning technique. ### Claim 11 (depends on 10) The computing apparatus of claim 10, wherein the optimization model uses a Tree of Parzen Estimators technique. ### Claim 12 (depends on 10) The computing apparatus of claim 10, wherein the optimization model uses an asynchronous advantage actor-critic (A3C) approach, or an A3C approach with advantage estimation. ### Claim 13 (depends on 8) The computing apparatus of claim 8, wherein the optimization model comprises continuous features of the dataset. ### Claim 14 (depends on 8) The computing apparatus of claim 8, wherein the criteria is either a predetermined number of iterations or an optimized objective, the optimized objective being either a minimization of a loss function below a predetermined threshold, or a maximization of reward above a predetermined threshold. ### Claim 15 A non-transitory computer-readable storage medium for optimizing a retail promotion having discrete constraints using a dataset, the dataset comprising a plurality of aspects associated with the retail promotion including historical sales data, the computer-readable storage medium including instructions that when executed by a computer, cause the computer to: receive the dataset, the retail promotion, and constraints, the constraints comprising a set of discrete constraints, wherein the set of discrete constraints comprising one or more of which products to put on promotion, promotion mechanics, product attributes and store attributes; receive a seed solution to an optimization model based on an objective, the seed solution based on the discrete constraints in view of the retail promotion, wherein the seed solution comprises a previous year's promotion schedule or a pre-developed future promotion schedule; iteratively perform an optimization iteration until a criteria is reached, the optimization iteration comprising: generate a constraint space that comprises a range or set of options for at least one of the discrete constraints and that defines a closeness to values provided in the seed solution, wherein the range or set of options are determined by a constraint satisfaction problem, and determine an optimized value of at least one variable of the optimized model based on the objective that is within the constraint space, the optimization model taking as input the dataset and the constraint space; output an optimized retail promotion based on the optimized value once the criteria is reached; and, determining how many units for each of the products put on promotion should be purchased from vendors based on the optimized retail promotion. ### Claim 16 (depends on 15) The computer-readable storage medium of claim 15, wherein the constraint satisfaction problem is a Boolean satisfiability problem or a satisfiability modulo theories solver. ### Claim 17 (depends on 15) The computer-readable storage medium of claim 15, wherein the optimization model uses a sequential optimization technique or a reinforcement learning technique. ### Claim 18 (depends on 17) The computer-readable storage medium of claim 17, wherein the optimization model uses a Tree of Parzen Estimators technique. ### Claim 19 (depends on 17) The computer-readable storage medium of claim 17, wherein the optimization model uses an asynchronous advantage actor-critic (A3C) approach or an A3C approach with advantage estimation. ### Claim 20 (depends on 15) The computer-readable storage medium of claim 15, wherein the criteria is either a predetermined number of iterations or an optimized objective, the optimized objective being either a minimization of a loss function below a first predetermined threshold, or a maximization of reward above a second predetermined threshold.