Best way to solve a optimization problem with no objective function?

I have a MILP but fixed the objective function, so at each iteration is constant.Therefore, I solve a constraint satisfaction problem.

• Is there an algorithm to solve this kind of problem fast? I have a continuous variable, two inequalities and two equalities.

• And more importantly, can I get the dual of my constraints?

(I used AMPL so if someone knows a good solver or resource there it would be highly appreciated).

• How many integer variables do you have, are some of them binary? Oct 5 at 20:22
• @orpanter, if your problem is NOT too large, the Fourier-Motzkin elimination method might be interesting. Oct 6 at 5:55

MILP with a fixed objective function is hard as finding a feasible solution. Since this can still encode n-queens completion or SAT it is still in the same complexity class.

Depending on your problem some MILP heuristic might find a solution. Constraint satisfaction programming might be fast but it could be that encoding it into sat or pseudo boolean form for the integer part only then try to find a solution for the continuous variable in a tiny linear program and if no such solution can be found learn a new constraint on the integers using Farkas' Lemma could work. A penalty method could also work well as could evolutionary algorithms. There is no approach that beats all others.

Nothing prevents you from getting a dual of the linear relaxation of MILP problem. In how far that relaxation is strong depends on your problem but a sufficient number of (Gomory/Lift-and-project) cuts can cut of all non-integer vertices of the polytope. See Duality of Mixed Integer Programs.

The question is a bit confusing, in that you say you have a MILP, mention a continuous variable but nothing about integer variables, and then ask about the dual solution (which exists for a continuous model but not for an integer model, at least not in the usual sense of "dual").

Assuming that we are talking about a linear program with the objective function fixed at 0, the dual problem will automatically have the all-zeroes solution be optimal. (It may not be the unique optimum, but it will definitely be optimal.) So the dual solution is trivial to get but likely useless.

Here's a quick proof of my assertion. Assume that the primal problem is an LP of the form \begin{align*} \min_{x}0\\ \textrm{s.t. }Ax & \ge b\\ x & \ge0, \end{align*}noting that equality constraints can always be rewritten as pairs of inequalities. The dual problem is\begin{align*} \max_{y}b^{\prime}y\\ \textrm{s.t. }A^{\prime}y & \le0\\ y & \ge0. \end{align*} Clearly $$y=0$$ is feasible in the dual, with objective value 0, which equals the optimal value of the primal. So by weak duality, $$y=0$$ is optimal in the dual.

• This assumes the primal is feasible?
– Sune
Oct 6 at 20:17
• @Sune Good catch. Yes, I assume feasibility. If the primal is infeasible, the dual is either infeasible or unbounded, and we can rule out infeasible because we know $y=0$ is feasible in the dual. So infeasible primal means unbounded dual, in which case there is no dual solution. Oct 7 at 23:52