no failure on infeasible integer problem

[c-cube]

On an infeasible problem, with max debug level, the solver prints
"PROBLEM HAS NO INTEGER FEASIBLE SOLUTION"
but the API just proceeds without raising any exception and returns a "solution" which isn't one.

[smimram]

Could you please provide a minimal test-case? I have not been using this library for ages, sorry.

[c-cube]

to repro:

$ dune utop src/

then #use "reg.ml";;

where reg.ml contains:

let decl_bool solver v name =
  Glpk.set_col_name solver v name;
  Glpk.set_col_kind solver v Glpk.Integer_var;
  Glpk.set_col_bounds solver v Glpk.Double_bounded_var 0. 1.;
  ()

let () =
  let solver = Glpk.new_problem() in
  Glpk.set_message_level solver 3;
  Glpk.set_class solver Glpk.Mixed_integer_prog;
  Glpk.use_presolver solver true;
  Glpk.set_simplex_time_limit solver 10.; (* timeout *)
  Glpk.set_direction solver Glpk.Maximize;
  (* declare vars *)
  let y = 0 in
  let p = 1 in
  let slack = 2 in
  let f = 3 in
  Glpk.add_columns solver 4;
  Glpk.set_col_name solver y "y";
  Glpk.set_col_kind solver y Glpk.Integer_var;
  Glpk.set_col_bounds solver y Glpk.Free_var neg_infinity infinity;
  decl_bool solver p "p";
  decl_bool solver f "f";
  decl_bool solver slack "slack";
  (* rows *)
  Glpk.add_rows solver 6;
  begin
    let matrix = ref [] in
    let add_coeff i j c = matrix := ((i,j),c) :: !matrix in
    (* r0: y = 6 *)
    add_coeff 0 y 1.;
    Glpk.set_row_bounds solver 0 Glpk.Fixed_var 6. 6.;
    (* r1: p = 0 *)
    add_coeff 1 p 1.;
    Glpk.set_row_bounds solver 1 Glpk.Fixed_var 0. 0.;
    (* r2: slack + f = 1 *)
    add_coeff 2 slack 1.;
    add_coeff 2 f 1.;
    Glpk.set_row_bounds solver 2 Glpk.Fixed_var 1. 1.;
    (* r3: - 1e+30 slack + y <= -6 *)
    add_coeff 3 slack (-1e30);
    add_coeff 3 y 1.;
    Glpk.set_row_bounds solver 3 Glpk.Upper_bounded_var neg_infinity (-6.);
    (* r4: - 1e+30 f - y <= 6 *)
    add_coeff 4 f (-1e30);
    add_coeff 4 y (-1.);
    Glpk.set_row_bounds solver 4 Glpk.Upper_bounded_var neg_infinity 6.;
    (* r5: - f - p <= -1 *)
    add_coeff 5 f (-1.);
    add_coeff 5 p (-1.);
    Glpk.set_row_bounds solver 5 Glpk.Upper_bounded_var neg_infinity (-1.);
    (* now push sparse matrix *)
    Glpk.load_sparse_matrix solver (Array.of_list @@ List.rev !matrix);
  end;
  (* objective *)
  Glpk.set_obj_coef solver y 1.; (* maximize y *)
  Glpk.warm_up solver;
  try
    Format.printf ">> simplex@.";
    Glpk.simplex solver;
    Format.printf ">> branch and bound@.";
    Glpk.branch_and_bound_opt solver;
    Format.printf "success@.";
    ()
  with
  | Glpk.No_convergence
  | Glpk.No_dual_feasible_solution
  | Glpk.No_primal_feasible_solution ->
    Format.printf "failed@."

it prints a bunch of info, then:

PROBLEM HAS NO INTEGER FEASIBLE SOLUTION
success

instead of "failed"

[smimram]

This gave me the motivation to start updating to the new glpk API. In the branch #6, you can do the following:

let decl_bool solver v name =
  Glpk.set_col_name solver v name;
  Glpk.set_col_kind solver v Glpk.Integer_var;
  Glpk.set_col_bounds solver v Glpk.Double_bounded_var 0. 1.;
  ()

