Suppose that I have a polytope \(P = \{ x \in \mathbb{R}^n  A x \le b \}\), and am interested in finding any integer feasible solution in \(P \cap \mathbb{Z}^n\) (for example in a boolean satisfiability problem). Since I'm only interested in feasibility, any objective function should work (say even one that is identically 0), but it seems clear that some objectives might be much better in practice, in that it might allow nodes in a branch and bound to be fathomed earlier. In addition one could "fatten" \(P\) as \(P' = \{ (x,z) \in \mathbb{R}^{m+n}  A x \le b + z, z \ge 0\}\) and take as an objective function \(c^T z\) where \(c \ge 0\) and not identically 0 (for example the all 1's vector). Has there been any work, most likely heuristic, about choosing good objectives for finding integer feasible solutions? asked 27 Jan '13, 10:29 VictorSMiller Michael Trick ♦♦ 
I recommend to read Feasibility Pump papers by Fischetti. answered 28 Jan '13, 13:19 Farvaresh Thanks, I've read a number of them, and even tried out the feasibility pump. In the problems that I've looked at it appears to be very hard for the FP to find an integer solution in the original problem.
(28 Jan '13, 14:31)
VictorSMiller

You can also come up with situations were it's worse to add an artificial objective. In fact some commercial codes have just the opposite heuristic i.e remove the objective and hope for the best. Unless you have some structure knowledge about the model to construct a reasonable objective, then I think you might end up in MIP randomness. answered 28 Jan '13, 06:36 Bo Jensen ♦ BTW : Please note for such a test to make sense, the B&C should be terminated in both cases when the first feasible solution is found. Otherwise you spend valuable time on confirming optimality, which for the zero objective might be harder.
(28 Jan '13, 06:40)
Bo Jensen ♦

I'm not a constraint proramming expert, but why don't you use CP if you just need a feasible integer solution?
Is there any particular problem you are dealing with? Maybe you can trigger some ideas in us... :)