Hi!

These are multiple fields of study you are talking about, JuMP is just the tip of an iceberg! Combinatorial optimization is actually an older field of study from what is known as integer programming nowadays, rooted more in the old field of graph theory, but you probably shouldn’t be surprised if they get used as synonyms these days. You have to differentiate between the problem semantics (with its complexity class), and the modelling technique and algorithm used to solve such problem. Integer programming is concerned with the mathematical/algebraic modelling of a combinatorial optimization problem as an integer program (IP) and then solving it using algorithms such as LP relaxation and branch and bound. The most generic IP problem is NP-Hard because other known NP-Hard problems from graph theory can be written as special case IPs. Mixed integer programs (MIP) are at least as hard as integer programs, because every IP can be trivially written as an MIP by adding a single dummy continuous variable with 0 coefficient in every constraint. Proving that one specific problem (referring to the semantics not a particular model or algorithm) is in P, NP-Complete or any other time complexity class is a whole field of study, known as complexity theory.

You can solve your (NP-Hard) combinatorial optimization problem by first writing it as an IP and then solving the IP. But the basic algorithm for IPs is hardly used solely for NP-Hard problems. Usually it is mixed with other problem-specific and/or evolutionary heuristics to get better solutions more quickly, and/or the algorithm is modified in some other fancy way that is again problem-specific, e.g. Lagrangian relaxation, branch and price, constraint generation, etc. When the problem is in P, you can bet that there is a better algorithm out there for that specific problem which you can use directly without going through integer programming at all.

For your problem, you might want to check constraint programming aka CP (closely related to logic programming) which is a nice competitor of integer programming for solving problems with semantics that are easier to describe in logic than in algebra. I believe scheduling is one of CP’s most braggable applications. This can also be mixed with heuristics to speed things up. Many scheduling problems can be reduced to the travelling salesman problem (TSP) or the resource constraint project scheduling problem (RCPSP) which are both NP-Hard but you need to double check your specific problem semantics. Read about MiniZinc and a guy named Peter Stuckey (Melbourne) who is one of the developers of MiniZinc. He has a nice online course teaching it too. CP has nothing to do with JuMP btw. All JuMP does is just help you write your mathematical program (MP), e.g. LP, IP, MILP, NLP, MINLP etc. and then send it to a compatible solver that will try to solve it. JuMP will also let you talk to the solver wherever possible and make the answer easily accessible to you. If your original problem is NP-Hard and big enough, chances are the solver will fail to return an answer in the time available to you, or it could return the best answer found which may or may not be useful. MiniZinc does a similar job as JuMP but for CPs, the default solver is Gecode.

Ideally you should find some papers which solved a similar problem as the one you have and try to learn from them before walking down that path on your own. Optimization theory is a very useful but complex field of study with a lot of jargon and acronyms thrown around, so be mindful of what you are getting yourself into! Now I need a break!