Method of determining value change for placement variable

Details Method of determining value change for placement variable Method of determining value change for placement variable

2007-03-13

2007-03-13

Frejd, Russell (Department: 2128)

Data processing: structural design, modeling, simulation, and em

Modeling by mathematical expression

C709S201000, C709S235000

Reexamination Certificate

active

10627274

ABSTRACT:
In an embodiment of a method of determining a value changes for a placement variable as part of a local search solution to an integer programming problem that models placement of services of a distributed application onto nodes of a distributed resource infrastructure, an unsatisfied communication constraint is selected. The unsatisfied communication constraint includes a sum of terms where at least some of the terms comprise products of placement variables. Stores are created for allowable changes of value for the variables in the unsatisfied communication constraint. The unsatisfied communication constraint is parsed through by term. For each variable in a term, the stores are updated with a change in the term for each of the allowable changes of the value while maintaining other variables constant. A variable to receive the value change, and possibly a value for the variable, are chosen based upon the store which meets at least one improvement criterion.

REFERENCES:
patent: 5195172 (1993-03-01), Elad et al.
patent: 5428712 (1995-06-01), Elad et al.
patent: 6031984 (2000-02-01), Walser
patent: 6321207 (2001-11-01), Ye
patent: 6374227 (2002-04-01), Ye
patent: 6526420 (2003-02-01), Borowsky et al.
patent: 2003/0216951 (2003-11-01), Ginis et al.
patent: 2004/0210624 (2004-10-01), Andrzejak et al.
patent: 2004/0230922 (2004-11-01), Allen et al.
patent: 2005/0010922 (2005-01-01), Czajkowski et al.
Hochbaum, D.S. Solving Integer Programs Over Monotone Inequalities in Three Variables: A Framework for Half Integrality and Good Approximations, European Journal of Operational Research, vol. 140, No. 2, Jul. 2002, pp. 291-321.
Baldick, R. A Unified Approach to Polynomially solvable Cases of Integer “Non-Separable” Quadratic Optimization, Discrete Applied Mathematics, vol. 61, No. 3, Aug. 1995, pp. 195-212.
Andrzejak, A. Memory-Efficient and Fast Enumeration of Global States, IEEE 7thInternational Conference on Information Visualization, Jul. 2003, pp. 189-193.
Subhlok et al., J. Integer Programming for Array Subscript Analysis, IEEE Transactions on Parallel and Distributed Systems, vol. 6, No. 6, Jun. 1995, pp. 662-668.
Wilken et al., K. Optimal Instruction Scheduling Using Integer Programming, ACM SIGPLAN Notices, Proceedings of the ACM SIGPLAN 2000 Conference and Programming Language Design and Implementation, May 2000, pp. 121-133.
Sven Graupner, Vadim Kotov, Artur Andrzejak, Holger Trinks, Control Architecture for Service Grids in a Federation of Utility Data Centers, HP Labs Technical Report HPL-2002-235, Hewlett-Packard Company, Palo Alto, Aug. 21, 2002. < http://www.hpl.hp.com/techreports/2002/HPL-2002-235.pdf>.
Artur Andrzejak, Sven Graupner, Vadim Kotov, Holger Trinks, Algorithms for Self-Origanization and Adaptive Service Placement in Dynamic Distributed Systems, HP Labs Technical Report, HPL-2002-259, Hewlett-Packard Company, Palo Alto, Sep. 2002. < http://www.hpl.hp.com/techreports/2002/HPL-2002-259.pdf>.
Cipriano Santos, Xiaoyun Zhu, Harlan Crowder, A Mathematical Optimization Approach for Resource Allocation in Large Scale Data Centers, HP Labs Technical Report, HPL-2002-64(R.1), Hewlett-Packard Company, Palo Alto, 2002. < http://www.hpl.hp.com/techreports/2002/HPL-2002-64R1.pdf>.
Parameswaran Ramanathan, Suresh Chalasani, Resource Placement with Multiple Adjacency Constraints in K-ary n-Cubes, IEEE transactions on Parallel & Distributed Systems, May 1995, vol. 6, No. 5, pp. 511-519, IEEE Press, Los Alamitos, 1995.
Sven Graupner, Vadim Kotov, Holger Trinks, Resource-Sharing and Service Deployment in Virtual Data Centers, The 22nd International Conference on Distributed Computing Systems Workshops, Vienna Austria, Jul. 2-5, 2002, pp. 666-671, IEEE Computer Society, Los Alamitos, 2002.
Christodoulous A. Floudas, V. Visweswaran, Quadratic Optomization, Handbook of Global Optimization, pp. 217-269, Kluwer Academic Publishers, Boston, 1995.
Joachim P. Walser, Solving Linear Pseudo-Boolean Constraint Problems with Local Search, Proceedings of the Fourteenth National Conference on Artificial Intelligence and the Ninth Innovative Applications of Artificial Intelligence Conference, Jul. 27-31, 1997, Providence, Rhode Island, pp. 269-274, AAAI Press, Menlo Park, 1997.
Bart Selman, Hector Levesque, David Mitchell, A New Method for Solving Hard Satisfiability Problems, Proceedings of the Tenth National Conference on Artificial Intelligence Jul. 12-16, 1992, San Jose, California, pp. 440-446, AAAI Press, Menlo Park, 1992.
David Abramson, Henry Dang, Mohan Krishnamoorthy, A Comparison of Two Methods for Solving 0-1 Integer Programs Using a General Purpose Simulated Annealing Algorithim, Annals of Operations Research, v. 63, pp. 129-150, Baltzer Science, Amsterdam, Netherlands, 1996.
Joachim Paul Walser, Domain-Independent Local Search for Linear Integer Optomization, Dissertation, Programming Systems Lab, Universität de Saarlandes, Saarbrücken, Germany, Oct. 1998.
Bart Selman, Greedy Local Search in MIT Encyclopedia of the Cognitive Sciences, MIT Press, Cambridge, 1999.
Bart Selman, Henry A. Kautz, Bram Cohen, Local Search Strategies for Satifiabily Testing Presented at the Second DIMACS Challenge on Cliques, Coloring, and Satisfiability, Oct. 11-13, 1993, Piscataway, New Jersey.
Bart Selman, Henry A. Kautz, Bram Cohen, Noise Strategies for Improving Local Search, Proceedings of the Twelfth National Conference on Artificial Intelligence, Aug. 1-4, 1994, Seattle, Washington, pp. 337-343, AAAI Press, Menlo Park, 1994.

Affiliated with

Also associated with

Rating

Method of determining value change for placement variable does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of determining value change for placement variable, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of determining value change for placement variable will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3732743