Linear Programming

I've already been using a linear programming library to do TOP-max optimizations. But I didn't know the background and happened to find some references recently. Mainly, this FAQ:

http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html

but also this online book about optimization:

http://www.sce.carleton.ca/faculty/chinneck/po.html

A linear program is either a minimization or maximization problem of a linear function with linear constraints. The FAQ gives the Standard Form as

minimize cx
subject to Ax = b
x >= 0

where x is a vector of variables and so on. The way I've been solving TOP-max is that I tell it to minimize the error, and constrain the error to be no smaller than the error in each prime for a given pair of generator sizes. This may be more efficient as an unconstrained optimization of a piecewize linear function, but it works as a linear program.

It's also possible to constrain some of the variables to be integers. This is called, among other things, mixed integer linear programming. Provided you keep the period fixed you can find the period mapping as part of the program. I've appended an example Python script that does this using PuLP and my regular temperament library. It's responsive but I haven't profiled it for a large number of optimizations.

You can't optimize for the period mapping and the period size with the same linear program because the period is multiplied by each element of the mapping. Linear programming doesn't allow for one variable being multiplied by another. This would, however, work as a quadratic program. It turns out that quadratic problems are quite common as well but I don't know of free libraries to solve them with integers. If you can find one, you could try doing the whole regular temperament search with it. Set the full mapping and generator sizes as variables and constrain it to have a low error and complexity.

There are other problems linear programming might help us with. Adaptive temperament is an optimization problem and, as I mentioned on the main list, it can probably be described as a linear program. I haven't worked out the details to be sure there are no nonlinearities though. Linear programs are routinely solved with thousands of variables. That standard simplex algorithm is non-polynomial but still efficient for such simple problems.

Here's that Python code. Hopefully Yahoo don't mangle the indentation any more.

"""Solve a regular temperament using mixed integer linear programming"""

import regular, pulp

def LinearTemperament(mapping, primes):
"""Return a temperament from an octave-equivalent mapping"""

prob = pulp.LpProblem("kees", pulp.LpMinimize)

# extract information from the mapping
octave = regular.hcf(mapping)
generatorMapping = [m/octave for m in mapping]

# set three variables: the generator and the error limits
generator = pulp.LpVariable("generator", 0, 1.0/octave)
maxError = pulp.LpVariable("maxError", 0, None)
minError = pulp.LpVariable("minError", None, 0)

# construct a period mapping including some parameters
period = 1.0/octave
periodMapping = [
pulp.LpVariable("M0%i"%i, None, None, pulp.LpInteger)
for i in range(1, len(primes))]

# specify that it's the error range we want to minimize
prob += maxError - minError, "obj"

# now set the errors of the temperament as constraints
for i in range(len(primes)-1):
weightedPrime = (periodMapping[i]*period +
generator*generatorMapping[i])/primes[i+1]
error = weightedPrime - 1
prob += maxError >= error
prob += minError <= error

prob.solve(pulp.GLPK(msg=0))

mapping = ([octave]+[e.varValue for e in periodMapping],
[0]+generatorMapping)
melody = [(a, a+b) for a, b in zip(mapping[0], mapping[1])]
result = regular.Rank2Temperament(primes, 1,
mapping[0], mapping[1], melody)
result.basis = (period, generator.varValue)
return result

if __name__=='__main__':
print LinearTemperament((1, 4), regular.limit5)
print LinearTemperament((0, 29, 29, 29, 29), regular.limit13)

>TOP-max

You've been saying this lately. Does it refer to Paul's TOP,
or your primes-only TOP?

-Carl

Carl Lumma wrote:
>>TOP-max
> > > You've been saying this lately. Does it refer to Paul's TOP,
> or your primes-only TOP?

They're both the same.

Graham

>>>TOP-max
>>
>> You've been saying this lately. Does it refer to Paul's TOP,
>> or your primes-only TOP?
>
>They're both the same.

Do you show this in your paper, and if so can you tell me
roughly where?

-Carl

Carl Lumma wrote:
>>>>TOP-max
>>>
>>>You've been saying this lately. Does it refer to Paul's TOP,
>>>or your primes-only TOP?
>>
>>They're both the same.
> > > Do you show this in your paper, and if so can you tell me
> roughly where?

Paul shows it in his paper, one of the footnotes, and I give a citation. I mention it in "Weighted Worst Errors".

Graham