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's gravatar image

VictorSMiller
28315
accept rate: 0%

edited 27 Jan '13, 11:01

Michael%20Trick's gravatar image

Michael Trick ♦♦
3.9k926

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

I recommend to read Feasibility Pump papers by Fischetti.

link

answered 28 Jan '13, 13:19

Farvaresh's gravatar image

Farvaresh
411
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

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.

link

answered 28 Jan '13, 06:36

Bo%20Jensen's gravatar image

Bo Jensen ♦
4.7k1715
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 ♦
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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:

×40
×2

Asked: 27 Jan '13, 10:29

Seen: 437 times

Last updated: 30 Jan '13, 03:53

OR-Exchange! Your site for questions, answers, and announcements about operations research.