5
$\begingroup$

I got an MPS file and a best know solution value for that problem. I do not know whether the MPS file contains a minimization or an maximization problem.

How do i programmatically create a copy of that MPS file and add a constraint saying that only solutions strictly better then best known solution value should be considered feasible?

$\endgroup$
4
  • $\begingroup$ how do you define strictly better if you do not know if you are minimizing or maximizing? $\endgroup$
    – Kuifje
    Sep 20 at 11:26
  • $\begingroup$ Well the automation can look at the file. I just do not know a priori without looking at the file whether it is an minimization or maximization problem. $\endgroup$ Sep 20 at 12:02
  • 1
    $\begingroup$ You might want to bear in mind that optimizing $c'x$ and also adding a constraint of the form $c'x \ge b$ or $c'x \le b$ has been known to slow down the solution process (by creating dual degeneracy, if memory serves). There are questions and answers related to this somewhere on OR SE. You might be better off feeding the cutoff to your solver as a parameter, if the solver has such a parameter. (CPLEX, for one, does.) $\endgroup$
    – prubin
    Sep 20 at 15:24
  • $\begingroup$ Not for the constraint based solver i am working with, but the caveat for simplex based solvers is appreciated. $\endgroup$ Sep 20 at 16:02

1 Answer 1

5
$\begingroup$

You can use PuLP to read the MPS file, add the constraint, and export the new problem as an MPS file :

  • The syntax is var, prob = LpProblem.fromMPS("prob.mps") to read the MPS file.

  • Then use prob += to add your constraint.

  • And finally prob.writeMPS("new_prob.mps") to export the new MPS
    file.

If you are minimizing, the constraint would be something like prob+= obj <= best_sol - tol, where obj is the objective function which you have to fetch, best_sol is your best known solution, and tol is your tolerance.

EDIT

Once you have loaded the MPS file as a pulp.LpProblem object, it is straightforward to know wether it is a minimization problem or not with the attribute pulp.LpProblem.sense which returns 1 for minimization, -1 for maximization.

More generally, with pulp.LpProblem.to_dict, you can access all attributes of the problem, including the objective coefficients.

$\endgroup$
5
  • $\begingroup$ How should the program choose tol? All my problems are ILP. So there is an unambiguously correct answer. $\endgroup$ Sep 20 at 12:04
  • $\begingroup$ I think tol is really up to you. Is best_sol-0.00000000001 considered better than best_sol? $\endgroup$
    – Kuifje
    Sep 20 at 12:43
  • $\begingroup$ best_sol-0.00000000001 might be wrong though. $\endgroup$ Sep 20 at 14:03
  • $\begingroup$ This answer leaves unaddressed how i find out the direction of the problem using PULP, how i extract the objective coefficients for the constraint and how i enforce strictly better without cutting of potential answers. $\endgroup$ Sep 20 at 21:44
  • $\begingroup$ I have added some tips on how to access the direction of the problem as well as the objective coefficients. I do not understand the part about cutting potential answers, could you elaborate ? $\endgroup$
    – Kuifje
    Sep 21 at 8:03

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.