let () =
  let solver = Glpk.new_problem () in
  (* Glpk.set_message_level solver 3; *)
  (* Glpk.set_class solver Glpk.Mixed_integer_prog; *)
  (* Glpk.use_presolver solver true; *)
  (* Glpk.set_simplex_time_limit solver 10.; (\* timeout *\) *)
  Glpk.set_direction solver Glpk.Maximize;
  (* declare vars *)
  let y = 0 in
  let p = 1 in
  let slack = 2 in
  let f = 3 in
  Glpk.add_columns solver 4;
  Glpk.set_col_name solver y "y";
  Glpk.set_col_kind solver y Glpk.Integer_var;
  Glpk.set_col_bounds solver y Glpk.Free_var neg_infinity infinity;
  decl_bool solver p "p";
  decl_bool solver f "f";
  decl_bool solver slack "slack";
  (* rows *)
  Glpk.add_rows solver 6;
  begin
    let matrix = ref [] in
    let add_coeff i j c = matrix := ((i,j),c) :: !matrix in
    (* r0: y = 6 *)
    add_coeff 0 y 1.;
    Glpk.set_row_bounds solver 0 Glpk.Fixed_var 6. 6.;
    (* r1: p = 0 *)
    add_coeff 1 p 1.;
    Glpk.set_row_bounds solver 1 Glpk.Fixed_var 0. 0.;
    (* r2: slack + f = 1 *)
    add_coeff 2 slack 1.;
    add_coeff 2 f 1.;
    Glpk.set_row_bounds solver 2 Glpk.Fixed_var 1. 1.;
    (* r3: - 1e+30 slack + y <= -6 *)
    add_coeff 3 slack (-1e30);
    add_coeff 3 y 1.;
    Glpk.set_row_bounds solver 3 Glpk.Upper_bounded_var neg_infinity (-6.);
    (* r4: - 1e+30 f - y <= 6 *)
    add_coeff 4 f (-1e30);
    add_coeff 4 y (-1.);
    Glpk.set_row_bounds solver 4 Glpk.Upper_bounded_var neg_infinity 6.;
    (* r5: - f - p <= -1 *)
    add_coeff 5 f (-1.);
    add_coeff 5 p (-1.);
    Glpk.set_row_bounds solver 5 Glpk.Upper_bounded_var neg_infinity (-1.);
    (* now push sparse matrix *)
    Glpk.load_sparse_matrix solver (Array.of_list @@ List.rev !matrix);
  end;
  (* objective *)
  Glpk.set_obj_coef solver y 1.; (* maximize y *)
  Glpk.warm_up solver;
  (* try *)
    Format.printf ">> simplex@.";
    Glpk.simplex solver;
    Format.printf ">> branch and bound@.";
    Glpk.branch_and_cut solver;
    (
      match Glpk.mip_status solver with
      | Glpk.No_feasible -> Format.printf "no feasible solution@.";
      | _ -> Format.printf "success@.";
    );
    ()
  (* with *)
  (* | Glpk.No_convergence *)
  (* | Glpk.No_dual_feasible_solution *)
  (* | Glpk.No_primal_feasible_solution -> *)
    (* Format.printf "failed@." *)

I did not have time yet to restore all features. Could you please test and tell me which ones are missing for you?

[c-cube]

Nice! This does indeed print "no feasible solution". I need the features to extract the (optimal) goal, as well as a full model for the variables, after optimizing a mixed integer/bool/real problem as above. (by "bool" I just mean integers variables bounded by [0, 1]).

[smimram]

You now have

val mip_obj_val : lp -> float

val mip_row_val : lp -> int -> float

val mip_col_val : lp -> int -> float

If you need something else, please tell me the name of the C glpk function.

[c-cube]

I'm going to try and adapt my code to this branch, but I'm not finding set_message_level anymore; it's convenient in tests imho

edit: also set_simplex_time_limit

[smimram]

Great. message level and time limit are now added as parameters of simplex and branch_and_cut (they are not global parameters anymore).

[c-cube]

I've got a segfault, I'll try to reproduce in another issue…

edit: the issue might be when extracting values or deallocating the solver, it's not related to this.

[smimram]

Arg :( Please provide a test case or at least a gdb stacktrace.