Hello, 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?) |

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.
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 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
Austin Buchanan |

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.