# Objectives for IP feasibility

 7 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 283●1●5 accept rate: 0% Michael Trick ♦♦ 3.9k●9●26 1 I'm not a constraint proramming expert, but why don't you use CP if you just need a feasible integer solution? (28 Jan '13, 08:00) Ehsan ♦ Is there any particular problem you are dealing with? Maybe you can trigger some ideas in us... :-) (30 Jan '13, 03:53) kr1zz

 4 I recommend to read Feasibility Pump papers by Fischetti. answered 28 Jan '13, 13:19 Farvaresh 41●1 accept rate: 0% 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
 3 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 ♦ 4.7k●1●7●15 accept rate: 14% 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 ♦
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: