• Registered: 2008-12-16
  • Posts: 4

Topic: 2 Challenges

I apologise if this forum is only intended for serious content (maybe there could be a fun forum?), but here's a pair of challenges:

A, B and C decide to go for a 10km walk. A and B can walk at 4kmh and C can walk at 8kmh. They also have a bicycle which only one of them can use at a time. When riding, A and B can travel at 24kmh while C can ride at 32kmh.

What is the shortest time in which all three can complete the trip, and how do they do it?

n.b. my solution is written in Maxima, which is open source, but which is a CAS rather than a Linear Programming package - but it has a simple simplex solver, and, usefully for this problem, a function for generating permutations.

For this one, I used LP_Solve, because it requires integers:

In my pocket I have £41.58 which is made up of different denominations of coins. There is exactly the same number of each coin. What is the minimum number of coins I have, and what are they? (Britain has 8 commonly used coins, and in GBP their values are: 0.01, 0.02, 0.05, 0.10, 0.20, 0.50, 1, 2).

Quote Post 1

  • Dmitrey
  • OpenOpt developer
  • Offline
  • From: Cherkasy town, Ukraine
  • Registered: 2008-12-15
  • Posts: 424

Re: 2 Challenges

For the problems with bicycle it's hard for me to dig in because I'm not keen on permutations theory and tricks.

My solution for pounds problem:
11 coins of each type except of 0.10
however, I used global non-linear problem instead.
Here's openopt code:
##########
from openopt import *
from numpy import *

# 1st  coord is coints number for a single type
# coords 2, 3, ..., 9 etc are 0 or 1:
# are coins of type 0.01, 0.02, 0.05, 0.10, 0.20, 0.50, 1, 2 present or absent

arr = array((0.01, 0.02, 0.05, 0.10, 0.20, 0.50, 1, 2))

# upper bound estimation
max_n_coins = 15 # search for no more than number of a single type coins = max_n
min_n_coins = int(0.99*41.58 / arr.sum())

x0 = [0]*9
def callback(p):
    if abs(p.xk[0]*(p.xk[1:] * arr).sum() - 41.58) < 1e-3:
        return True
    else:
        return False
       
p = GLP(lambda x: x[0] + 10*abs(41.58 - (x[0] * x[1:] * arr).sum()), lb=[min_n_coins] + [0]*8, ub=[max_n_coins] + [1]*8, x0=x0, maxIter = 10000, iprint = 100,  maxFunEvals = 1e15, maxTime = 15, callback =  callback)

solver = oosolver('galileo', useInteger=True, population = 15,  mutationRate = 0.15)# it could be turned better but I have no time
r = p.solve(solver)

if p.istop > 0: print('number of each type coins: ' + str(r.xf[0]) + '; coins involved: ' + str(arr * r.xf[1:]))
else: print 'failed, please restart'
##########

typical output (about 9/10 cases converged ok during 0.1...1 sec):
solver: galileo   problem: unnamed   goal: minimum
iter    objFunVal   
    0  4.158e+02
  100  1.320e+01
  200  1.320e+01
  238  1.100e+01
istop:  80
Solver:   Time Elapsed = 1.09     CPU Time Elapsed = 1.05
objFunValue: 11 (feasible, max constraint =  0)
number of each type coins: 11.0; coins involved: [ 0.01  0.02  0.05  0.    0.2   0.5   1.    2.  ]

Dmitrey's Website

Quote Post 2

  • Registered: 2008-12-16
  • Posts: 4

Re: 2 Challenges

Dmitrey wrote:

For the problems with bicycle it's hard for me to dig in because I'm not keen on permutations theory and tricks.

Actually, if you have a guess at the order in which they use the bicycle, you will probably be right. I only wrote the extra code to generate all permutations because I wanted to check.

Dmitrey wrote:

My solution for pounds problem: 11 coins of each type except of 0.10

11 + 2*11 + 5*11 + 20*11 + 50*11 + 100*11 + 200*11 = 4158
You used 77 coins, which is a good answer! However - there is an even better one available...

Quote Post 3

  • Dmitrey
  • OpenOpt developer
  • Offline
  • From: Cherkasy town, Ukraine
  • Registered: 2008-12-15
  • Posts: 424

Re: 2 Challenges

Ok, here's the better solution:
total number of coins: 72
num of each type coins: 18
coins involved: [   1.    0.    0.   10.   20.    0.    0.  200.]

Here's openopt code:
####################
from openopt import *
from numpy import *
Coins = [1, 2, 5, 10, 20, 50, 100, 200]
nCoins = len(Coins)

for i in xrange(1, 80):
   
    beq = 4158.0 / i
    Aeq = Coins
   
    p = MILP(f = ones(nCoins), Aeq = Aeq,  beq=beq, A=A, b=b, lb=zeros(nCoins), ub=ones(nCoins), intVars = range(nCoins))   
    r = p.solve('lpSolve', iprint=-1)
    #or using glpk solver, glpk+cvxopt should be installed:
    #r = p.solve('glpk', iprint = -1)
    #however  absence of A yields error from CVXOPT so I put a dummy : p.A = ones(nCoins), p.b = 100000
    if r.istop > 0:
        print '--------------------------'
        print('total number of coins: %d' % (i * len(where(r.xf!=0)[0])))
        print('num of each type coins: %d' % i)
        print('coins involved: ' + str(Coins * r.xf))
##################
It takes about a 0.5 second to yield the output:
--------------------------
total number of coins: 77
num of each type coins: 11
coins involved: [   1.    2.    5.    0.   20.   50.  100.  200.]
--------------------------
total number of coins: 72
num of each type coins: 18
coins involved: [   1.    0.    0.   10.   20.    0.    0.  200.]
--------------------------
total number of coins: 132
num of each type coins: 33
coins involved: [   1.    0.    5.    0.   20.    0.  100.    0.]
--------------------------
total number of coins: 216
num of each type coins: 54
coins involved: [  0.   2.   5.   0.  20.  50.   0.   0.]
--------------------------
total number of coins: 252
num of each type coins: 63
coins involved: [  1.   0.   5.  10.   0.  50.   0.   0.]
--------------------------
total number of coins: 264
num of each type coins: 66
coins involved: [  1.   2.   0.  10.   0.  50.   0.   0.]

Dmitrey's Website

Quote Post 4

  • Registered: 2008-12-16
  • Posts: 4

Re: 2 Challenges

Dmitrey wrote:

Ok, here's the better solution:
total number of coins: 72
num of each type coins: 18
coins involved: [   1.    0.    0.   10.   20.    0.    0.  200.]

Yay!!!

LP_Solve has a feature called special ordered sets which allows the user to stipulate that only a specified number of the given variables can be non-zero. I used {letter}1 for used coins and {letter}2 for unused coins.

I set up the schema to minimise the number of coins needed as follows:

min: a1 + b1 + c1 + d1 + e1 + f1 + g1 + h1;
a1 + a2 = b1 + b2;
a1 + a2 = c1 + c2;
a1 + a2 = d1 + d2;
a1 + a2 = e1 + e2;
a1 + a2 = f1 + f2;
a1 + a2 = g1 + g2;
a1 + a2 = h1 + h2;
a1 + 2 b1 + 5 c1 + 10 d1 + 20 e1 + 50 f1 + 100 g1 + 200 h1 = 4158;
int a1, a2, b1, b2, c1, c2, d1, d2, e1, e2, f1, f2, g1, g2, h1, h2;
sos
SOS: a1, a2 <= 1;
sos
SOS: b1, b2 <= 1;
sos
SOS: c1, c2 <= 1;
sos
SOS: d1, d2 <= 1;
sos
SOS: e1, e2 <= 1;
sos
SOS: f1, f2 <= 1;
sos
SOS: g1, g2 <= 1;
sos
SOS: h1, h2 <= 1;

...and here is the output:

Value of objective function: 72

Actual values of the variables:
a1                             18
b1                              0
c1                              0
d1                             18
e1                             18
f1                              0
g1                              0
h1                             18
a2                              0
b2                             18
c2                             18
d2                              0
e2                              0
f2                             18
g2                             18
h2                              0

So 72 coins are used - 18 each of a1, d1, e1 and h1 - which represent 1p, 10p, 20p and £2 (200p) coins.

Quote Post 5

6 Reply by Guestuser

  • Guestuser
  • Guest

Re: 2 Challenges

