System and method for optimizing the allocation of a resource
US6374227B1 · kind B1 · utility
Assignee
Inventor
Key dates
| Filing date | Apr 15, 1999 |
| Grant date | Apr 16, 2002 |
| Priority date | — |
| Expiry date | Apr 15, 2019 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06Q10/06315
- WIPO fieldIT methods for management
- WIPO sectorElectrical engineering
Abstract
A system (8) for optimizing the allocation of a resource includes an optimizer file (14) containing resource allocation data including a demand for allocation of the resource, a plurality of bids for the resource, and a plurality of reserve bids for the resource. A solver (18) receives an integer program and generates an LP relaxation solution to the integer program. An optimizer engine (16) coupled to the file (14) and to the solver (18) receives the data and the LP relaxation solution and generates an enhanced integer program that includes at least one cut according to the data. The cut includes a lifted cover inequality of a specified general form that the LP relaxation solution violates. A specified parameter associated with the lifted cover inequality is determined according to a first heuristic. The solver (18) generates a solution to the enhanced integer program that optimizes the allocation of the resource subject to the demand, bids, and reserve bids. In another embodiment, the engine (16) constructs a maximization problem of a specified general form according to the data, bids, and reserve bids and communicates the problem. The problem incorporates a special ordered set. …
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.