search

atoptima / Coluna.jl

Branch-and-Price-and-Cut in Julia
https://www.atoptima.com
Other
192 stars 43 forks source link

ERROR: Unexpected variable state during column insertion. #747

Closed vulcanyao closed 1 year ago

vulcanyao commented 1 year ago

Describe the bug Cannot solve an MILP with Coluna!!

To Reproduce The error can be reproduced by running the code attached!!

Expected behavior What's reason for this kind of error?

Environment (please complete the following information):

Additional context Add any other context about the problem here. Bug.zip

guimarqu commented 1 year ago

Hi! Thanks for the report.

What version of Coluna are you using?

I think you should at least move to the latest version of Julia (1.6 LTS or 1.8). When I run the code in my machine, BlockDecomposition throws the following error:

ERROR: LoadError: BlockDecomposition.MasterVarInDwSp(r_itau[1,1], b5[1,1,1] : -5000 x[1,1,1] - r_itau[1,1] - r_itau[1,2] - r_itau[1,3] - r_itau[1,288] + eta1[1,1,1] ≥ -5000.0)

It means that master variable r_itau[1,1] is the subproblem constraint b5[1,1,1].

vulcanyao commented 1 year ago

Hi,

The version of Coluna is Coluna v0.4.2!!

guimarqu commented 1 year ago

You should update to the latest version. Some bugs have been fixed.

vulcanyao commented 1 year ago

Hi,

I received the following error when I attempted to update Coluna! Can you please help me out ?

(@v1.8) pkg> update Coluna ┌ Warning: could not download https://pkg.julialang.org/registries │ exception = HTTP/2 301 (Connection timeout after 30002 ms) while requesting https://pkg.julialang.org/registries └ @ Pkg.Registry /Users/administrator/.julia/scratchspaces/a66863c6-20e8-4ff4-8a62-49f30b1f605e/agent-cache/default-macmini-aarch64-1.0/build/default-macmini-aarch64-1-0/julialang/julia-release-1-dot-8/usr/share/julia/stdlib/v1.8/Pkg/src/Registry/Registry.jl:68 Updating registry at ~/.julia/registries/General No Changes to ~/.julia/environments/v1.8/Project.toml No Changes to ~/.julia/environments/v1.8/Manifest.toml

guimarqu commented 1 year ago

Hey, never happened to me. Looks like a network issue. Is it working today?

vulcanyao commented 1 year ago

Hi Guillaume,

Nope, I changed my IP address when updating Coluna. I have downloaded the source code of Coluna 0.5.1, could you please help me update Coluna via the source code?

Best, Canqi Yao PhD candidate Department of Mechanical and Energy Engineering Southern University of Science and Technology (SUSTech)

On Thu, Nov 24, 2022 at 5:50 PM Guillaume Marques @.***> wrote:

Hey, never happened to me. Looks like a network issue. Is it working today?

— Reply to this email directly, view it on GitHub https://github.com/atoptima/Coluna.jl/issues/747#issuecomment-1326206629, or unsubscribe https://github.com/notifications/unsubscribe-auth/AHHHNAOKH6X6MUDQIVASINDWJ426NANCNFSM6AAAAAASIWXXQM . You are receiving this because you authored the thread.Message ID: @.***>

guimarqu commented 1 year ago

Hi, your request to the julia pkg server timed out. I think it means you can't update any julia pkg. So even if you install Coluna from the source code (by doing ] dev Coluna), you'll have trouble downloading the dependencies. I think you should try with a brand new julia depot folder.

The way to do that is to create a folder that will be your new ~/.julia and change the JULIA_DEPOT_PATH environment variable. See https://docs.julialang.org/en/v1/manual/environment-variables/#JULIA_DEPOT_PATH. Then, try to download packages to see if it works.

vulcanyao commented 1 year ago

Hi, I have successfully update Julia (1.8.3) and Coluna (0.5.1) to the latest version, and revised the code attached. The Coluna still cannot obtain a feasible solution. [Uploading EVRP-BCP_latest.jl.zip…]()

guimarqu commented 1 year ago

Hi, looks like the upload did not work.

vulcanyao commented 1 year ago

Hi, Please find the file attached! Thanks .



On Nov 25, 2022, at 21:31, Guillaume Marques @.***> wrote:

Hi, looks like the uploading did not work.

— Reply to this email directly, view it on GitHub https://github.com/atoptima/Coluna.jl/issues/747#issuecomment-1327482581, or unsubscribe https://github.com/notifications/unsubscribe-auth/AHHHNAP6UFMHONQUQTZL3A3WKC5RJANCNFSM6AAAAAASIWXXQM. You are receiving this because you authored the thread.

guimarqu commented 1 year ago

Hi, it didn't work.

vulcanyao commented 1 year ago

Sorry, can you see the code ?

Bug_Coluna.zip

guimarqu commented 1 year ago

Thank you! There was a bug in column generation that is now fixed. A new release of Coluna will be available in a few hours.

