search

coin-or / Dip

DIP is a decomposition-based solver framework for mixed integer linear programs.
https://github.com/coin-or/Dip/wiki
Eclipse Public License 1.0
17 stars 7 forks source link

Problem with accepting infeasible integer solution in phase 1 #135

Closed spoorendonk closed 3 years ago

spoorendonk commented 4 years ago

When restoring feasibility in phase 1 sometimes a solution is integer although the master objective is > 0, ie., the problem is still infeasible. Maybe this is mostly true if the convexity constraints are allowed to be <= 1?

https://github.com/coin-or/Dip/blob/67faa5ae29d338166daba3bfa453b3a87bb6d5bd/Dip/src/DecompAlgo.cpp#L1701-L1713

a possible fix is to check the phase and objective before accepting integer solutions?

Something like

  if (phase == PHASE_PRICE1 &&
      decompAlgo->getMasterObjValue() > DecompEpsilon) {
    // infeasible, do not add solution
  }
tkralphs commented 3 years ago

I'm not sure I quite understand the issue. Before accepting a solution, it is checked both for IP feasibility and for APP feasibility. If it satisfies both of these, then it should really be feasible. I guess I need to be able to replicate the issue to see what's going on. Can you clarify further?

spoorendonk commented 3 years ago

I think the problem is that there are still artificial variables in the solution. Hence my suggestion to check the master objective for a 0 value before accepting solutions.

So the case is, that the problem is integer feasible but some of the constraints are satisfied by artificial variables. I guess you can check that in APP feasibility but as a user you (I at least) would have expected that to be handled.

Does that make sense?

tkralphs commented 3 years ago

It makes sense, but I don't see yet how a solution can be accepted when there are non-zero artificials. The feasibility checked does specifically check for artificials being non-zero and returns infeasible is there are any here. https://github.com/coin-or/Dip/blob/67faa5ae29d338166daba3bfa453b3a87bb6d5bd/Dip/src/DecompAlgo.cpp#L6629-L6631 So the only way you could have decompAlgo->getMasterObjValue() > DecompEpsilon is (I guess) if multiple artificials all had value just below DecompEpsilon, but together they add up to something above DecompEpsilon. Could you give a specific example where this happens? What are the values of the variables?

spoorendonk commented 3 years ago

My mistake. Closing