Practical Cutting Stock Problem

Warning. This post is for an audience of close to zero. My technical friends will find this pretty basic, and my non-technical friends will find this too technical. Welcome to the middle space that I occupy between these two worlds.

I wanted to build this series of retaining walls to replace the overgrown ivy and eroding slope next to my stairs in my front yard.

Retaining Walls

One of the challenges of my current job is to keep my skills sharp as a program manager. I decided to find an automated solution, even when the practical solution was pretty obvious. My problem was basic, I had to make the following cuts:

  • 43 1/8
  • 4′ 7/8
  • 44.5″ x 3

As these were landscape timbers, I knew that I could get them at Home Depot in 8, 10 or 12 foot lengths at $20.57, $29.97, or $37.27. The longer lengths cost more at 2.57, 3, and 3.11 a foot. To minimize my cost, I wanted to buy the least number of pieces and at the shortest lengths possible.

I solved this in 2 minutes in excel, by just guessing and found that I could do one 8 and one 12 or three eights. Three eights would be $62 and and 8,12 would be $58. I’m going to pay the $4 and get pieces I can more easily move, and get 4 more feet to play with.

However, isn’t this a nice knapsack problem for the excel solver? I thought I would give it a try. Google showed me this quick refresher and Wikipedia provides a nice start and the integer program can be formulated as:

$$\min\sum_{i=1}^n c_i x_i$$ $$\text{s.t.}\sum_{i=1}^n a_{ij} x_i \ge q_j, \quad \quad \forall j=1,\dots,m$$ $$x_i \ge 0, \text{integer} $$

where is the number of times order appears in pattern and is the cost (often the waste) of pattern .

However, I wanted to be quick. I didn’t want to have to find all patterns ahead of time. After playing around for a couple minutes, I got this working in excel using a genetic algorithm by forcing each cut to only happen once and minimizing the amount spent.

Excel Solver Example

With these constraints:

Solver Parameters Solver Parameters

While I had a quick solution under my belt, I waited until a long plane flight to cook up something better. First, I skimmed through these papers:

For me, it turns out the key to solving this is to come up with a list of potential patterns and to solve for the pattern combinations in order to get the quantities right. First, I used Matlab to come up with feasible combinations by using the and the very handy allcomb function to generate all possible combinations and removing those that were too long.

{aaa01f1184b23bc5204459599a780c2efd1a71f819cd2b338cab4b7a2f8e97d4} here 3 cuts are hard-coded
M = allcomb([0:max_num], [0:max_num], [0:max_num]);

