Skip to main content
edited body
Source Link
Kevin Dalmeijer
  • 6.4k
  • 1
  • 18
  • 49

Relaxing the equality constraint to an inequality constraint (when the problem allows!) should generally speed up convergence, and I have seen this many times in practice.

You can understand this as follows: column generation in the primal is equivalent ofto adding cuts in the dual. Bad duals (very suboptimal for the full problem) lead to dual cuts (primal columns) that cut off points in the dual space that we do not really care about in the first place.

For your specific problem, you have information that the solver does not have: you actually do not require an equality constraint! This translates to: the dual multipliers are non-negative/non-positive instead of unbounded. Adding this information (relaxing the constraint in the primal) then leads to an easier problem in the dual, and faster convergence.

Relaxing the equality constraint to an inequality constraint (when the problem allows!) should generally speed up convergence, and I have seen this many times in practice.

You can understand this as follows: column generation in the primal is equivalent of adding cuts in the dual. Bad duals (very suboptimal for the full problem) lead to dual cuts (primal columns) that cut off points in the dual space that we do not really care about in the first place.

For your specific problem, you have information that the solver does not have: you actually do not require an equality constraint! This translates to: the dual multipliers are non-negative/non-positive instead of unbounded. Adding this information (relaxing the constraint in the primal) then leads to an easier problem in the dual, and faster convergence.

Relaxing the equality constraint to an inequality constraint (when the problem allows!) should generally speed up convergence, and I have seen this many times in practice.

You can understand this as follows: column generation in the primal is equivalent to adding cuts in the dual. Bad duals (very suboptimal for the full problem) lead to dual cuts (primal columns) that cut off points in the dual space that we do not really care about in the first place.

For your specific problem, you have information that the solver does not have: you actually do not require an equality constraint! This translates to: the dual multipliers are non-negative/non-positive instead of unbounded. Adding this information (relaxing the constraint in the primal) then leads to an easier problem in the dual, and faster convergence.

Source Link
Kevin Dalmeijer
  • 6.4k
  • 1
  • 18
  • 49

Relaxing the equality constraint to an inequality constraint (when the problem allows!) should generally speed up convergence, and I have seen this many times in practice.

You can understand this as follows: column generation in the primal is equivalent of adding cuts in the dual. Bad duals (very suboptimal for the full problem) lead to dual cuts (primal columns) that cut off points in the dual space that we do not really care about in the first place.

For your specific problem, you have information that the solver does not have: you actually do not require an equality constraint! This translates to: the dual multipliers are non-negative/non-positive instead of unbounded. Adding this information (relaxing the constraint in the primal) then leads to an easier problem in the dual, and faster convergence.