[FRIAM] Optimization problem

[Stephen Guerin]

Algorithm with guaranteed optimal:

   1. purchase ceil(TotalLengthNeeded / 6)  tubes
   2. Weld purchased tubes into one long tube
   <https://www.youtube.com/watch?v=ShByF_MBpNI> *
   3. Cut what you need in any order

   * assumes welder $ < optimization design and compute time
_______________________________________________________________________
Stephen.Guerin at Simtable.com <stephen.guerin at simtable.com>
CEO, Simtable  http://www.simtable.com
1600 Lena St #D1, Santa Fe, NM 87505
office: (505)995-0206 mobile: (505)577-5828
twitter: @simtable


On Fri, Sep 20, 2019 at 1:56 PM Gary Schiltz <gary at naturesvisualarts.com>
wrote:

> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://redfish.com/pipermail/friam_redfish.com/attachments/20190920/4254765a/attachment.html>