CPLEX has a feature called Indicator Constraints, which can be an elegant way of thinking of certain kinds of relationships among variables.  With the following model in CPLEX's LP format I get the 18 coin solution too:

Minimize
obj: x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8
Subject To
c1: 0.01 x1 + 0.02 x2 + 0.05 x3 + 0.1 x4 + 0.2 x5 + 0.5 x6 + x7 + 2 x8
      = 41.58
i1:  y1 = 0 -> x1  = 0
i2:  y2 = 0 -> x2  = 0
i3:  y3 = 0 -> x3  = 0
i4:  y4 = 0 -> x4  = 0
i5:  y5 = 0 -> x5  = 0
i6:  y6 = 0 -> x6  = 0
i7:  y7 = 0 -> x7  = 0
i8:  y8 = 0 -> x8  = 0
i9:  y1 = 1 -> x1 - N  = 0
i10: y2 = 1 -> x2 - N  = 0
i11: y3 = 1 -> x3 - N  = 0
i12: y4 = 1 -> x4 - N  = 0
i13: y5 = 1 -> x5 - N  = 0
i14: y6 = 1 -> x6 - N  = 0
i15: y7 = 1 -> x7 - N  = 0
i16: y8 = 1 -> x8 - N  = 0
Binaries
y1  y2  y3  y4  y5  y6  y7  y8
Generals
x1  x2  x3  x4  x5  x6  x7  x8  N
End

Quote Post 6

7 Reply by Andrew Makhorin

  • Andrew Makhorin
  • Guest

Re: 2 Challenges

The correct solution is 25 coins:

x[1] = 1
x[2] = 1
x[5] = 1
x[10] = 0
x[20] = 0
x[50] = 1
x[100] = 1
x[200] = 20

Below here is the MathProg model I used to obtain the solution.


set COINS;

param denom{c in COINS};

var x{c in COINS}, >= 0, integer;

param s;

s.t. foo: sum{c in COINS} c * x[c] = s;

minimize obj: sum{c in COINS} x[c];

solve;

display x;

data;

set COINS := 1 2 5 10 20 50 100 200;

param s := 4158;

end;

Quote Post 7

  • Dmitrey
  • OpenOpt developer
  • Offline
  • From: Cherkasy town, Ukraine
  • Registered: 2008-12-15
  • Posts: 424

Re: 2 Challenges

Andrew Makhorin wrote:

The correct solution is 25 coins:

x[1] = 1
x[2] = 1
x[5] = 1
x[10] = 0
x[20] = 0
x[50] = 1
x[100] = 1
x[200] = 20

Below here is the MathProg model I used to obtain the solution.

Hi Andrew,
you have misunderstood the task (as well as I had done first time, however, in other way)
in your solution x[200] = 20 that is not equal to x[100] = 1. All non-zero numbers must be equal.

As for MathProg, I'm not familiar with the language, still there is one thing for sure - I can't take the languages where semicolon (or or any other symbol) has to be put in the end of each line. This is one of the reasons why I had migrated from C/C++ and MATLAB/Octave to Python.
BTW, fortunately, Fortress language (I consider it very promising) has no the drawback.

Thank you for your GLPK tool,
Regards, Dmitrey.

Dmitrey's Website

Quote Post 8

9 Reply by Andrew Makhorin

  • Andrew Makhorin
  • Guest

Re: 2 Challenges

> you have misunderstood the task (as well as I had done first
> time, however, in other way)
> in your solution x[200] = 20 that is not equal to x[100] = 1. All
> non-zero numbers must be equal.

You are right. I considered the change making problem.

Adding the missing constraint leads to the following solution:

x[1] = 18
x[2] = 0
x[5] = 0
x[10] = 18
x[20] = 18
x[50] = 0
x[100] = 0
x[200] = 18

> As for MathProg, I'm not familiar with the language, still there
> is one thing for sure - I can't take the languages where
> semicolon (or or any other symbol) has to be put in the end of
> each line. This is one of the reasons why I had migrated from
> C/C++ and MATLAB/Octave to Python.
> BTW, fortunately, Fortress language (I consider it very
> promising) has no the drawback.

Such reason sounds a bit strange. :)

FYI: GNU MathProg is a subset of AMPL implemented in glpk.

Quote Post 9