Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
2007-11-03
2011-12-20
Puente, Emerson (Department: 2196)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
C718S100000, C706S019000
Reexamination Certificate
active
08082549
ABSTRACT:
The present invention provides a system, method and apparatus for allocating resources with a linear programming model comprising an objective function and a set of constraints describing feasible allocations of the resources. The method ranks constraints based on a numerical measure derived from criteria selected from at least a first and second group and selects one or more of the top-ranked constraints. A new problem is determined from the model's objective function, the previously selected constraints, and the newly selected constraints, and a tentative resource allocation is determined based on the new problem. Whenever the tentative resource allocation violates a model constraint not in the current problem, one or more of the top-ranked such violated constraints are selected, and the new problem determination and tentative resource allocation steps are repeated. The resources are allocated according to the tentative resource allocation when it does not violate any model constraints.
REFERENCES:
patent: 4744026 (1988-05-01), Vanderbei
patent: 4744027 (1988-05-01), Bayer et al.
patent: 4744028 (1988-05-01), Karmarkar
patent: 4885686 (1989-12-01), Vanderbei
patent: 4914563 (1990-04-01), Karmarkar et al.
patent: 4924386 (1990-05-01), Freedman et al.
patent: 5136538 (1992-08-01), Karmarkar et al.
patent: 5471408 (1995-11-01), Takamoto et al.
patent: 6069894 (2000-05-01), Holender et al.
patent: 6516313 (2003-02-01), Perry
patent: 7689592 (2010-03-01), Denton et al.
patent: 2005/0171826 (2005-08-01), Denton et al.
patent: 2006/0171316 (2006-08-01), El-Sakkout et al.
patent: 2006/0242647 (2006-10-01), Kimbrel et al.
patent: 2008/0189418 (2008-08-01), Kimbrel et al.
Arsham, H., “A Computationally stable solution algorithm for linear programs,” Applied Mathematics and Computation (2007), 188:1549-1561.
Bixby, R. E., “Solving real-world linear programs: a decade and more of progress,” Operations Research (2002) 50:3-15.
Corley, H. W., et al., “The cosine simplex algorithm,” International Journal of Advanced Manufacturing Technology (2006) 27:1047-1050.
COSMOS problem instances, http://ieweb.uta.edu/cosmos/Instances.htm.
Curet, N. “A primal-dual simplex method for linear programs,” Operations Research Letters (1993) 13:233-237.
Dare. P., et al., “GPS network design: logistics solution using optimal and near-optimal methods,” Journal of Geodesy (2000) 74:467-478.
Forrest, J. J., et al., “Steepest-edge simplex algorithms for linear programming,” Mathematical Programming (1992) 57:341-374.
Gill, P. E., et al., “A numerically stable form of the simplex algorithm,” Linear Algebra and Its Applications (1973) 7:99-138.
Guerrero-Garcia, P., et al., “Phase I cycling under the most-obtuse-angle pivot rule,” European Journal of Operational Research (2005), 167:20-27.
Hu, J.-F., “A note on ‘an improved initial basis for the simplex algorithm’,” Computers and Operations Research (2007), 34:3397-3401.
Johnson, E. L., et al., “Progress in linear programming-based algorithms for integer programming: an exposition,” INFORMS Journal of Computing (2000) 12:2-23.
Karmarkar, M., “A new polynomial-time algorithm for linear programming,” Combinatorica (1984) 4:373-379.
Li, H. L., et al., “A linear programming approach for identifying a consensus sequence on DNA sequences,” Bioinformatics (2005) 21:1838-1845.
Li, W., “A Basis-Deficiency-Allowing Primal Phase-I Algorithm using the Most-Obtuse-Angle Column Rule,” Computers and Mathematics with Applications (2006), 51:903-914.
Myers, D. C., “A Dual Simplex Implementation of a Constraint Selection Algorithm for Linear Programming,” Journal of the Operational Research Society (1992), 43:177-180.
OR-library, J.E. Beasley, http://people.brunel.ac.uk/˜mastjjb/jeb/info.html.
Pan, P.-Q., “Practical finite pivoting rules for the simplex method,” OR Spektrum (1990) 12:219-225.
Pan, P.-Q., “A simplex-like method of with bisection for linear programming,” Optimization (1991) 22:717-743.
Pan, P.-Q., “A variant of the dual pivoting rule in linear programming,” Journal of Information and Optimization Sciences (1994) 15:405-413.
Pan, P.-Q., “New Non-Monotone Procedures for Achieving Dual Feasibility,” Journal of Nanjing University, Mathematical BiQuarterly (1995), 12:155-162.
Pan, P.-Q., “The most-obtuse-angle-row pivot rule for achieving dual feasibility: a computational study,” P.-Q. Pan, European Journal of Operational Research (1997) 101:167-176.
Pan, P.-Q., “A basis-deficiency-allowing variation of the simplex method of linear programming,” Computers and Mathematics with Applications 36 (1998) 36:33-53.
Rosenberger, J. M., et al., “Rerouting aircraft for airline recovery,” Transportation Science (2003) 37:408-421.
Santos-Palomo, A., “The sagitta method for solving linear programs,” European Journal of Operational Researxh (2004), 157:527-539.
Santos-Palomo, A., et al., “A non-simplex active-set method for linear programs in standard form,” Studies in Informatics and Control (2005) 14:79-84.
Stojkovic, N. V., et al., “Two direct methods in linear programming,” European Journal of Operational Research (2001) 131:417-439.
Stone, J. J., “The Cross-Section Method: An Algorithm for Linear Programing,” Rand Corporation (1958), P-1490.
Thompson, G. L., et al., “Techniques for Removing Nonbinding Constraints and Extraneous Variables from Linear Programming Problems,” Management Science (1966), 12:588-608.
Todd, M. J., “Theory and practice for interior-point methods,” ORSA Journal on Computing (1994) 6:28-31.
Todd, M. J., “The many facets of linear programming,” Mathematical Programming (2002) 91:417-436.
Vieira, H., et al., “An improved initial basis for the simplex algorithm,” Computers and Operations Research (2005) 32:1983-1993.
Zeleny, M. “An external reconstruction approach (ERA) to linear programming,” Computers and Operations Research (1986) 13:95-100.
Corley, Jr. Herbert W.
Rosenberger Jay M.
Board of Regents , The University of Texas System
Chalker Daniel J.
Chalker Flores LLP
Flores Edwin S.
Huaracha Willy W
LandOfFree
System, method and apparatus for allocating resources by... 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, method and apparatus for allocating resources by..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System, method and apparatus for allocating resources by... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4306856