Re: [FRIAM] Optimization problem

[Steven A Smith]

Then there are those carefully selected branches from small trees or
large bushes that  can be trimmed to size... watch out for poison oak!

On 9/20/19 7:59 PM, Carl Tollander wrote:
> Welding galvanized steel without proper respirators (even outdoors)
> can kill you.  Research this carefully.
>
> How about some nice thick wall pvc?
>
> Carl
>
> On Fri, Sep 20, 2019, 17:48 Steven A Smith  > 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  > 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
> >>>  > 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 

Re: [FRIAM] Optimization problem

[Roger Critchlow]

You can splice together conduit pieces with set screw couplers.  They're
cheap, stable under compression loads, only require a screwdriver to
operate, and produce no toxic gases.

https://www.homedepot.com/p/Halex-3-4-in-Electrical-Metallic-Tube-EMT-Set-Screw-Coupling-25-Pack-62807B/202288563

-- rec --

On Fri, Sep 20, 2019 at 8:00 PM Carl Tollander  wrote:

> Welding galvanized steel without proper respirators (even outdoors) can
> kill you.  Research this carefully.
>
> How about some nice thick wall pvc?
>
> Carl
>
> On Fri, Sep 20, 2019, 17:48 Steven A Smith  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 
>> 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
>> >>>  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 

Re: [FRIAM] Optimization problem

[Carl Tollander]

Welding galvanized steel without proper respirators (even outdoors) can
kill you.  Research this carefully.

How about some nice thick wall pvc?

Carl

On Fri, Sep 20, 2019, 17:48 Steven A Smith  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  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
> >>>  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 <
> g...@naturesvisualarts.com> wrote:
> > I'd like advice on possible ways to solve the following problem
> > (plumbers must 

Re: [FRIAM] Optimization problem

[Steven A Smith]

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  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
>>>  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  
 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

Re: [FRIAM] Optimization problem

[Gary Schiltz]

Steve, that makes my day! Your solution is like Kirk's way of passing
the "Kobayashi Maru" training exercise.
https://en.wikipedia.org/wiki/Kobayashi_Maru

On Fri, Sep 20, 2019 at 6:23 PM Stephen Guerin
 wrote:
>
> Algorithm with guaranteed optimal:
>
> purchase ceil(TotalLengthNeeded / 6)  tubes
> Weld purchased tubes into one long tube *
> Cut what you need in any order
>
>* assumes welder $ < optimization design and compute time
> ___
> stephen.gue...@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  
> 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
>>  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  
>> > 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

Re: [FRIAM] Optimization problem

[Stephen Guerin]

Algorithm with guaranteed optimal:

   1. purchase ceil(TotalLengthNeeded / 6)  tubes
   2. Weld purchased tubes into one long tube
    *
   3. Cut what you need in any order

   * assumes welder $ < optimization design and compute time
___
stephen.gue...@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 
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
>  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 
> 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

Re: [FRIAM] Optimization problem

[Gary Schiltz]

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  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" 
>  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
> >  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 
>  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 

Re: [FRIAM] Optimization problem

[Gary Schiltz]

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  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
> >  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  
> >> 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/
> 

Re: [FRIAM] Optimization problem

[Marcus Daniels]

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" 
 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
>  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  
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 

Re: [FRIAM] Optimization problem

[Steven A Smith]

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
>  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  
>> 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

Re: [FRIAM] Optimization problem

[Gary Schiltz]

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
 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  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

Re: [FRIAM] Optimization problem

[Marcus Daniels]

And if you want to know how it works, I suggest SCIP.   https://scip.zib.de/

From: Friam  on behalf of Pieter Steenekamp 

Reply-To: The Friday Morning Applied Complexity Coffee Group 
Date: Friday, September 20, 2019 at 12:52 PM
To: The Friday Morning Applied Complexity Coffee Group 
Subject: Re: [FRIAM] Optimization problem

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 
mailto:g...@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

Re: [FRIAM] Optimization problem

[Pieter Steenekamp]

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 
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] Optimization problem

[Gary Schiltz]

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