5

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?

worldsmithhelper
  • 4,007
  • 6
  • 21
  • how do you define strictly better if you do not know if you are minimizing or maximizing? – Kuifje Sep 20 '22 at 11:26
  • 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. – worldsmithhelper Sep 20 '22 at 12:02
  • 1
    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.) – prubin Sep 20 '22 at 15:24
  • Not for the constraint based solver i am working with, but the caveat for simplex based solvers is appreciated. – worldsmithhelper Sep 20 '22 at 16:02

1 Answers1

5

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.

Kuifje
  • 13,324
  • 1
  • 23
  • 56
  • How should the program choose tol? All my problems are ILP. So there is an unambiguously correct answer. – worldsmithhelper Sep 20 '22 at 12:04
  • I think tol is really up to you. Is best_sol-0.00000000001 considered better than best_sol? – Kuifje Sep 20 '22 at 12:43
  • best_sol-0.00000000001 might be wrong though. – worldsmithhelper Sep 20 '22 at 14:03
  • 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. – worldsmithhelper Sep 20 '22 at 21:44
  • 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 ? – Kuifje Sep 21 '22 at 08:03