2
$\begingroup$

I want to solve a relaxed version of a MILP; I am using docplex.mp. I found LinearRelaxer in docplex.mp.relax_linear , however I keep getting this error message:

  • model model1: found 1 un-relaxable elements, main cause is logical (e.g. x_25_10_0 -> [b_10_0 >= b_25_0+0.601])

  • reason: logical: 1772 unrelaxables

    def solve(model, **kwargs):
  lp = LinearRelaxer.make_relaxed_model(model)
  lp.print_information()
  sol = lp.solve(log_output=True)

  if sol is not None:
     print(sol.solve_details.best_bound)
     print("solution for a cost 
       {}".format(model.objective_value))
     model.print_information()
     print_solution(model, sol)
     sol.display()
     return model.objective_value
 else:
     print("* mdl is infeasible")
     return None
Improve this question
$\endgroup$
1
  • $\begingroup$ one possible way would be changing the logic expression to its mathematical equivalent. For example, the logic expression you mentioned might be turned out to, $LHS \geq RHS - M(1-x25100)$ if the variable $x$ is binary. Would you try that? $\endgroup$
    – A.Omidi
    Commented Jun 29, 2022 at 14:05

2 Answers 2

Reset to default
3
$\begingroup$

Disclaimer: I do not use Docplex (nor Python). That said, the following is in the documentation for LinearRelaxer:

Some constructs are not relaxable, for example, piecewise-linear expressions, SOS sets, logical constraints… When a model contains at least one of these non-relaxable constructs, a message is printed and this method returns None.

Are you using logical implication constraints in your model? The error message suggests there are a bunch of them (1772). It appears that if you want to use the relaxer you will need to replace them with big-M constraints or something similar.

Improve this answer
$\endgroup$
11
  • $\begingroup$ Yes, I replace them with big M constraints but this leads me to another error: Dual infeasible due to empty column '_max976'. $\endgroup$
    – Nada.S
    Commented Jun 29, 2022 at 11:55
  • $\begingroup$ That suggests a formulation error in the big M version. Do you have a variable named "_max976" that appears in the objective function but not in any constraints? $\endgroup$
    – prubin ♦
    Commented Jun 29, 2022 at 15:08
  • $\begingroup$ Yes, I had in the objective function a function of type max{0, x} where x est de type (x = var-value) and the variable var appears in constraints. What I understood that it considers it as new variable and name it _max976. So I replace the max{0,x} by a new variable y >=0 and I added a constraint y>=x. The model executed with no error. but the value of the dual simplex is 0 which is so far from the optimal solution. $\endgroup$
    – Nada.S
    Commented Jun 29, 2022 at 16:48
  • $\begingroup$ Try constructing a solution that you believe should be feasible with objective value better than 0, then substitute it into the constraints and see if you can find a violated constraint. If so, either your solution is not really feasible or that constraint is incorrectly stated. Besides doing this with pencil and paper, another possibility is to fix every variable to the value in your proposed solution by setting lower bound = upper bound = value, then solve the model. Assuming CPLEX says the model is infeasible, check which constraints it thinks are violated. $\endgroup$
    – prubin ♦
    Commented Jun 29, 2022 at 17:55
  • $\begingroup$ I have already found optimal solutions for the same model for small instances and there is no constraint that was violated. I want to have solutions for large instances which requires a lot of time to compare with the solutions of a heuristic. that's why I thought of comparing them with the solutions of a linear relaxation. but even for the small instances (10 instances) that were solved with a gap of 0.01%, it gives the value 0 $\endgroup$
    – Nada.S
    Commented Jun 29, 2022 at 22:12
1
$\begingroup$

As a simple example to work around what you want the following template would be useful:

from docplex.mp.model import Model
from docplex.mp.relax_linear import LinearRelaxer

# The originial model name
mdl = Model(name='test')

# Declare variables
e.g. x, y

# The optimization model
mdl.minimize(mdl.sum(...));
mdl.add_constraints(..., 'con1');
mdl.add_constraints(..., "con2");

# Solving the model
mdl.print_information()
m = mdl.solve(log_output=True)

# Solving the model again in the relaxed form 
lp = LinearRelaxer.make_relaxed_model(mdl)
lp.print_information()
s_lp = lp.solve(log_output=True)
s_lp.display()
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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