{aaa01f1184b23bc5204459599a780c2efd1a71f819cd2b338cab4b7a2f8e97d4} now reduce to the feasible solutions
F = M(M*cuts' < max_length, :);

{aaa01f1184b23bc5204459599a780c2efd1a71f819cd2b338cab4b7a2f8e97d4} remove the trivial
F = F(2:end,:);

First, I implemented this in Excel using their simplex solver.

Improved Solver

With the following solver constraints:

I also implemented an end-to-end solution in Matlab that should be useful for my next project. This way I understand the math behind it and can use my optimizer for any number of projects.

This produces an output like:

board: 1 | quantity: 1 | 2 cuts of 44.5  waste: 7
board: 2 | quantity: 1 | 1 cuts of 44  waste: 52
board: 3 | quantity: 1 | 1 cuts of 44 1 cuts of 44.5  waste: 7.5
board: 4 | quantity: 2 | 1 cuts of 44 1 cuts of 49  waste: 3
----------------------
Total waste: 72.5 inches

And I added some graphics to be able to guide my cuts.

matlab_results

Please share any comments/insights.

Consistency, Focus and Grace

“My commitment must be to truth, not to consistency.” — Ghandi

Then Jesus said to his host, “When you give a luncheon or dinner, do not invite your friends, your brothers or sisters, your relatives, or your rich neighbors; if you do, they may invite you back and so you will be repaid. But when you give a banquet, invite the poor, the crippled, the lame, the blind, and you will be blessed. Although they cannot repay you, you will be repaid at the resurrection of the righteous.” Luke 14:12-14

It was the smell of smoke which alerted me to his presence. I had a long layover in Salt Lake City and I was taking the Trax downtown to sketch, tour the sights, and find a good coffee shop. The sun shone brightly into the impeccably clean and nearly empty car as I did my quick survey of my new fellow traveler. He was an over-weight latin-american with an unshaven and stressed out face. His shoes were worn out and he was talking on a cheap pre-paid cell phone with a friend to figure out how he was going to get $40 to pay for medicine his wife needed. Not excessively loudly, but definitely not softly he explained that his wife recently had a medically-induced accident that resulted in injuries to their infant. He talked about trusting God to provide the money and highlighted that their baby was fine, but that his wife was not.

I was feeling excessively penitent due to a Bishop Bienvenu encounter with a Las Vegas police officer the night before. He gave me a warning despite clocking me at nearly 40 mph over the speed limit in Red Rock Canyon after a run. I had also been upgraded to first class for both flights that day, and this new passenger made me very aware that we were two members of very different worlds whose lives were coming into contact. Additionally, I had just taken out $40 from an ATM in the airport and the money he was stressing over was sitting two feet from him in my pocket.

I reached into my pocket and fingered the bills, thinking of the words to use as I handed them to him. But then my left brain kicked in.

“Doesn’t this story sound too contrived.” “Isn’t this exactly what he would say to get our money.” “By his accent, English is not his native language, but he is speaking english.” “This train is empty, but he sat right next to me with this story.” “I should give this money to a real charity who can better discern the need.” “I don’t want to insult him.”

These thoughts rushed through my head as I felt what I would describe the Holy Spirit tug at my heart to give him the dollars. I thought of the joy that this could bring his day. I prayed to God to make things more clear to me, and was convicted that He had already done that. But then I thought about being used, about the risk of being played. Hadn’t I been working 12 hour days for the last month to take care of my family? I could use this money to buy a great gift for my kids. Or get closer to my church tithe . . .

As I carried on this internal dialogue, I arrived at my stop and quickly fled to the certainty of the doors which opened next to me. In near tears, I thought of how much I love being a recipient of grace, but how hard it is to activate my own ability to practice grace. I tried to catch a sight of him as the train drove on, but was denied the opportunity. I didn’t deserve it.

I walked across the street back into my familiar channel, bathed in sunshine and surrounded by mountains as I walked past the amazingly well groomed grounds of the Mormon temple and Salt Lake’s best shopping and restaurants. As I walked past Nordstrom, I watched an amazing fountain show as well-off kids danced in front of the dancing water. I thought of the fountain shows I had seen the night before at the Aria and the Bellagio. I thought of the discussions I had with my fellow engineers about how to create laminar flow, keep the pumps running and what computer models would be best to simulate the fountains; all stuffed from the Holstein’s burgers and shakes that were just settling in our bellies. I was hit with the pang of remorse a loving father feels when he is 1000s of miles from his wife and kids — who is constantly away because I want to succeed for them, for you, but mostly for me.

As I sat by an artificial creek that ran through the outdoor shopping mall to sketch a bronze pair of statues, I couldn’t shake the interconnectedness of three discussions I had lately that explored the interplay of motivation, focus, and grace.

The first was a Facebook “discussion” (mostly me ranting) regarding the endorsement a friend of mine gave to a disillusioned evangelical who was decrying the evil of those who threatened to withdraw their support from World Vision’s reversal on its employment/ethics policy regarding those in active homosexual relationships. I found the article to be an unfair screed which characterized evangelicals such as myself with being out of touch with science, culture and “on the wrong side of history”. My friend was particularly sympathetic to the article’s claim that conservative Christians were putting politics over children’s lives and made the claim that a dollar withheld of WorldVision was directly (and willfully) depriving a child of food. To me, who has never provided support to World Vision, this complaint definitely hit close to home.

The bigger issue that I couldn’t get out of my mind was the idea that there is constant death around us. Constant suffering, like that of my fellow traveler mentioned earlier. Though I put forward a passionate defense of my fellow evangelicals, I was convicted that are actions are never really defensible. I’m well aware that if we really felt, and knew, the true nature of need in the world, I would cry out like Oskar Schindler:

If I’d made more money… I threw away so much money. You have no idea. If I’d just…This car. Goeth would have bought this car. Why did I keep the car? Ten people right there. Ten people. Ten more people. This pin. Two people. This is gold. Two more people. He would have given me two for it, at least one. One more person.

Every day I make so many selfish decisions. I put my heart in my job, in my abilities and my pleasures. How defendable are any of us before a standard such as this? I remember the time in college when I was seized by the gravity of my selfishness and offered all my possessions to the fellow college students in my house. It was passionate, selfless and valiant — until someone took my chair. Optimizing one’s life is hard and we show our true colors when our values conflict.

This point was driven home as I read about Jim Kim’s efforts at the World Bank to punish african nations (and therefore their populace) who are not supportive of active homosexual lifestyles. Just like my friend, I found myself indignant that someone would withdraw aid where needed, just like cities in the US that withdrew support for Catholic charities to the homeless and children in need of adoption because of dissonance between their doctrinal stance on abortion and progressive politics.

The Economist states the importance of focus well:

The uncomfortable truth is that an economic institution like the bank has to pick its battles. There is a limit to how many conditions outsiders can attach to their aid. Its aim is to encourage economic development. Most of the evidence is that the bank is most effective when client countries see it as an economic partner, rather than a boss imposing a Western agenda.

It seems we are all trying to optimize the world in our own image per our own objectives. Which calls into question my most prized possessions: my motivation and drive. I see my life priorities summarized as (1) Worship, (2) Love and (3) Achieve. As a Christian, I believe I was created to bring God glory, to worship Him. To worship Him is to serve Him, and to serve him is to love others with the love we desire for ourselves: both our family and others. To love others is to love my country and my world, who I want to make a more secure and better place. Hence my desire to achieve — to make a difference.

This third priority was called into question by another discussion when a coworker told me that he worked to support his family. Period. He didn’t work for national security. He didn’t work to find fulfillment. He didn’t work to prove to the world that he was somebody and that his life has value. While I know this friend to do excellent work, he made it clear where his vocational heart was.

To me, this is an irreconcilable position. I take great pride in my long hours. I want to teach my children the value of hard work. I want to teach them to make a difference and love the feeling of getting something done. I want to be a net giver professionally — to be a contributor, not organizational dead weight. Yes, I want to support my family, but in line with Jim Collins’ Good to Great, that is only of the three necessary conditions for meaningful work. I also love what I do and believe that I have the desire, motivation and capability to be the best in the world in my field. Isn’t that how everyone should approach their job? Aren’t those good things to want and doesn’t wanting them make me a better citizen, father and man?

What concerns me is the false dichotomy that I know we can all fall prey to. These days, I’m well aware that the good is the enemy of the better and there are so many seemingly good choices which are inconsistent with my goals. I’m convinced that maturing professionally is making the hard choices and deciding not to do many good things. It is all about focus and focus is all about priorities.

I hope to figure all this out, but I’m not there yet. What I do know is that I’m commanded to love, be humble and have an open heart that is ready to serve — despite my own desire to always get in the way. As for me, I’m thankful that the Christian conception is of a prodigal, not efficient Father. After all, isn’t His message of grace the most inefficient message in history? In any case, it certainly didn’t lack focus.

World Vision and the Culture Wars

I, for one, am tired of arguing. I’m tired of trying to defend evangelicalism when its leaders behave indefensibly.

Is there a problem with hypocrisy in the modern church? Yes, just as there was in the ancient, medieval and renaissance churches. Fortunately, Christian doctrine and practice accounts for the fact that all of the churches members will remain in a state of sin. The church has a built-in “sin problem”.

Unfortunately, there is a lot of confusion regarding the proper response when this problem is recognized. There are many calls in the current culture for doctrine to bend because of pressures from the scientific community and public perception at large. The core issue is the insistence that individual feelings, cultural mores and scientific consensus should determine Church doctrine.

Ever since Søren Kierkegaard’s turn to experience in the 20th century, emotions and feelings have been increasingly exalted as vital to forming the modern worldview. Couple this with the Scopes trial in Dayton, Tennessee, and H. L. Mencken’s characterization of fundamentalists as the sort of folks who are the unlucky recipients of the rubbish tossed out of your upscale train car as you rode from New York to New Orleans, and you get a full-blown culture war. The term ‘fundalmentalism‘ meant something very different then when compared to the straw-man characterization popular now that casts biblical inerrantists as robotic and unschooled biblical literalists.

The Scopes trial has a fascinating history, with William Jennings Bryan leveraging his considerable oratorical skills to defend creationism with flourishes that emphasized the primacy of the the “rock of ages” over the “ages of rocks” that were a consistent focus of the evolutionary scientists at the trial. Mencken’s skillful pen drew up the battle lines, casting fundamentalists as emotional and pedantic as they fought against the tide of logic, progress and science — a characterization that has only grown stronger over time. After World War II, anti-communism and conservative Christianity sealed an alliance that became a tenant of american conservatism and the academy gradually became less and less associated with conservative values. It doesn’t help that our society has polarized overall due to natural feedback cycles and self-selectivity in location, education, marriages and vocations. We now have an educated and well-paid elite in the cities that are overwhelmingly liberal islands– both economically and religiously, while their surrounding territory has become more conservative. Moreover, these separate populations are now served by increasingly separate educational institutions, food distribution, and entertainment. The technology-enabled connectivity we are experiencing now is just accelerating everything into an increasingly polarized state.

While modern polarization between conservatives and progressives is heavily discussed, there is a lesser known population of evangelicals who are growing increasingly dis-enchanted with the traditional church. While they want to respect the traditional Church, they want a more modern version of Christianity which is consonant with their desire to love others and the current scientific/cultural consensus of their peers. They are open to a progressive doctrine and emphasize honesty over certainty. They want to offer something distinct than the image of Westboro Baptist Church, which has characterized evangelicals in the eyes of many.

Rachel Held Evans is a young blogger and author who tailors her work to this population and recently resonated with some my respected evangelical friends in her recent article How evangelicals won a culture war and lost a generation. One friend posted on Facebook that her article “could not have been said better” and was “exactly how [she had] been feeling.”

Ms Evans’s leverages her hometown of Dayton, Tennessee and its role in the culture wars to build a sympathetic audience online. She claims to be an active defender evangelicals, but her books and writings are consistently critical of the traditional church. Like the furniture store that is always going out of business to attract sales, Ms Evans has made a brand of continually walking away from conservative Christianity in a number of books and articles and here she once again galvanizes her audience as an insider who is walking away from the complications of dogma to the bliss of a culturally relevant and acceptable version of the Christian faith. She writes:

I, for one, am tired of arguing. I’m tired of trying to defend evangelicalism when its leaders behave indefensibly.

“I’m going AWOL on evangelicalism’s culture wars so I can get back to following Jesus among its many refugees: LGBT people, women called to ministry, artists, science-lovers, misfits, sinners, doubters, thinkers and “the least of these.”

Here she does something very subtle. While from her books, she has been AWOL from orthodox Christianity since 2008, she once again draws her boundaries which form the basis of her own salvo in the culture wars and then blames conservatives for the instigation. Implicit in her article is that you have to decide between a false dichotomy: you are either in the evangelical tent or you are an artist or scientist or sinner, or thinker.

I disagree. Outliers aside, the church I see is not going out of its way to prosecute homosexuals, but is simply defending its doctrine against a massive attack on its source of authority. I’ve never found the conservative church to be obsessed with this issue. I’ve never heard it mentioned in any sermon after attending 6 churches over 15 years–that is roughly 700 sermons. (The last time I heard a the pastor mention the sanctity of a marriage between a man and a woman in Boston 15 years ago at Park Street Church in Boston.) The church and its organizations are being asked this question on all fronts and even though many don’t want to answer it, they are being forced to show their hand. Will you redefine marriage? Will you buy contraception for your members? What is your position on gay rights/marriage? I have no doubt that if the church were pressed to celebrate divorce or gluttony or any of her present sins, that it would be forced to clarify her position on these matters as well, fortunately society hasn’t forced those questions on the church yet.

Aside from a incredibly small fringe, there is nothing like a symmetric response to the gay pride movement. There are just people like me, trying to live consistent and loving lives, but who can not change the foundations of our faith just because others want us to. To Christians like me, we are ready to change our mind if you can show me through what we consider to authoritative that homosexual behavior is approved, celebrated and sanctioned. To those who disagree, it is worth considering what evidence you would consider that would change your mind. If the answer is that there could be no external evidence outside of your own feelings about the subject, then you and I have a very different way of approaching the question: “What is truth?”

This is the issue for Christians: should they abandon their source of truth and replace it with something else? If so, what and why? Ms Evans doesn’t have any answers here. While she has built a brand around honesty and doubt, she exalts herself as the measure of truth and declares dogmatically:

“Christians can disagree about what the Bible says (or doesn’t say) about same-sex marriage. This is not an issue of orthodoxy.”

Now, what does she mean by orthodoxy? The definition of orthodoxy I’ve learned is an acceptance of transcendent standard rooted in tradition and authority. Without a transcendent standard, you have a church, and a Christ, without anything to offer. You might as well join the local meetup, it will cost you a lot less, help your resume, and fit better in your modern schedule.

But despite the hidden foundation of the article, which is to abandon conservative epistemology and jump in with the flow of the times, is there a real claim to the argument that lured in my friends?

“But when we begin using child sponsorships as bargaining tools in our debates, we’ve lost the way of Jesus”?

While Ms Evan’s faith is centered in the nebulous “way of Jesus” that I wish she would clarify, I have two key issues with her argument: (1) You can’t assume that the cessation of support for an organization is intended to harm or inconsiderate of the object of the charity and (2) there is good reason to keep ones philanthropic activities in line with ones values.

First, World Vision claims that financial concerns had nothing to do with their reversal and I have no reason to believe otherwise. While two articles I’ve read quote 2,000 and 4000 lost sponsorships, I have no idea of the real number. Lets assume there were three categories for lost sponsorships: (1) normal attrition, (2) “bargaining chip” moves that placed doctrine over the needs of needy children and hoarded their money or (3) individuals who out of conscience moved their money to another critical need since World Vision was now adhering to a view inconsistent with their values. We have no idea of the second category is significant, but Ms Evans seems to assume all evangelicals fit there. My guess would be a 1/4/95 {aaa01f1184b23bc5204459599a780c2efd1a71f819cd2b338cab4b7a2f8e97d4} split in the populations who ceased supporting. The second category, yes, behaved selfishly and are worthy of her rebuke. Admittedly, that is a lot of people by my own math, maybe 100 to 200 bad apples in the mix. However, it is the third category that I feel deserves a defense.

First, I think it is completely consistent to align one’s money with one’s values. If one affirms the traditional definition of marriage, they were out of sync with World Vision from its first position and it was the right thing to re-consider their partnership in light of this values disconnect. Consider if world vision would have announced that they no-longer supported women in leadership roles, or were no longer going to provide support to non-Christian children or children of a certain race. Such a position would have rightly caused a reconsideration by many to decide if they wanted to support such an organization and take their money elsewhere, even though some children would suffer and if the money were moved to another charity, other children would benefit. There are no shortages of excellent charities and we can never support them enough.

There is an additional line of logic implicit in her arguments and the supporting Facebook comments, that I find troubling. Two example Facebook comments are:

Just shifting your support to another organization still leaves those children you have been supporting through World Vision without the support they are counting on is unconscionable! Those are people! not just “recipients” of your money.

and

They still pulled their funds from 2000 children who needed the money for food, education and living in general. Doesn’t that upset you at all? Is it ok for those kids to starve now? I think as Christians we of all people should understand grace and being the hands and feet of Jesus.

From these comments, I (and all of us who withhold some of our funds from World Vision) am in a whole condemnable category of my own. I wasn’t a World Vision supporter in the first place and am therefore worthy of more condemnation than those who were giving but withdrew their support. Additionally, while I support other charities, I’ve certainly spent money on myself and on luxuries for my children that could have gone to saving other children. I purchased new clothes for my children when I could have provided food to others. Aren’t we all guilty here to some degree? And for an article that excoriates others for their judgmental actions, aren’t the comments above laden with a big bit of judgment resulting from a small bit of information?

One of the great ironies of this article, is that ignores the real suffering that has been caused by such a shift in support from governmental access and resources to faith-based organizations that have orthodox and traditional policies on abortion or homosexual activity. Who is going to advocate for the homeless in DC who can no longer receive food or the adoptive services which have been diminished in numerous cities as their federal funding has been pulled? Are these organizations not also “bargaining chips” in the culture wars?

In short, I applaud Ms Evans for winning a lot of eyeballs on the internet by putting together a compelling article with the right ingredients for internet stardom: a dramatic walking away from faith from an insider, a claim that she is not engaging in/even running away from culture wars from as she fans the flames, a scathing judgment against the judgmental conservatives in a non-judgmental way, and a framing of conservatives for fighting a war just to be right as they cling to ancient scriptures in the face of modern progress.

However, her most skillful move was to employ Mencken’s most effective weapon: the straw man which casts evangelicals as doctrinaire and so obsessed with persecuting well-meaning homosexuals that they are willing to throw children under the bus. For those who are apt to believe this characterization accurately reflects a sizable percent of those who removed their funding, I would recommend that you step back and talk with someone who withdrew their support. You might just find they are a lot more reasonable than Ms Evans makes them out (or needs them) to be to sell her books.