Solver failure on small problem

[metanoid]

Trying to construct an MWE for #82 , I ran into this. A small problem, which I imagine ConstraintSolver should be able to enumerate and solve in it's entirety (smaller than sudoku) seems to take very long and consume all my RAM.

To reproduce:

using JuMP
using ConstraintSolver
using Cbc # for testing

model = Model()

# Variables
@variable(model, 0 <= inclusion[h = 1:3] <= 1, Int);
@variable(model, 0 <= allocations[h = 1:3, a = 1:3] <= 1, Int);
@variable(model, 0 <= days[h = 1:3, a = 1:3] <= 5, Int);

# Constraints
@constraint(model, must_include[h = 1:3],
    sum(allocations[h,a] for a in 1:3) <= inclusion[h]
);
# at least n
@constraint(model, min_hospitals,
    sum(inclusion[h] for h in 1:3) >= 3
);
# every h must be allocated at most one a
@constraint(model, must_visit[h = 1:3],
    sum(allocations[h,a] for a in 1:3) <= 1
);
# every allocated h must have fewer than 5 days of visits per week
@constraint(model, max_visits[h = 1:3],
    sum(days[h, a] for a in 1:3) <= 5 * inclusion[h]
);

benefit = @expression(model,
    sum(days[h,a] * 5
    for h in 1:3, a in 1:3));

@objective(model, Max, benefit);
set_optimizer(model, with_optimizer(Cbc.Optimizer))
optimize!(model) # working
set_optimizer(model, with_optimizer(ConstraintSolver.Optimizer))
optimize!(model) # consumes all RAM without finishing

Status:

pkg> status
    Status `C:\Users\username\Documents\Projects\projectname\Project.toml`
  [336ed68f] CSV v0.5.23
  [9961bab8] Cbc v0.6.6
  [e0e52ebd] ConstraintSolver v0.1.0 #master (https://github.com/Wikunia/ConstraintSolver.jl)
  [a93c6f00] DataFrames v0.20.0
  [4076af6c] JuMP v0.20.1
  [fdbf4ff8] XLSX v0.5.8

[Wikunia]

Thanks for issue. This is really a v0.0.1 version of the project. Especially <= constraints can be very slow at the moment. I'll have a look into this.

[Wikunia]

The problem with this problem is that each constraint individually doesn't constrain the objective much but the 3 day constraints combined limit it easily to 75. Have to check good methods to define better bounds. I'm self taught in this so this project is mostly trial and error. I appreciate that you tried the project and created this issue. Stay tuned 😊

[metanoid]

Thanks for looking into it. I suspect part of the problem is that I've specified the issue in MILP style, not Constraint Programming style. I'll look into refactoring the problem definition to see if that reduces the solve time.

[Wikunia]

i.e it is easy for the current solver if you add the constraint:

@constraint(model, max_visits_total,
    sum(days[h, a] for a in 1:3, h in 1:3) <= 5 * sum(inclusion)
)

Which just combines the days constraint such that the whole objective is on the left.

[metanoid]

i.e it is easy for the current solver if you add the constraint:

@constraint(model, max_visits_total,
    sum(days[h, a] for a in 1:3, h in 1:3) <= 5 * sum(inclusion)
)

Which just combines the days constraint such that the whole objective is on the left.

I don't think that's equivalent. Consider trying to allocate the following value to the days structure:

[9, 0, 0;
 0, 2, 0;
 0, 0, 2
]

For sum(inclusion) = 3, the original formulation would reject this allocation, but your new formulation would not reject it, since the sum across all days is less than 3*5 = 15.

On Mon, Feb 17, 2020 at 3:52 PM Ole Kröger notifications@github.com wrote:

i.e it is easy for the current solver if you add the constraint:

@constraint(model, max_visits_total, sum(days[h, a] for a in 1:3, h in 1:3) <= 5 * sum(inclusion) )

Which just combines the days constraint such that the whole objective is on the left.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/Wikunia/ConstraintSolver.jl/issues/83?email_source=notifications&email_token=ABZOZLA6VQJ6I7JV56YM4K3RDKJBHA5CNFSM4KVINUW2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEL6POFI#issuecomment-587003669, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABZOZLAXHD2FXN4OW3YQAQ3RDKJBHANCNFSM4KVINUWQ .

[Wikunia]

Sorry for the confusion. I didn't mean replacing the three constraints by one. I mean adding an additional constraint.

[Wikunia]

That PR is a possible fix for this. Will do some more testing before it gets merged.