Re: using Mathematica for solving TSP-like problem with route priorities
- To: mathgroup at smc.vnet.net
- Subject: [mg125675] Re: using Mathematica for solving TSP-like problem with route priorities
- From: danl at wolfram.com
- Date: Wed, 28 Mar 2012 04:57:59 -0500 (EST)
- Delivered-to: l-mathgroup@mail-archive0.wolfram.com
- References: <jkf05i$8j2$1@smc.vnet.net>
On Thursday, March 22, 2012 5:50:26 AM UTC-5, Peter Sisak wrote: > 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 with in 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 I'm not fully clear on the constraints so what I suggest might or might not be viable. Here is the idea. Treat it as a TSP problem. Start with Euclidean distances between all points. We'll modify with penalty terms between various types of pairs. Vertices are, for our purpose, top left and right, and bottom left and right points on each 'X'. Between every pair of bottom left and bottom right or top left points, add some penalty. Likewise for the other three cases. We have one other issue to handle. We want to be sure, when at, say, a top left point, that we proceed immediately to its bottom right neighbor (assuming you diod not just come from there). I think this can be effected by subtracting from the Euclidean distance in a way that makes this a beneficial move. Actually this is not guaranteed to work, but it might work in practice. It will (almost) definitely work is the TSP code allows for negative distances. I'm not sure whether FindShortestTour will support that though. Not e that successfully enforcing this "move to diagonal neighbor" ploy will also have the desired effect of alternating between front stitches (between such neighbors) and back stitches (all other moves). By the way, problems like this do get studied. One context in which they arise is machine planning, e.g. for drilling, cutting, or spot welds. Daniel Lichtblau Wolfram Research