Optimizing for the longest distance travelled

Question

I was had a question about optimizing for the longest distance travelled.

Suppose there is a highway which we can use to travel for a specific distance based on a set of fee rules involving 3 types of tokens x, y, z. You are given a set amount of each type of tokens and The fee rules are of the following form and is asked to maximize the distance travelled,

 30x's + 10y's + 10z's -> d_1km
 30x's + 10y's + 0z's  -> d_2km
 30x's + 0y's + 0z's   -> d_3km
 5x's + 0y's + 0z's    -> d_4km
 5x's + 3y's + 3z's    -> d_5km

My initial thought was to order the distance travelled from largest to smallest and try to spend my tokens in that order, but I believe this will cause me to miss out on some edge deals that will enable me to go even further. I believe I've seen some mathematical concept to optmizing this type of problems, but I can't remember exactly what this is called. Any hints or pointers as to how to tackle this problem is greatly appreciated!

Answer 1

There is probably a dynamic programming approach here as well, but a standard way to approach this type of problem is to set it up as an Integer Linear Program (ILP) as the decision variables are naturally integers. There are several python packages that can set up the model (pulp, pyomo, CVXOPT, others), and several free solvers that can solve ILP problems such as CBC and glpk using the "branch and bound" or similar algorithm. Most frameworks that can set up the model are separate from the solver.

Here is an example setup of your problem in pyomo which uses the separately installed cbc solver.

Code

import pyomo.environ as pyo

# DATA
#                  dist  X   Y   Z
highways = { 'h1': (24, (30, 10, 10)),
             'h2': (17, (30, 10, 0 )),
             'h3': (22, (30, 0,  0 )),
             'h4': (8,  (5,  0,  0 )),
             'h5': (13, (5,  3,  3 ))}

tokens = {'X': 64, 'Y': 15, 'Z': 12}

# a convenience...
token_types = list('XYZ')
costs = {}
for idx, t in enumerate(token_types):
    for h in highways.keys():
        costs[(h, t)] = highways[h][1][idx]

# set up ILP
m = pyo.ConcreteModel()

# SETS

m.H = pyo.Set(initialize=highways.keys())
m.T = pyo.Set(initialize=token_types)      # token types

# PARAMS
m.tokens_avail = pyo.Param(m.T, initialize=tokens)
m.dist         = pyo.Param(m.H, initialize={k:v[0] for k, v in highways.items()})
m.cost         = pyo.Param(m.H, m.T, initialize=costs)

# VARS
m.pay    = pyo.Var(m.H, m.T, domain=pyo.NonNegativeIntegers)   # pay this many tokens of type t on highway h
m.travel = pyo.Var(m.H, domain=pyo.NonNegativeIntegers)        # travel on highway h this many times

# OBJECTIVE
# maximize distance traveled, add some tiny penalty to prevent spending unneeded tokens
m.obj = pyo.Objective(expr=pyo.sum_product(m.dist, m.travel) - 0.01 * pyo.sum_product(m.pay), sense=pyo.maximize)

# CONSTRAINTS
# limit token use to available, for each type
def token_limit(m, t):
    return sum(m.pay[h, t] for h in highways) <= m.tokens_avail[t]
m.C1 = pyo.Constraint(m.T, rule=token_limit)

# pay the cost of each trip
def pay_tokens(m, h, t):
    if not m.cost[h, t]:
        return pyo.Constraint.Skip
    return m.travel[h] <= m.pay[h, t] / m.cost[h, t]
m.C2 = pyo.Constraint(m.H, m.T, rule=pay_tokens)

# check the model...
m.pprint()


solver = pyo.SolverFactory('cbc')
res = solver.solve(m)
print(res)

tot_distance = pyo.sum_product(m.dist, m.travel)

print(f'total distance achieved: {pyo.value(tot_distance)}')

for idx in m.travel.index_set():
    if m.travel[idx]:
        print(f'travel {idx} {pyo.value(m.travel[idx])} times')

for idx in m.pay.index_set():
    if m.pay[idx]:
        print(f'pay {pyo.value(m.pay[idx])} {idx[1]} tokens on {idx[0]}')

Output (partial)

Problem: 
- Name: unknown
  Lower bound: -115.16
  Upper bound: -115.16
  Number of objectives: 1
  Number of constraints: 13
  Number of variables: 20
  Number of binary variables: 0
  Number of integer variables: 20
  Number of nonzeros: 20
  Sense: maximize
Solver: 
- Status: ok
  User time: -1.0
  System time: 0.0
  Wallclock time: 0.01
  Termination condition: optimal
  Termination message: Model was solved to optimality (subject to tolerances), and an optimal solution is available.
  Statistics: 
    Branch and bound: 
      Number of bounded subproblems: 0
      Number of created subproblems: 0
    Black box: 
      Number of iterations: 2
  Error rc: 0
  Time: 0.01609015464782715
Solution: 
- number of solutions: 0
  number of solutions displayed: 0

total distance achieved: 116.0
travel h4 8.0 times
travel h5 4.0 times
pay 40.0 X tokens on h4
pay 20.0 X tokens on h5
pay 12.0 Y tokens on h5
pay 12.0 Z tokens on h5