2
$\begingroup$

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).

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

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ This assumes the primal is feasible? $\endgroup$
    – Sune
    Oct 6 at 20:17
  • 1
    $\begingroup$ @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. $\endgroup$
    – prubin
    Oct 7 at 23:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.