Special-ordered-set-based cost minimization
AssigneeMicrosoft Corporation
InventorsMIN WEI, ALEXANDER S. STOJANOVIC, JOHN OBERON
Life of this patent
Estimating the term…
Abstract
An embodiment of the invention is directed toward determining a solution to an objective function that is to be maximized or minimized. An initial feasible basis is determined. An entering variable is determined to enter the initial feasible basis. It is determined if there is an exiting variable. While there is an exiting variable, the exiting variable is removed from the feasible basis, the entering variable is added to the feasible basis, and a new entering variable is determined.
Claims11
Computer-readable media having computer-executable instructions embodied thereon that, when executed, cause a computing device to perform a method of minimizing the cost of a vendor supply chain, the method comprising:
- identifying an objective function to be minimized related to the cost of the vendor supply chain, subject to one or more constraints, wherein the one or more constraints and the objective function may be nonlinear;
- determining an initial feasible basis by the computing device;
- determining an entering variable to enter the initial feasible basis, wherein the entering variable
- is from a particular special ordered set and there are no other variables in the initial feasible basis from the particular special ordered set, or
- is adjacent to an exactly one variable in the initial feasible basis that is from the particular special ordered set;
- determining if there is an exiting variable in the initial feasible basis;
- and while there is an exiting variable in the initial feasible basis,
- removing the exiting variable from the initial feasible basis,
- adding the entering variable to the initial feasible basis,
- determining a new entering variable to be the entering variable,
- wherein the new entering variable is from a particular special ordered set and there are no other variables in the initial feasible basis from the particular special ordered set, or is adjacent to an exactly one variable in the initial feasible basis that is from the particular special ordered set, and
- determining if there is a new exiting variable in the initial feasible basis to be the exiting variable.
Computer-readable media having computer-executable instructions embodied thereon that, when executed, cause a computing device to perform a method of minimizing the cost of advertisement placement, the method comprising:
- identifying an objective function to be minimized related to the cost of advertising placement, subject to one or more constraints, wherein the one or more constraints and the objective function may be nonlinear;
- determining an initial feasible basis by the computing device;
- determining an entering variable to enter the initial feasible basis, wherein the entering variable
- is from a particular special ordered set and there are no other variables in the initial feasible basis from the particular special ordered set, or
- is adjacent to an exactly one variable in the initial feasible basis that is from the particular special ordered set;
- determining if there is an exiting variable in the initial feasible basis;
- and
- while there is an exiting variable in the initial feasible basis,
- removing the exiting variable from the initial feasible basis, adding the entering variable to the initial feasible basis, determining a new entering variable to be the entering variable, wherein the new entering variable is from a particular special ordered set and there are no other variables in the initial feasible basis from the particular special ordered set, or is adjacent to an exactly one variable in the initial feasible basis that is from the particular special ordered set, and
- determining if there is a new exiting variable in the initial feasible basis to be the exiting variable.
Computer-readable media having computer-executable instructions embodied thereon that, when executed, cause a computing device to perform a method of determining a solution to an objective function to be maximized or minimized, subject to one or more constraints, wherein the one or more constraints and the objective function may be nonlinear, the method comprising:
- determining an initial feasible basis by the computing device;
- determining an entering variable to enter the initial feasible basis, wherein the entering variable
- is from a particular special ordered set and there are no other variables in the initial feasible basis from the particular special ordered set, or
- is adjacent to an exactly one variable in the initial feasible basis that is from the particular special ordered set;
- determining if there is an exiting variable in the initial feasible basis;
- and
- while there is an exiting variable in the initial feasible basis,
- removing the exiting variable from the initial feasible basis,
- adding the entering variable to the initial feasible basis,
- determining a new entering variable to be the entering variable,
- wherein the new entering variable is from a particular special ordered set and there are no other variables in the initial feasible basis from the particular special ordered set, or is adjacent to an exactly one variable in the initial feasible basis that is from the particular special ordered set, and
- determining if there is a new exiting variable in the initial feasible basis to be the exiting variable.
Dependencies are inferred from the claim text.