[Date Index] [Thread Index] [Author Index]

using Mathematica for solving TSP-like problem with route priorities

• To: mathgroup at smc.vnet.net
• Subject: [mg125617] using Mathematica for solving TSP-like problem with route priorities
• From: Peter Sisak <p-kun80 at hotmail.com>
• Date: Thu, 22 Mar 2012 05:49:03 -0500 (EST)
• Delivered-to: l-mathgroup@mail-archive0.wolfram.com

Dear Mathgroup,

Seeing Mathematica's capabilities in a number of 
combinatorial/optimization problems, I would like to know if someone 
could solve my problem as well (unfortunately, I'm completely 
unfamiliar with the magic needed.) The problem at hand is 
cross-stitching. As you might know, in cross-stitching one embroiders 
the pattern onto a suitable cloth (generally this is a so-called 
Aida cloth, although the quality of the base textile is irrelevant in the problem posed =E2=80=93 it can have some indirect 
scope in, say, calculating total yarn usage) with a continuous yarn. The 
pattern is generated by forming X-es, between the weave gaps of the base 
textile. A sample pattern is here, with a basic floral pattern.

..X...X..
..XX.XX..
XX.X.X.XX
.XX.X.XX.
...XXX...
.XX.X.XX.
XX.X.X.XX
..XX.XX..
..X...X..
In the attached pattern, dot means a space left empty, while an X means 
a place cross-stitched. A multicolour cross-stitch pattern is, for all 
purposes, just a sum of its elements, so it can be optimised discretely 
for each of the colours involved,  but seeing such functionality 
is not something I am interested in or expecting at all.

In cross-stitching, the following constraints are observed:

  a.. All X-es are executed in the same order. That is, depending on the 
decision of the program or embroiderer, first the \ (top-left to 
bottom-right or bottom-right to top-left) stitches are executed, then 
the / (bottom-left to top-right or top-right to bottom left), 
overlapping the previously laid \. This however does not mean that all 
such occurrences (pattern-wide) need to be separated, doing all 
\=E2=80=99s first then all /=E2=80=99s second; only that within the 
scope of an isolated cross-stitch of the pattern, there is ordered 
execution, but one easily might leave half of it done, then execute the 
other half somewhere in the middle, instead of separating the execution 
of the whole pattern into two strictly oriented phases. The execution 
order is relatively highly weighted, one can put a (say) +10.0 penalty 
on execution of a stitch in a wrong order (while it is possible to lead 
the needle and yarn under the previous stitch on the front side, it 
generally adds much to the difficulty of execution, and usually it comes 
out looking less neat.) The execution direction of a given sub-stitch of 
the X is essentially uninteresting (that is, no penalty for doing a \ 
stitch from top to bottom instead of bottom to top.) This is the route 
priority mentioned in the topic.
  b.. The back side should preferably consist of unit-distance 
orthogonal steps. Of course, in case of a pattern more spread and 
disjoint, it is impossible to execute them without larger jumps, but 
these should be minimised, and preferably these should be also 
orthogonal. A suggested simple penalty metric is (distance travelled on 
backside)^2 =E2=80=93 1. Incidentally, the preferred execution by human 
hobbyists appears to give more weight to one axis over another (say, 
preferring vertical back side stitches over horizontal), but this, if 
any, should be given only very small penalty, on the scale of 
0.025*(total count of back side orthogonal stitches in the wrong 
direction) or so.
  c.. The front side is strictly not permitted to have any parts of the 
cross double-stitched (the yarn going the same front side subpath twice, 
regardless of direction).
  d.. The back side is permitted to have the parts double-stitched (yarn 
going the same subpath twice), although this is discouraged. A suggested 
penalty metric would be (length of yarn overlapping) * 1.0.
  e.. The desired start/end points are not specified. It needs to be 
found by the solver.
>From what I know, there was no research whatsoever on execution of 
cross-stitch patterns, neither is there any software that I know of 
(commercial or otherwise) that can do any optimisation or planning on 
the execution of a cross-stitch pattern. Since the research and 
functionality on executing these cross-stitch patterns might prove 
useful (for hobbyists or for software companies), I would like to know 
some suggestions, code or feedback on it. For a reasonable visual 
representation, the end solution should be presented in a 
step-by-step manner, with each step, presenting the 
consecutive front-side stitches (subpaths), showing its direction (maybe 
with a small arrow?), and showing the incoming and outgoing backside 
stitches in a lighter shade.

Generally, showing all backside stitches would result in a rather 
crowded display which would be a terrible mental gymnastics to 
interpret, so it is to be avoided =E2=80=93 perhaps a separate summary 
output for showing general overlap in the end solution is something that 
could prove useful, showing possibly a 0.2 units wide yarn, and 
colouring the total overlaps with either a shaded weighted 
representation or the common green-yellow-red (=E2=80=9Ctraffic 
light=E2=80=9D) weighted representation. Possible extensions of the 
basic cross-stitched execution involve front-side half-stitches (only \ 
or / done instead of the full X, this could probably be relatively 
easily coded and executed, both in notation as well as programming), 
orthogonal stitches on the front side, or other stitches of varied 
length and angle =E2=80=93 but all these are beyond the scope of my 
request, and I believe putting it all in would be a much more 
challenging task (not to mention they'd need a more intricate 
notation, one that I wouldn't undertake inventing. But sure 
enough, if you feel the original constrained problem is too simple, why 
not generalise it...)

Thank you for your help in advance

Peter Sisak