Data processing: financial – business practice – management – or co – Automated electrical financial or business practice or... – Health care management
Reexamination Certificate
1999-04-15
2001-11-20
Hafiz, Tariq R. (Department: 2163)
Data processing: financial, business practice, management, or co
Automated electrical financial or business practice or...
Health care management
C705S007380
Reexamination Certificate
active
06321207
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates in general to the field of optimization systems and methods, and more particularly to a system and method for optimizing the allocation of a resource.
BACKGROUND OF THE INVENTION
Many businesses and other types of organizations wish to optimize the manner in which they allocate various resources to reduce costs and improve efficiency. For example, a shipper of goods might wish to optimize the allocation of transportation capacity among multiple competing carriers in a way that minimizes shipping costs while satisfying the shipper's coverage, equipment, service, and other requirements. It is often desirable to optimize the allocation of such resources using computer-based systems that incorporate software specifically tailored to solve optimization problems using standard “brute force” approaches. For example, commercially available integer program solvers such as CPLEX and XPRESS may in some circumstances be used in an attempt to optimize a shipper's allocation of transportation capacity.
As the resource allocation needs of business and other organizations continue to increase in their complexity and importance, the speed, efficiency, and accuracy in which resources are allocated have become increasingly critical to the success of the organizations. However, previous systems and methods for optimizing the allocation of resources are inadequate for many optimization scenarios. For example, integer program solvers such as CPLEX and XPRESS may use a standard branch-and-bound approach in an attempt to solve optimization problems that are formulated as integer programs, but are often unable to solve even relatively small such problems in a brute force manner before overloading the memory of even the most powerful computers. Even where these solvers incorporate additional algorithms or other techniques in an attempt to reduce the size and complexity of the optimization problem, they are often too slow and require too much processing power to be of practical value. These and other deficiencies make previous systems and methods for optimizing allocation of resources inadequate for many purposes.
SUMMARY OF THE INVENTION
According to the present invention, the disadvantages and problems associated with previous optimization systems and methods have been substantially reduced or eliminated.
According to one embodiment of the present invention, a system for optimizing the allocation of a resource includes an optimizer file containing resource allocation data including a demand and multiple bids for the resource, each bid including at least a unit price for the resource. An optimizer engine coupled to the file receives the data and generates priorities for at least some of the bids according to their unit prices. The engine also generates an integer program according to the data and communicates the priorities in association with the integer program. A solver is coupled to the engine and receives the priorities and the integer program. The solver generates a solution to the integer program using the priorities, the solution optimizing the allocation of the resource subject to the demand and the bids. In another embodiment, the engine may generate an enhanced integer program that incorporates one or more cuts to further improve the optimization process.
The system and method of the present invention provide numerous important technical advantages. The present invention allows the allocation of a resource, such as one or more shipping lanes for example, to be optimized quickly, efficiently, and accurately relative to standard “brute force” approaches for solving integer programs. Furthermore, the present invention may optimize the allocation of a resource where previous systems and methods are unable to provide any solution due to insufficient computer memory or other limitations. The present invention generates priorities for at least some bids on a lane according to a comparison of their unit prices on the lane to allow a solver to generate an acceptable solution to the integer program quickly, efficiently, and accurately relative to previous optimization techniques. The priorities generated according to the present invention may be particularly effective for solving optimization problems when used in combination with cuts generated according to the present invention. Other important technical advantages are readily apparent to those skilled in the art.
REFERENCES:
patent: 6021402 (2000-02-01), Takriti
patent: 6064981 (2000-05-01), Barni et al.
patent: WO-200116665-A2 (2001-03-01), None
patent: WO-200048109-A1 (2000-08-01), None
Bradley et al., “Applied Mathematical Programming,” 1977, Addison-Wesley Publishing Company, pp. 387-398.*
Murphy, “transportation Management Systems Optimize Shipment Planning and Execution,” Keller International Publishing, Feb. 1998, 9 pages.*
Brandt, “Software Attempts to Simplify Lane Bidding,” Transport Topics, Feb. 16, 1998, 3 pages.*
PR Newswire, “i2 Technologies and InterTrans Logistics Agree to Merge,” Mar. 24, 1998, 2 pages.*
PR Newswire, “CAPS Logistics, Inc., A Baan COmpany, Launches BidPro™ for Carrier Bid Optimization,” Apr. 26, 1999, 2 pages.*
Kutanoglu et al., “On combinatorial auction and Lagrangian relaxation for distributed resource scheduling,” IIE Transactions, Sep. 1999, 17 pages.*
M2 Presswire, “INTERTRANS: InterTrans introduces leading edge transportation purchasing tool,” Feb. 10, 1998, 1 page.*
Veeramani, D., “Task and Resource Allocation Via Auctioning,” Proc. of the 1992 Winter Simulation Conference, XP-000957604, pp. 945-954, Dec. 13, 1992.
Walsh, W.E., et al., “Some Economics of Market-Based Distributed Scheduling,” Proc. of the 18th Int. Conf. on Distributed Computing Systems, XP-002151676, pp. 612-621, May 26-29, 1998.
Geppert, A., et al., “Market-Based Workflow Management,” Proc. of the Int. IFIP/GI Working Conference for Electronic Commerce, XP000956169, pp. 179-191, Jun. 3-5, 1998.
International Search Report, Nov. 15, 2000.
“Integer and Combinatorial Optimization,” George L. NemHauser and Laurence A. Wolsey, A Wiley Interscience Publication, pp. 265-270 and 459-465, Copyright 1988.
Baker & Botts L.L.P.
Hafiz Tariq R.
i2 Technologies US, Inc.
Norman Marc
LandOfFree
System and method for optimizing the allocation of a resource does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for optimizing the allocation of a resource, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for optimizing the allocation of a resource will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2588366