[FRIAM] Optimization problem

Fri Sep 20 19:22:29 EDT 2019

Marcus, for the couple of dozen pieces I need to cut, I suspect a
purely brute force solution would be adequate. I've only begun to
think about what an extremely naive algorithm would look like.

On Fri, Sep 20, 2019 at 6:07 PM Marcus Daniels <marcus at snoutfarm.com> wrote:
>
> In my experience, general purpose constraint and SMT solvers tend to have poor performance compared to linear relaxation techniques found in mathematical optimization products like CPLEX (which also have constraints but from a limited repertoire).   It depends on the nature of your constraints whether CPLEX will work, but I think it will for your problem.
>
> On 9/20/19, 3:55 PM, "Friam on behalf of Steven A Smith" <friam-bounces at redfish.com on behalf of 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