Redundant and non-redundant constraints

Specific Domains Optimization (Mathematical)
1

Hello! I need to solve a LP model with CPLEX and find which of constraints are non redundant. After solving, it gives me the following message:

Tried aggregator 1 time.
LP Presolve eliminated 22 rows and 0 columns.
Reduced LP has 10 rows, 3 columns, and 26 nonzeros.
Presolve time = 0.00 sec. (0.01 ticks)
Initializing dual steep norms . . .

How can i find which constraints have eliminated?

2

This requires you to use the CPLEX C API: IBM Documentation

Doing so is non-trivial, I strongly encourage you to consider if you need to do this. Here is some code to get you started:

using JuMP, CPLEX
model = direct_model(CPLEX.Optimizer())
# ... build model ...
optimize!(model)
cpx = backend(model)
redlp_p = Ref{Ptr{Cvoid}}()
CPXgetredlp(cpx.env, cpx.lp, redlp_p)
lp = redlp_p[]  # Use this pointer with CPX functions

Depending on what you mean by “non redundant,” there are better ways of doing this. For example, you could check the slack of each constraint to see if it is binding, or you could look for constraints with a dual of 0.0.

1 Like
3

I think you meant Ref{Ptr{Cvoid}}()? :sweat_smile:

4 Likes
4

Are you looking for the presolved model, or for a set of non-redundant constraints from the original LP?

Couple of remarks (which may or may not be relevant based on the above question):

  1. In general, the presolved model may still contain some redundant constraints.

  2. Presolve may eliminate constraints that are non redundant. For instance, consider the following LP:

    min   x1 + x2 + x3
s.t.  x1 + x2 + x3 = 3
           x2 + x3 = 2
                x3 = 1

    The 3 constraints are non-redundant, but presolve will eliminate all of them (they form a triangular system).

  3. CPLEX also makes use of dual reductions. These are transformations that may remove some feasible solution, but keeps all optimal ones. Again, these may eliminate non-redundant constraints.

Finally, if you want a set of non-redundant constraints that are active at the optimum, you are looking for a basis, which you should be able to query from CPLEX without needing to go through the presolved model.

2 Likes
5

Thank you all for your advices!
@odow i follow your code but now i have this message. Have you any ideas what’ s wrong with it?png1

6

Have you any ideas what’ s wrong with it?

You probably need to update to the latest version of CPLEX.jl.

Check

julia> import Pkg; Pkg.status("CPLEX")
Status `/private/tmp/jump/Project.toml`
  [a076750e] CPLEX v0.7.3

and if it’s not 0.7.3, run Pkg.update().