solving an equation where some unknowns must be integers

Answer 1

Please use Maple, Mathcad or Sage for that. Here is a list of software, that can help you with it: http://en.wikipedia.org/wiki/Comparison_of_computer_algebra_systems

Answer 2

I think that unreason gave the correct answer. You need to read a book about "Nonlinear Integer Programming". I don't have a good book to recommend you, but you can probably find something by going to the library.

I don't think that lp_solve is not good enough for you, because you cannot rewrite your problem in to a mixed integer Integer linear Programming problem (MILP). Maple and Mathcad is not a good idea, because you are not looking for symbolic algebra package.

My guess us that the book will tell you to do branch and bound. Here is a schematic description:

1) Start out solving a generalized problem where t_k are all real prsitime numbers

minimize Σnk = 1 (1 - min(s·tk,Ck)/max(s·tk,Ck)), under the constrain that s > 0, t1…tn ∈ R+

.You can use a generalized Newtons method to do this. Matlab and scipy provide generalized solvers this out of the box, but be careful because your function may have several local minima.

2) Once you have found this solution, you can do a branch ing step. Choose a variables t_k and an integer number a_k, and solve the following two problems independently

Problem 1 minimize Σnk = 1 (1 - min(s·tk,Ck)/max(s·tk,Ck)), under the constrain that s > 0, t1…tn ∈ R+and t_k <= a_k

Problem 2 minimize Σnk = 1 (1 - min(s·tk,Ck)/max(s·tk,Ck)), under the constrain that s > 0, t1…tn ∈ R+ and t_k >= a_k

3) Keep doing branching steps until you have split your problem in to a set of sub-problems that each have an integer solution. Then you can compare these integer solutions and choose the best one.

As you probably have guessed this description is somewhat schematic. You need good branching rules to branch the correct way, and you need good bounding rules to avoid following branches that arent promising.