Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Check how to deal with equalities when computing Benders cuts right-hand side #934

Closed
najaverzat opened this issue Jun 14, 2023 · 1 comment · Fixed by #937
Closed

Check how to deal with equalities when computing Benders cuts right-hand side #934

najaverzat opened this issue Jun 14, 2023 · 1 comment · Fixed by #937
Assignees

Comments

@najaverzat
Copy link
Contributor

In Benders _compute_cut_rhs_contrib we separate the contribution of classic linear inequalities from the contribution of the bounding constraints. The bounding contraints costs are given by dual_sol and their contribution depends on the sense of the bounding (UPPER, LOWER and LOWER_AND_UPPER).

In the case of LOWER_AND_UPPER (i.e. equality) we have to check how to compute the good contribution. For the moment, given bounded variable constr: value <= x <= value, the contribution equals value*cost(constr).

@guimarqu
Copy link
Contributor

Equality is treated as two constraints: 'x <= value' & 'x >= value', and only one of them will be active. Consequently, the case LOWER_AND_UPPER should not happen. I think we should remove it from the ActiveBound.

Remove from the enum:

@enum ActiveBound LOWER UPPER LOWER_AND_UPPER

Remove from the condition in Benders:

if active_bound == MathProg.LOWER || active_bound == MathProg.LOWER_AND_UPPER

Remove these 3 lines because they are not correct (see counterexample below but it can break some unit tests):

push!(varids, var_id)
push!(varvals, sense * cost)
push!(activebounds, LOWER_AND_UPPER)

Remove from the test:

Coluna.MathProg.VarId[vids["y1"], vids["x1"], vids["y2"], vids["x2"]], Float64[10.0, 5.0, 2.0, 3.0], Coluna.MathProg.ActiveBound[MathProg.LOWER, MathProg.UPPER, MathProg.UPPER, MathProg.LOWER_AND_UPPER], ## x2 fixed to 1.0

counterexample:

MinSense + 1.0 y3 + 2.0 y1 + 1.0 y2 + 1.0 art1 + 1.0 art2 + 1.0 art3  
sp_c1 : + 1.0 y3 + 1.0 y1 + 2.0 y2 + 1.0 art1  >= 2.0 (BendSpPureConstrConstraintu1 | true)
sp_c2 : + 5.0 y1 - 1.0 y2 + 1.0 art2  >= 5.0 (BendSpTechnologicalConstrConstraintu2 | true)
sp_c3 : - 2.0 y3 + 1.0 art3  >= 3.0 (BendSpTechnologicalConstrConstraintu3 | true)
0.0 <= y3 <= 2.0 (Continuous | BendSpSepVar | true)
1.0 <= y1 <= 1.0 (Continuous | BendSpSepVar | true)
0.0 <= y2 <= 2.0 (Continuous | BendSpSepVar | true)
0.0 <= art1 <= Inf (Continuous | BendSpSecondStageArtVar | true)
0.0 <= art2 <= Inf (Continuous | BendSpSecondStageArtVar | true)
0.0 <= art3 <= Inf (Continuous | BendSpSecondStageArtVar | true)

Solutions:

primal = Primal solution
| y1 = 1.0
| y2 = 0.5
| art2 = 0.5
| art3 = 3.0
└ value = 6.00 

dual = Dual solution
| sp_c1 = 1.0
| sp_c2 = 1.0
| sp_c3 = 1.0
| y1 = -4.0 (UPPER)
| y3 = 2.0 (LOWER)
└ value = 6.00 

@najaverzat najaverzat linked a pull request Jun 15, 2023 that will close this issue
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants