Adding constraint improves objective.

[karlsb1871]

Hi there,

I am currently using this solver for a scheduling problem, which I have modelled as a routing problem, where my objective is to maximise. As with routing problems, I have a set of nodes to visit and have created a "Virtual Node", for where the route start and ends. I have added constraints to ensure that at the start of the route, we must go from the virtual node to an uplink node, something specific to my problem. I have done this by introducing two sets of constraints.

  for (k, s) in K.iter().enumerate() {
        let (mut vars, mut coefs) = get_empty_vars_and_coefs();
        for i in (0..N.len())
            .into_iter()
            .filter(|&n| uplink_indicies.contains(&n))
        {
            for p in 0..N[i].get_vtw(s).unwrap().len() {
                vars.push(x[k][virtual_indicies[0]][0][i][p].clone());
                coefs.push(1.0);
            }
        }
        model.add_cons(vars, &coefs, 1.0, 1.0, "start_virtual_to_uplink");
    }

    for (k, s) in K.iter().enumerate() {
        let (mut vars, mut coefs) = get_empty_vars_and_coefs();
        for i in (0..N.len())
            .into_iter()
            .filter(|&n| !uplink_indicies.contains(&n))
        {
            for p in 0..N[i].get_vtw(s).unwrap().len() {
                vars.push(x[k][virtual_indicies[0]][0][i][p].clone());
                coefs.push(1.0);
            }
        }
        model.add_cons(vars, &coefs, f64::MIN, 0.0, "start_virtual_to_uplink");
    }

x is my variable where x[k][i][p][j][q] = 1 if vehicle k goes from node i, in window p to node j, in window q. In the first set of constraints, I define that each vehicle must travel from the virtual node to an uplink node, and in the second constraints, I say they cannot go from the virtual node to any other type of node. Along with these constraints I have the other necessary constraints for a routing problem.

However, I am finding that when I have both of these constraints, I am getting an objective value of 4, whereas when I drop the first set of constraints, the solver is returning the optimal objective as 0. This has been bugging me because how can removing a set of constraints make the objective worse?

I understand that without having all of the code this isn't much to go on, however I was wondering if anyone has come across this before or if there is something potentially wrong with my formulation?

Thanks Karl

[mmghannam]

Hi Karl! SCIP by default has a mimization objective sense. In case you don't have it yet, maybe you need to set it to maximize?

model.set_obj_sense(ObjSense::Maximize);

[karlsb1871]

Hi @mmghannam,

Thanks for the quick reply. Yeah I have set the sense this way, think I got this from an example somewhere

let mut model = Model::new().hide_output().include_default_plugins().create_prob("test").set_obj_sense(ObjSense::Maximize);

[mmghannam]

hmmm, that's strange. If you can't share the code, could you maybe attach logs for both runs, with and without constraints?

PS. don't forget to remove .hide_output() from the code above.

[karlsb1871]

with_constraints.txt without_constraint.txt

Hi, here are the logs for both with and without constraints

[mmghannam]

This doesn't look too good (in the version with constraints) but also explains this behavior. SCIP returned an infeasible solution. You should probably file an issue on the SCIP repo, but an lp file would be helpful here. You can get the file after creating the model using the write("PATH", "lp") method.

[linear] <s_less_F_if_y>: <s_0_7_0_0>[C] (+4.54747351e-13) -1.79769313e+308<y_0_7_0_0>[B] (-6.8790666e-16) <= 0;
;
violation: right hand side is violated by 1e+20

[karlsb1871]

@mmghannam I have just raised an issue on the SCIP repo with the lp file as suggested. Thanks for your help with this, ill comment here if any solution is found. 👍🏻

[mmghannam]

Cool, thanks @karlsb1871! I'll close this for now, feel free to reopen if it turns out the problem is related to russcip.

[karlsb1871]

@mmghannam just to update you. I raised this issue with the SCIp repo and as you suggested the error was coming from a big M constraint, where I set the coefficient to the upper bound of a variable, which I had set to f64::MAX because there was not real upper bound on the variable. Just thought I would update you in case an issue like this arises in the future 👍🏻