CODEWITHSUNDEEP
javascriptoptimizationmathematical-optimizationcalculus
Antoni4
Antoni4

Reputation: 2693

The maximum volume of a box

Trying to write a simple web app to solve the following common calculus problem in JavaScript.

Suppose you wanted to make an open-topped box out of a flat piece of cardboard that is L long by W wide by cutting the same size square (h × h) out of each corner and then folding the flaps to form the box, as illustrated below:

box_vol_problem

You want to find out how big to make the cut-out squares in order to maximize the volume of the box.

Ideally I want to avoid using any calculus library to solve this.

My initial naive solution:

// V = l * w * h
function getBoxVolume(l, w, h) {
  return (l - 2*h)*(w - 2*h)*h;
}

function findMaxVol(l, w) {
  const STEP_SIZE = 0.0001;

  let ideal_h = 0;
  let max_vol = 0;

  for (h = 0; h <= Math.min(l, w) / 2; h = h + STEP_SIZE) {
    const newVol = getBoxVolume(l, w, h);
    if (max_vol <= newVol) {
      ideal_h = h;
      max_vol = newVol;
    } else {
      break;
    }
  }

  return {
    ideal_h,
    max_vol
  }
}

const WIDTH_1 = 20;
const WIDTH_2 = 30;

console.log(findMaxVol(WIDTH_1, WIDTH_2))

// {
//   ideal_h: 3.9237000000038558,
//   max_vol: 1056.3058953402121
// }

The problem with this naive solution is that it only gives an estimate because you have to provide STEP_SIZE and it heavily limits the size of the problem this can solve.

Upvotes: 0

Views: 512

Answers (2)

Antoni4
Antoni4

Reputation: 2693

After realising that the derivative of the volume function is a second degree polynomial you can apply a quadratic formula to solve for x.

Using calculus, the vertex point, being a maximum or minimum of the function, can be obtained by finding the roots of the derivative

// V = l * w * h
function getBoxVolume(l, w, h) {
  return (l - 2*h)*(w - 2*h)*h;
}

// ax^2 + bx + c = 0
function solveQuad(a, b, c) {
  var x1 = (-1 * b + Math.sqrt(Math.pow(b, 2) - (4 * a * c))) / (2 * a);
  var x2 = (-1 * b - Math.sqrt(Math.pow(b, 2) - (4 * a * c))) / (2 * a);
  return { x1, x2 };
}

function findMaxVol(l, w) {    
  // V'(h) = 12h^2-4(l+w)h+l*w - second degree polynomial
  // solve to get the critical numbers
  const result = solveQuad(12, -4*(l + w), l*w)

  const vol1 = getBoxVolume(l, w, result.x1);
  const vol2 = getBoxVolume(l, w, result.x2);

  let ideal_h = 0;
  let max_vol = 0;

  // check for max
  if (vol1 > vol2) {
    ideal_h = result.x1;
    max_vol = vol1;
  } else {
    ideal_h = result.x2;
    max_vol = vol2;
  }

  return {
    ideal_h,
    max_vol
  } 
}

const WIDTH_1 = 20;
const WIDTH_2 = 30;

console.log(findMaxVol(WIDTH_1, WIDTH_2))

// {
//   ideal_h: 3.9237478148923493,
//   max_vol: 1056.30589546119
// }

Upvotes: 2

MyStackRunnethOver
MyStackRunnethOver

Reputation: 5275

You have an objective function: getBoxVolume(). Your goal is to maximize the value of this function.

Currently, you're maximizing it using something equivalent to sampling: you're checking every STEP_SIZE, to see whether you get a better result. You've identified the main problem: there's no guarantee the edge of the STEP_SIZE interval falls anywhere near the max value.

Observe something about your objective function: it's convex. I.e., it starts by going up (when h = 0, volume is zero, then it grows as h does), it reaches a maximum, then it goes down, eventually reaching zero (when h = min(l,w)/2).

This means that there's guaranteed to be one maximum value, and you just need to find it. This makes this problem a great case for binary search, because given the nature of the function, you can sample two points on the function and know which direction the maximum lies relative to those two points. You can use this, with three points at a time (left, right, middle), to figure out whether the max is between left and middle, or middle and right. Once these values get close enough together (they're within some fixed amount e of each other), you can return the value of the function there. You can even prove that the value you return is within some value e' of the maximum possible value.

Here's pseudocode:

max(double lowerEnd, upperEnd) {

    double midPoint = (upperEnd + lowerEnd) / 2

    double midValue = getBoxVolume(l, w, midpoint)

    double slope = (getBoxVolume(l, w, midpoint + epsilon) - midValue) / epsilon

    if (Math.abs(slope) < epsilon2) { // or, if you choose, if (upperEnd - lowerEnd < epsilon3)
        return midpoint
    }

    if (slope < 0) { // we're on the downslope
        return max(lowerEnd, midPoint)
    }

    else { // we're on the up-slope
        return max(midpoint, upperEnd)
    }
}

Upvotes: 2

Related Questions