Research vs Homework

i don't know how these two things differ in other fields, but it seems there's a key difference between research and homework. Sure, they both involve solving problems, generally using methods previously discovered. But homework is normally structured in a much nicer format than research. Generally homework questions come at the end of a chapter which just introduced a new theoretical framework for solving problems. So these homework problems will generally just test a student's ability to put this theoretical framework into action (even if its the theoretical action of a proof). Sometimes these problems will ask you to go back a few chapters and use other theoretical work as well, but thats the most they ask.

Research is a different beast in itself. The research problems are generally just concepts that somebody notices or thinks up, so something that can seem obvious may be really hard to prove (see Goldbach Conjecture). Further, there's no general recipe for all the type of things you'll need in research. And if it happens that you need something that you haven't yet learned, then I guess you've got some studying to do.

I'm thinking about this right now because I just finished working on a research problem that was pretty annoying. When I first heard the problem proposed, I knew very little about integer programming or linear programming. I had related the problem to the Maximum Independent Set (MIS) problem and felt pretty annoyed that because the MIS problem is NP-Complete (lets just say really hard), I wouldn't be able to get further. Back then, I simply wrote computer programs to try to enumerate all the feasible solutions - but stopped when I was able to prove that the programs would take a long LONG time to finish. I was able to solve some smaller instances of the problem by hand and left the larger instances alone.

Well this weekend, I went back to the larger instances. Initially I started with some of those same thoughts, and the lazy programmer in me just wanted to write a nested for loop and call it a day. But again, being able to see how long that program would take to run, I kept doing things to increase the running time of the program and was able to finish up that larger case.

The key improvement I made this weekend was formulating the problem as an integer program and solving the LP relaxation (with a little bit of branch and bound). This seems like such an obvious way to approach the problem to my mind today, but I received so much resistance from my co-authors when I initially proposed this as a way of tackling this problem that I just gave in. But after they were unable to move past a few different enumeration techniques, this idea came back into my head with positive results.

I'm trying to wrap my head around this whole "research" concept. I know that I fell in love with it in undergrad, but each problem seems to possess its own uniqueness. I remember when I was taking proof based math classes, I would systematically attack homework problems:
- What am I trying to prove?
- What are the key terms in the assumption?
- What are the key terms in the conclusion?
- Are there any theorems that relate these key terms?

Normally by the time I've gotten to the fourth question, I can get to a proof. Its not so simple in research. First of all, I don't generally know what I'm trying to prove, except that its unproven. Sometimes, its helpful to make a claim like "I'm trying to prove a matrix is totally unimodular", but if I'm unable then it doesn't mean that the matirxis NOT totally unimodular, it means that I haven't proven that it is totally unimodular.

Second, I'm normally asking a question that can be formulated in many different ways. So the idea of key terms depends a whole lot on which format I choose to work with. Sometimes it doesn't matter, but other times after the research has been completed I'll see why I couldn't have come to the same result with a different format. But things are always easier after the fact.

And third, unlike homework where we're working out of a standard text book, research is just building on whats already been done. There may be a theorem that was discovered last month (and hence not in any text book) that helps me to proceed with a given format. But I won't know this by simply looking at a text book. So another part of it is looking back and forth at research journals and publications. Or as was the case with this weekend, I may need to look at other areas. This may provide me with a different way of looking at the problem that makes the question being asked more concrete.

But I do think that the way I learned to break down homework problems can be an effective way of doing research, but its a much more iterative process (hence the "re" in research).