Boots – shoes – and leggings
Patent
1994-12-23
1998-02-03
Gordon, Paul P.
Boots, shoes, and leggings
36446809, 36446806, 364153, G06F 1900
Patent
active
057151652
ABSTRACT:
A method and system for scheduling using a facet ascending algorithm or a reduced complexity bundle method for solving an integer programming problem is presented. A Lagrangian dual function of an integer scheduling problem is maximized (for a primal minimization problem) to obtain a good near-feasible solution, and to provide a lower bound to the optimal value of the original problem. The dual function is a polyhedral concave function made up of many facets. The facet ascending algorithm of the present invention exploits the polyhedral concave nature of the dual function by ascending facets along intersections of facets. At each iteration, the algorithm finds the facets that intersect at the current dual point, calculates a direction of ascent along these facets, and then performs a specialized line search which optimizes a scaler polyhedral concave function in a finite number of steps. An improved version of the facet ascending algorithm, the reduced complexity bundle method, maximizes a nonsmooth concave function of variables. This is accomplished by finding a hyperplane separating the origin and the affine manifold of a polyhedron. The hyperplane also separates the origin and the polyhedron since the polyhedron is a subset of its affine manifold. Then an element of the bundle is projected onto the subspace normal to the affine manifold to produce a trial direction normal. If the projection is zero (i.e., indicating the affine manifold contains the origin), a re-projection onto the subspace normal to the affine manifold of an appropriate face of the polyhedron gives a trial direction. This reduced complexity bundle method always finds an .epsilon.-ascent trial direction or detects an .epsilon.-optimal point, thus maintaining global convergence. The method can be used to maximize the dual function of a mixed-integer scheduling problem.
REFERENCES:
patent: 5077661 (1991-12-01), Jain et al.
patent: 5093794 (1992-03-01), Howie et al.
patent: 5155679 (1992-10-01), Jain et al.
patent: 5195172 (1993-03-01), Elad et al.
patent: 5216593 (1993-06-01), Dietrich et al.
patent: 5233533 (1993-08-01), Edstrom et al.
R.N. Tomastik et al, "The Facet Ascending Algorithm for Integer Programming Problems", IEEE Proceedings, Dec. 1993.
P.B. Luh et al, "Schedule Generation and Reconfiguration for Parallel Machine", IEEE Transactions on Robotics and Automation, vol. 6, No. 6, Dec. 1990, pp. 687-696.
M.L. Fisher, "The Lagrangian Relaxation method For Solving Integer Programming Problems", The Institute of Management Sciences, Jan. 1981, pp. 1-18, vol. 27, No. 1, Jan. 1981.
A. R. Conn et al, "A Projection Method For The Uncapacitated Facility Location Problem", Mathmatical Programming 46 (1990) pp. 273-298.
R. N. Tomastick et al, "A New Lagrangian Relaxation Algorithm For Scheduling Of Manufacturing Systems", NSF Proceedings, 1994.
Luh Peter B.
Tomastik Robert N.
Gordon Paul P.
The University Of Connecticut
LandOfFree
Method and system for scheduling using a facet ascending algorit 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 and system for scheduling using a facet ascending algorit, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for scheduling using a facet ascending algorit will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-668387