search

open-connectome-classes / StatConn-Spring-2015-Info

introductory material
18 stars 4 forks source link

Optimization question: Integer programming #206

Open mrjiaruiwang opened 9 years ago

mrjiaruiwang commented 9 years ago

So we talked today in class about how we can formulate a lot of these optimization problems as integer programs, but is there a generic way to solve integer programs in the form of:

minimize some objective function subject to constraints (one of which is that the optimal solution to the objective function takes integer values)

Does there exist a general algorithm for these that does not make any assumptions about particular objective functions or constraints that is faster than exponential time?

jtmatterer commented 9 years ago

Even in the case of a linear objective function and linear constraints, integer programming is NP-complete.