The branch-cut-price algorithm may not find a feasible solution quickly (the default heuristic is the restricted master heuristic and it needs a set of columns that combined together forms a feasible solution).

It may help if

vulcanyao commented 1 year ago

Hi, I have updated Coluna to 0.5.2 and rerun the code attached. The following error occurs. I didn't find any file named 'assert_has_lp_dual_sol_failure.lp' in the root folder! Bug_Coluna.zip

Are there other bugs in Coluna?

ERROR: Something unexpected happened when retrieving the dual solution to the LP restricted master.

Termination status of the solver after optimizing the master (should be OPTIMAL) : UNCOVERED_TERMINATION_STATUS Number of dual solutions (should be at least 1) : 0

A file named assert_has_lp_dual_sol_failure.lp that contains the LP restricted master has been written. Please check the LP, try to optimize it with another solver, and try to get a dual solution. Open an issue with all these information at https://github.com/atoptima/Coluna.jl/issues.

guimarqu commented 1 year ago

This is not a bug but an unsupported case. The file should be in the folder from which you run julia.

guimarqu commented 1 year ago

Note that your solver does not return any dual solution to the master so it's impossible to compute subproblem reduced costs and continue column generation. So we need to run the master as it was at the time the error occurred and see why the solver does not return a dual solution.

vulcanyao commented 1 year ago

Hi, after I change the value of opt_tol from 1e-5 (the previous error, no dual solutions) to 1e-2, this error "ERROR: Unexpected variable state during column insertion" happened again. Is there something wrong with the relative optimality tolerance ?

conqueralg=Coluna.ColCutGenConquer(stages=[Coluna.Algorithm.ColumnGeneration(opt_rtol=1e-2)])

ERROR: Unexpected variable state during column insertion.

Column id: Coluna.MathProg.Variableu31994. Reduced cost of the column: -0.00011840196792833879. The column is in the master ? true. The column is active ? true.

If the column is in the master and active, it means a subproblem found a solution with negative (minimization) / positive (maximization) reduced cost that is already active in the master. This should not happen.

If you are using a pricing callback, make sure there is no bug in your code. If you are using a solver (e.g. GLPK, Gurobi...), check the reduced cost tolerance redcost_tol parameter of ColumnGeneration. If you find a bug in Coluna, please open an issue at https://github.com/atoptima/Coluna.jl/issues with an example that reproduces the bug.

guimarqu commented 1 year ago

Hi, you should increase redcost_tol.

guimarqu commented 1 year ago

Hi ! The "unexpected variable state during column insertion" is not an error anymore but just a warning because it does not block the column generation algorithm. You must update to 0.5.3.

vulcanyao commented 1 year ago

Hi according to what Coluna displayed, the following lp model is saved which cannot provide a dual solution for the column generation. I'm not familiar with the .lp file, could you please show me how to solve .lp file? I have searched the related info. with Google, and didn't find any useful tutorials. Thanks a lot!

assert_has_lp_dual_sol_failure.lp.zip

guimarqu commented 1 year ago

Hi,

Here is an example of how you can read a lp file and then optimize it (with Clp but you can obviously use any supported solver):

using JuMP, Clp
model = read_from_file("assert_has_lp_dual_sol_failure.lp")
set_optimizer(model, Clp.Optimizer)
optimize!(model)

Looks like there is an unsupported (very large) coefficient in the model. In constraint c_3659, variable MC_11285 has coefficient 2.0e19 which is too large for the solver. What's the value of your big M?

vulcanyao commented 1 year ago

Hi the value of big M is 500, should I reduce it?

guimarqu commented 1 year ago

No, it's good. Can one of your subproblem variables take a very large value?

I think you should first name all your constraints to find what constraint has this coefficient (the name is c so I think it's an unnamed constraint).

vulcanyao commented 1 year ago

Hi, while naming the constraint within the recursive loop, I found that I cannot put a single name for a set of constraints, e.g., the aaa is the forth line. Could you please help me fix this problem? Thanks a lot.

` for i in N if i in list_CS

Cons:SoC

        @constraint(EVRP, aaa[j in N, k in K], E[i, k] - e[i, j] * x[k, i, j] + r[i, k] - E[j, k] <= M * (1 - x[k, i, j]))
        @constraint(EVRP, [j in N, k in K], -M * (1 - x[k, i, j]) <= E[i, k] - e[i, j] * x[k, i, j] + r[i, k] - E[j, k])
        @constraint(EVRP, [j in N, k in 1:vehicle], tau_var[j] >= tau_var[i] + T[i, j] + r[i, k] * g[i] - M * (1 - x[k, i, j]))

        # Cons. enforced on two binary variables
        @constraint(EVRP, [tau = 2:Lambda_s], rs_itau[i, tau] >= r_itau[i, tau] - r_itau[i, tau-1])
        @constraint(EVRP, sum(rs_itau[i, tau] for tau in Lambda) <= 1)
        ss = 0
        ss0 = 0
        for tau in Lambda
            ss += rs_itau[i, tau] * tau
            ss0 += rs_itau[i, tau] * (tau + 1)
        end
        @constraint(EVRP, ss * Delta_tau <= tau_var[i])
        @constraint(EVRP, ss * Delta_tau <= tau_var[i])
        @constraint(EVRP, [k in 1:vehicle], r[i, k] * g[i] <= sum(r_itau[i, tau] for tau in Lambda) * Delta_tau)
        @constraint(EVRP, delta[i] == 0)
    else
        # Without CSs 
        # Cons:SoC
        @constraint(EVRP, [j in N, k in K], E[i, k] - e[i, j] * x[k, i, j] - E[j, k] <= M * (1 - x[k, i, j]))
        @constraint(EVRP, [j in N, k in K], -M * (1 - x[k, i, j]) <= E[i, k] - e[i, j] * x[k, i, j] - E[j, k])
        @constraint(EVRP, [j in N, k in 1:vehicle], tau_var[j] >= tau_var[i] + T[i, j] - M * (1 - x[k, i, j]))

        @constraint(EVRP, tau_var[i] <= t[i] + delta[i])
        @constraint(EVRP, t[i] <= tau_var[i])
        @constraint(EVRP, eta[i] >= epsilon[i] + u[i] * deltabar - zeta1[i] * chi - zeta2[i] * chi - M * (1 - sum(x[k, j, i] for j in N for k in K)))
        # KKT opt. condition
        @constraint(EVRP, -gamma * zeta1[i] + gamma * zeta2[i] - q[i] + u[i] - v[i] == 0)
        @constraint(EVRP, 1 - zeta1[i] - zeta2[i] == 0)
        @constraint(EVRP, 0 <= epsilon[i] + gamma * delta[i] - chi)
        @constraint(EVRP, epsilon[i] + gamma * delta[i] - chi <= M * omega1[i])
        @constraint(EVRP, zeta1[i] <= M * (1 - omega1[i]))
        @constraint(EVRP, 0 <= epsilon[i] - gamma * delta[i] + chi)
        @constraint(EVRP, zeta2[i] <= M * (1 - omega2[i]))
        @constraint(EVRP, epsilon[i] - gamma * delta[i] + chi <= M * (1 - omega2[i]))
        @constraint(EVRP, u[i] <= M * (1 - omega3[i]))
        @constraint(EVRP, deltabar - delta[i] <= M * (1 - omega3[i]))
        @constraint(EVRP, v[i] <= M * (1 - omega4[i]))
        @constraint(EVRP, delta[i] <= M * (1 - omega4[i]))
    end
end`
guimarqu commented 1 year ago

Indeed, constraint names should be unique.

You can remove the loop by defining the sets of indices before:

in_CS = I ∩ list_CS
out_CS = setdiff(I, list_CS)

@constraint(aaa[i in in_CS, j in N, k in K], ...)
vulcanyao commented 1 year ago

Hi, thank you for this good technique, but there is still a same error.

Termination status of the solver after optimizing the master (should be OPTIMAL) : INFEASIBLE_OR_UNBOUNDED assert_has_lp_dual_sol_failure.lp.zip

The info. of this lp is shown as follows

Coefficient statistics: Matrix range [1e-02, 6e+03] Objective range [1e+00, 1e+03] Bounds range [5e-01, 1e+00] RHS range [1e-02, 5e+02] Presolve removed 1480 rows and 8671 columns Presolve time: 0.03s Presolved: 1926 rows, 1900 columns, 69910 nonzeros

Concurrent LP optimizer: primal simplex, dual simplex, and barrier Showing barrier log only...

Ordering time: 0.01s

Barrier performed 0 iterations in 0.05 seconds (0.11 work units) Barrier solve interrupted - model solved by another algorithm

Solved with dual simplex

Solved in 117 iterations and 0.06 seconds (0.11 work units) Infeasible or unbounded model

guimarqu commented 1 year ago

Hey, so what's wrong with your master formulation? Do you now why it is infeasible or unbounded?

vulcanyao commented 1 year ago

Hi, the code finally worked after I revise an inequality symbol in the original code, but the convergence rate is much slow for large-sized instances. Are there any methods to accelerate the BPC. Thanks a lot!

guimarqu commented 1 year ago

Hi, great news :) Did you try stabilization in column generation? You should set the value to 1 for automatic stabilization.

https://github.com/atoptima/Coluna.jl/blob/e4908fc91eb5249fa9d9764a6f884bea7ba2e5ce/src/Algorithm/colgen.jl#L83

guimarqu commented 1 year ago

Otherwise, you may rework your reformulation, introduce branching variables, separate valid inequalities and try what the literature suggests for your type of problem.

vulcanyao commented 1 year ago

Hi thanks a lot, I will try the stabilization method as you suggested. Have a nice Friday!