Solving integer constrained optimization problems

Question

I'm new to these problems both mathematically and programmatically. If anyone could suggest a c++ library to use that could solve the following problem I would really appreciate it.

Given constants:

{x_1, ..., x_n}, {y_1, ..., y_n}, {z_1, ..., z_n}, C, & variables {q_1, ..., q_n}

Maximize: sum(i = 1..n} q_i*x_i

Subject to: C - sum(i = 1..n){ sum(j = 1..q_i) [y_i + (j-1)*z_i ] } >= 0 AND q_i >= 0

All constants are integers greater than zero. The q_i's are also integers.

So I'm trying to solve for {q_1, ..., q_n}

Answer 1

Sounds like an optimization problem that would be well suited to linear programming. The GNU Linear Programming Kit (GLPK) is a full-featured C library for this.

IBM has a nice tutorial about linear programming and how to do it with GLPK here.