| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 225.1 | Some Ideas | FASDER::MTURNER | Mark Turner * DTN 425-3730 * MEL4 | Tue Sep 04 1990 20:35 | 29 |
| This sounds like the knapsack problem, which has been attacked
with many different strategies. See Note 377.n in 2B::MATH.
The difference between o.r. and a.i. tools in problems like this
seems to be partly a matter of whether continuous or discrete
search is involved: o.r. people contributed methods like simplex
linear programming, which searches continuous spaces, and a.i.
researchers developed many of the discrete search methods (A*,
British Museum, branch-and-bound, etc.). In which of these
does your specific problem fall?
Another useful question is the standard one of whether you have
a human expert available. IBM supposedly tried to do automatic
layout of patterns on fabric, but its best strategy didn't beat
the human expert, a garment cutter from New York with many years
of experience.
This problem used to be given as an exercise in the Advanced OPS
course run by the US AI Training Group. You may want to check
with John Frost (SELECT::FROST), Tom Cooper (RUNT::COOPER), or
the training folks to see if the materials and code are still
available. As I recall, there were callable graphics so you
could see how the search was going.
Now maybe a real mathematician like Andrew or Hans can give a
better answer!
Mark
|
| 225.2 | n-Queens? | HERON::ROACH | TANSTAAFL ! | Wed Sep 05 1990 13:42 | 9 |
| If you are looking for general problems which are good example of the
difference between algorithmic and rule-based programming, I might
suggest looking at the n-Queens problem. My first big "Aha" in OPS5
came when I saw a 1 rule solution to the problem. It showed me how a
good representation of the problem was sufficient to achieve results.
It didn't teach me the n-Queens algorithm, but it did teach me that I
could get the job done!
Cheers
|
| 225.3 | The Japanese have done it! | HERON::ROACH | TANSTAAFL ! | Wed Sep 05 1990 13:46 | 11 |
| If you are looking for more information on garment pattern generation,
a Japan SWAS team built a system for a Japanese department store chain.
Once a person's general measurements were entered into a system, they
could select a garment from a catalogue and the system would generate a
custom pattern for the garment.
I think that at the end of the day the team discovered a traditional
approach to the solution, but it was the AI approach that lead them to
the traditional fix.
pat
|
| 225.4 | Reference in paper industry | EVOAI1::RIPOLL | Stephane RIPOLL, PARIS | Fri Sep 07 1990 10:34 | 3 |
| Also ask Henri Mercier. He was in touch with a little company, Aire
Informatique, who developped a similar application in OPS 5, for
paper industry.
|
| 225.5 |
| SELECT::FOLEY | | Fri Sep 28 1990 20:15 | 18 |
|
I've seen this problem in cardboard box manufacturing. There are some 'trim'
packages available commercially. The one we encountered used a fast integer
programming formulation; but had some limitations due to restrictive
assumptions (see "A 0-1 Model for Solving the Corrugator Trim Problem"
Haessler from Management Science Vol 29 No. 2 1983).
We have just begun a major piece of AI consulting in a 'diagramming' problem
(cutting sheets of color photo paper from rolls) - same thing everywhere:
paper, film, steel, plastics, textiles... So far we're planning a
classic search approach, but plan on getting some OR help in case some
hybridization with OR methods might help.
Please post whatever you find out. We should know more ourselves in a month
if that's not too late.
Tom Foley, AI Select
|