a given linear program can be reduced from a optimizing problem to a problem where you only need a valid solution. (and which then has the optimal solution to the optimizing problem; using the dual program)

Is this also possible for an integer programs? (Maybe if you use that integer programms can be written as quadratic programms?)

asked 17 Dec '14, 10:09

zBirdy's gravatar image

accept rate: 20%

edited 20 Dec '14, 01:56

fbahr's gravatar image

fbahr ♦

If the definition of "valid solution" included integrality, it would not do you any good even if it were true (which I'm pretty sure it is not). Also, to be technical, you need the conversion to a satisfaction problem to be linear (or at least polynomial) time.

(19 Dec '14, 16:13) Paul Rubin ♦♦

As Paul Rubin hints at, the question is ill-posed since there are no restrictions on the reduction. The reduction could just solve the integer program (IP) in exponential time and output the/an answer.

Most of what I say below relies on the assumption that coNP and NP are different. This is widely believed by complexity theorists.

If you restrict things to polynomial-time reductions, then you cannot expect to reduce IP optimization to IP feasibility in "one go" like you can for LP. BUT, you can solve IP optimization via a sequence of IP feasibility problems, but this is probably not what you're looking for.

Suppose you can reduce IP optimization to IP feasibility the same way that LP optimization reduces to LP feasibility. Namely, suppose there is a polytime reduction that converts your optimization IP Q1 to a feasibility IP Q2, such that any feasible solution to Q2 can be converted (in polytime) to an optimal solution to Q1. Then, consider the question Q3: "is it true that every feasible solution to Q1 has objective value worse than k?" Question Q3 is coNP-complete. And, our reduction shows that Q3 also belongs to NP (the witness is a feasible solution to Q2 that converts back to a solution of Q1 with objective worse than k). But a coNP-complete problem cannot belong to NP, unless coNP=NP. This shows that no such polytime reduction can exist, unless coNP=NP.

On the other hand, you can solve the optimization IP via polynomially many calls to an oracle that solves IP feasibility. The basic idea is to add a constraint that says "the objective function value must be at least as good as k," and perform binary search on k to find the optimal value.


answered 24 Dec '14, 17:50

Austin%20Buchanan's gravatar image

Austin Buchanan
accept rate: 42%

edited 24 Dec '14, 20:46

Your answer
toggle preview

Follow this question

By Email:

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



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



Asked: 17 Dec '14, 10:09

Seen: 811 times

Last updated: 24 Dec '14, 20:46

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