[FRIAM] Optimization problem

Sun Sep 22 06:26:21 EDT 2019

Gary,

If you want a quick answer to get your task done, I found a few online
tools to calculate for you. eg:
  https://www.kurraglenindustries.com.au/linear-cutting-list-calculator.htm
  http://cutlist.dotordotdot.com/current
  https://www.cutlistoptimizer.com/

Then to study the problem later, it looks like your problem is well-known
as the one-dimensional cutting stock problem
<https://en.wikipedia.org/wiki/Cutting_stock_problem> and is NP-Hard. It's
also equivalent to the bin packing problem. There's quite a few papers
applying Ant colony optimization (ACO) as a successfu heuristic to both
problems.

And by golly, there's an extension to the cutting stock problem that
involves welding :-)
  https://www.hindawi.com/journals/aor/2019/6507054/

On Sat, Sep 21, 2019 at 8:59 PM Stephen Guerin <redfishgroupllc at gmail.com>
wrote:

> Gary,
>
> Thanks for posing this problem to the group - it's been fun to have in the
> back of the mind for a day. I agree with Pieter that this is a kind of
> knapsack problem for which Dynamic Programming is a popular approach where
> you would extend to multiple knapsacks.
>
> I might approach it with a variant of the multiple traveling salesman
> (mTSP) problem where your purchased tubes are salesman and the tubes you
> want cut are cities which all need to be visited once with the constraint
> to minimize the number of salesmen and the upper bound on how far each
> salesman can travel (6 meters/miles). The difference of the tube cutting
> model with mTSP is that the tubes aren't in a spatial layout so you would
> use the length of the tube to be cut as the distance to visit that city. I
> like that the edges between tubes to be cut that tend to show up in
> successful solutions will get reinforced over time. Do you remember
> Alberto Gallo's model from Bios where he used ant colony optimization to
> solve the problem?
>
> A GA could also be used by indexing the tubes to be cut as genes in the
> genome.
>
> Owen has an elegant optimization on the TSP in Agentscript just using
> random swaps based on a fitness function - a kind of simulated annealing
> heuristic. http://agentscript.org/models/travsalesman.html
>
> Another approach would be a market model where  6m tubes bid on tubes
> segments and their value determined by how much a given tube would complete
> their unclaimed space. This was similar to Dick Gordon's paint booth
> problem at Bios bidding on cars to paint based on the cost of changing
> colors.
>
> Stephen
>
> -Stephen
>
> On Fri, Sep 20, 2019, 5:48 PM Steven A Smith <sasmyth at swcp.com> wrote:
>
>> Gary -
>>
>> I understand better now...
>>
>> I definitely agree that the *most* naive eyeballing methods can be
>> excruciatingly wasteful.
>>
>> I presume that your conduit length requirements are not precise... that
>> you might be designing them to allow for leaving the window partially
>> open but otherwise not subject to intrusion or compromise?  That seems
>> to complicate the problem but may pose opportunities.  In particular,
>> *I* might be looking for solutions which leave me with a *minimum* of
>> leftover conduit by making them longer than their shortest possibles in
>> some cases.  Or looking at it the other way, even if you don't need to
>> leave the windows open much when "locked" a more complete use of the
>> material might be obtained by relaxing the length a little without
>> compromising security (if a given window can only be opened a few inches
>> for example).
>>
>> I will be interested in hearing the results of whatever optimization (or
>> satisficing) method you use yields.
>>
>> - Steve
>>
>> PS. regarding guerin's solution, an alternate would be to measure as
>> suggested, then cut naively until the remaining spaces are larger than
>> the remaining pieces.  Only *then* does one break out the welder and
>> begin to piece together as-needed.   I don't think these are equivalent.
>>   It also occurs to me that *2* pieces of conduit (end to end, unwelded)
>> in a window channel might be *nearly* as effective as a single piece,
>> albeit less elegant?
>>
>> > Hey Steve. The actual project is nothing elaborate. My house has a
>> > couple or three dozsen horizontally sliding windows with pretty weak
>> > locks. Since I've had a couple of break-ins in the past, I decided
>> > that the easiest way to shore up security for that aspect of the house
>> > is to just cut short pieces of 3/4 inch conduit to lay horizontally in
>> > the spaces where the windows slide. When I want to open a window, I
>> > will just stand its conduit piece up, and when I want to "lock" it
>> > again, just lay it back horizontally. I asked on FRIAM because instead
>> > of just eyeballing it and having lots of extra (even potentially
>> > useful in the future) pieces left over, I'd rather use my (and
>> > FRIAM's) brain to look at possible ways of optimizing this. Kind of
>> > fun actually putting my mind to something for a change (retirement can
>> > be boring if you're not careful).
>> >
>> > On Fri, Sep 20, 2019 at 5:55 PM Steven A Smith <sasmyth at swcp.com>
>> wrote:
>> >> Gary -
>> >>
>> >> I *patently don't* recommend my method, though it does have some
>> >> charms.   I recently was faced with a similar problem to yours where I
>> >> needed to cut and install trim around the perimeter of the room (with
>> >> door openings) I just layed hardwood floor in.
>> >>
>> >> Rather than go into it in detail (I already did that and realized it
>> was
>> >> a TL;DR as usual, so cut it) I will just say that I approach these
>> >> problems as *satisficing* and *constraint* problems rather than
>> >> *optimization*.    Once I had a candidate layout, I simply looked at
>> the
>> >> results and determined that the *waste* was acceptable.   Depending on
>> >> the circumstances I sometimes prefer to have for example, 2 3'
>> leftovers
>> >> rather than 1 5' leftover, other times, vice-versa, depending on how I
>> >> might use said leftovers in some future application (or hedging against
>> >> a mistake in my measuring/cutting).
>> >>
>> >> Care to share what your actual conduit/pipe project is?
>> >>
>> >> - Steve
>> >>
>> >>
>> >>> Thanks for the links, Peter. I will probably use that software or
>> >>> similar, to get a quick solution, then look at the MOOCs.
>> >>>
>> >>> On Fri, Sep 20, 2019 at 2:52 PM Pieter Steenekamp
>> >>> <pieters at randcontrols.co.za> wrote:
>> >>>> Two possible approaches are:
>> >>>> a) Solve the problem yourself. Use one or a combination of standard
>> algorithms ( eg you mentioned linear programming and greedy algorithms,
>> there are many more of course) and/or your own custom algorithm. If you
>> wish to go this route and want to learn about the subject, I recommend the
>> series of MOOCS by Stanford's Tim Roughgarden
>> https://www.coursera.org/specializations/algorithms
>> >>>> Or, I think yours is probably a knapsack -type problem and the MOOC
>> https://www.coursera.org/learn/discrete-optimization covers that
>> relatively well.
>> >>>> b) But if you just want to get the solution you can use optimization
>> software like
>> https://www.ibm.com/za-en/products/ilog-cplex-optimization-studio (they
>> have a free edition that will be good enough for your application) will
>> solve it for you without you necessarily knowing how the software does it.
>> >>>>
>> >>>> On Fri, 20 Sep 2019 at 21:00, Gary Schiltz <
>> gary at naturesvisualarts.com> wrote:
>> >>>>> I'd like advice on possible ways to solve the following problem
>> >>>>> (plumbers must surely face this all the time). I need to cut a set
>> of
>> >>>>> metal tubes of varying lengths from standard length (6 meter)
>> >>>>> galvanized conduit stock. The goal is to find the number of tubes I
>> >>>>> need to buy, and the order of cuts to produce the minimum amount of
>> >>>>> leftover, unused tube.  I'm interested in what types of solutions
>> >>>>> people use for similar 1-dimensional problems, e.g. linear
>> >>>>> programming, greedy algorithms, etc. (I've been Googling). I'm only
>> >>>>> looking to cut around 15-25 pieces, so my gut feeling is that an
>> >>>>> exhaustive search of all possible solutions, though probably
>> NP-hard,
>> >>>>> would be feasible to perform. Working programs, as well as libraries
>> >>>>> in any language would be a bonus.
>> >>>>>
>> >>>>> ============================================================
>> >>>>> FRIAM Applied Complexity Group listserv
>> >>>>> Meets Fridays 9a-11:30 at cafe at St. John's College
>> >>>>> to unsubscribe
>> http://redfish.com/mailman/listinfo/friam_redfish.com
>> >>>>> archives back to 2003: http://friam.471366.n2.nabble.com/
>> >>>>> FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove
>> >>>> ============================================================
>> >>>> FRIAM Applied Complexity Group listserv
>> >>>> Meets Fridays 9a-11:30 at cafe at St. John's College
>> >>>> to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com
>> >>>> archives back to 2003: http://friam.471366.n2.nabble.com/
>> >>>> FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove
>> >>> ============================================================
>> >>> FRIAM Applied Complexity Group listserv
>> >>> Meets Fridays 9a-11:30 at cafe at St. John's College
>> >>> to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com
>> >>> archives back to 2003: http://friam.471366.n2.nabble.com/
>> >>> FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove
>> >>
>> >> ============================================================
>> >> FRIAM Applied Complexity Group listserv
>> >> Meets Fridays 9a-11:30 at cafe at St. John's College
>> >> to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com
>> >> archives back to 2003: http://friam.471366.n2.nabble.com/
>> >> FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove
>> > ============================================================
>> > FRIAM Applied Complexity Group listserv
>> > Meets Fridays 9a-11:30 at cafe at St. John's College
>> > to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com
>> > archives back to 2003: http://friam.471366.n2.nabble.com/
>> > FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove
>>
>>
>> ============================================================
>> FRIAM Applied Complexity Group listserv
>> Meets Fridays 9a-11:30 at cafe at St. John's College
>> to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com
>> archives back to 2003: http://friam.471366.n2.nabble.com/
>> FRIAM-COMIC <http://friam.471366.n2.nabble.com/FRIAM-COMIC>
>> http://friam-comic.blogspot.com/ by Dr. Strangelove
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://redfish.com/pipermail/friam_redfish.com/attachments/20190922/b7f3cdc0/attachment.html>