1991-11-14
1993-11-30
Fleming, Michael R.
395 50, 395 51, G06F 1516, G06F 1531
Patent
active
052673464
ABSTRACT:
A computer based combination problem processor solves constrained combination satisfaction problems for determining discrete values of respective variables in which the constraint is externally specified by a set of inequalities and equalities, and solves combination optimization problems for determining the discrete values of respective variables to minimize or maximize the value of a given objective function. The computer includes an initial constraint violating inequality creator for creating constraint violating inequalities reciprocal to the set of inequalities; a variable value changer for changing a variable value for examination of meeting constraints; a variable selector for selecting a value of a variable whose value is unknown; a constraint violating condition creator for creating a new constraint violating condition obtained as a logical product of simplified inequalities by digitizing a variable appearing in the constraint violating conditions created from the constraint violating inequalities, when none of the values satisfy the constraints produced by the processes by the variable value changer or the variable value selector. A constraint violating condition storer stores constraint violating conditions created by the constraint violating condition creator. A variable value is changed or selected such that none of the constraint violating conditions stored in the constraint violating condition storer are satisfied. The above obtained variable value combination satisfying none of the constraint violating conditions is the solution to the constrained combination satisfaction problem or the constrained combination optimization problem.
REFERENCES:
patent: 3134017 (1964-05-01), Burhans et al.
patent: 4744027 (1988-05-01), Bayer et al.
patent: 5107452 (1992-04-01), Karmarker et al.
Maruyama, F. et al., "Solving Combinatorial Constraint Satisfaction and Optimization Problems Using Sufficient Conditions for Constraint Violation", Proceedings of International Symposium on Artificial Intelligence 1991, Mexico, pp. 269-275.
Gavish, B., "Augmented Lagrangean Based Algorithms for Centralized Network Design", IEEE Transactions on Communications, vol. COM33, No. 12, Dec. 1985.
Feldman et al., "Optimization Algorithms for Student Scheduling via Constraint Satisfiability", The Computer Journal, vol. 33, No. 4, Aug. 1990, pp. 356-364.
Costa, M. C., "Une Etude Pratique de Decoupes de Panneaux de Bois", R.A.I.R.O. Recherche Operationnelle, vol. 18, No. 3, Aug. 1984, pp. 211-219.
European Search Report, The Hague, Apr. 19, 1993.
Wah et al., "MANIP--A Multicomputer Architecture for Solving Combinatorial Extremum-Search Problems", IEEE Trans. on Computers, May 1984, 377-390.
de Kleer et al., "Diagnosing Multiple Faults", Artificial Intelligence, 1987, 97-130.
Baldwin, D., "Consul: A Parallel Constraint Language," IEEE Software, Jul. 1989, 62-69.
Minton et al., "Solving Large-Scale Constraint Satisfaction and Scheduling Problems Using a Heuristic Repass Method", AAAI-90, Jul. 1990; 17-24.
Cohen, J., "Constraint Logic Programming Languages", Comm. of the ACM, Jul. 1990, 52-68.
Maruyama Fumihiro
Minoda Yoriko
Sawada Shuho
Takizawa Yuka
Yoshida Hiroyuki
Downs Robert W.
Fleming Michael R.
Fujitsu Limited
LandOfFree
Combination problem solving apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Combination problem solving apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combination problem solving apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2104437