Solver Problems

A solver problem is a multivariable or combinatorial problem without an obvious mathematical solution. While that may sound like a mouthful, these types of problems are faced by everyone, nearly every day. For example, deciding which route to take when going to a meeting, or creating a schedule for a significant number of employees. These problems often have no known best solution - for example, did I choose the fastest route (even if I used Google maps)? Did I create the most efficient schedule?

In smaller cases (e.g., fewer options for the route to take or fewer employees to schedule), these problems can sometimes be solved exactly, but they grow more complex exponentially given the number of options (i.e., variables).

Solver problems are generally defined by three key components:

• Variables: These are the output of the solver, or what is trying to be solved. For example, the different options for traveling from point A to point B or the shifts and days and employees for a schedule.

• Constraints: These are mathematical definitions (i.e., formulas) of what is allowable in the solution space - or the “rules” of the problem. For example, in the routing case, certain vehicles are not allowed by law on certain roads. Or in the scheduling case, certain employees can only work one weekend per month.

  For example, here is a constraint taken from the supply-chain (see "PBS" demo) sample problem. This constraint simply states that the origin and destination must be different for a segment, given it makes no sense to ship something to the same place!

  \(\sum_{\left(r,s\right)\in\phi}\sum_{i} x_{ri}x_{si} = 0\)

• Objective: This is also a formula that is to be minimized or maximized. In the routing example, an objective could be to minimize distance or time. In the scheduling example, the objective could be to minimize over or under staffing while maximizing employee shift requests.

  For example, here is the objective function from the supply-chain sample problem. cost is a matrix which defines the expense of going from location r to location s and the objective is to minimize the sum of all segments in the route:

  \(C = \sum_{\left(r,s\right)\in\psi}cost(r_a,s_a)\)

Solver Problems in Amazolve

In Amazolve, variables are represented as an two dimensional (2D) array of “atoms” and constraints and objectives are defined in a problem.json file using nested summations and expressions. The mathematical formulas that define a specific problem (the constraints and objective) are always defined as summations - for example, the sum of all segments of a route, or the sum of all hours an employee works. Thus, Amazolve uses this to organize the problem.json file and in fact the entire problem definition itself.

Given the sample constraint and objective formulas shown above, here's how they would look in Amazolve's problem.json file:

• Constraint:

{
  "constraint": {
    "CID": "C2",
    "comment": "Constraint #2 - Origin and destination must be different",
    "penaltyVar": "hardPenalty",
    "sumIter": "iterArray",
    "arrayName": "phi",
    "iterVars": [
      "r",
      "s"
    ],
    "sums": [
      {
        "sumIter": "iterDim",
        "iterDim": "S",
        "iterVars": [
          "i"
        ],
        "exprMain": "Xr(r, i) * Xr(s, i)"
      }
    ]
  }
}

• Objective:

{
  "constraint": {
    "CID": "C",
    "sumIter": "iterArray",
    "arrayName": "phi",
    "iterVars": [
      "r",
      "s"
    ],
    "sums": [
      {
        "sumIter": "iterDim",
        "iterDim": "S",
        "iterVars": [
          "i"
        ],
        "sums": [
          {
            "sumIter": "iterDim",
            "iterDim": "S",
            "iterVars": [
              "j"
            ],
            "exprMain": "cost(r, i, j) * Xr(r, i) * Xr(s, j)"
          }
        ]
      }
    ]
  }
}