Add access to GLPK parameters in lp-glpk backend

[adelaett]

This pull request aims to give access to GLPK parameters from the lp-glpk backend. Most parameters were already accessible from the lp-glpk-js backend but not from lp-glpk.

I needed the mip_gap or tm_lim for my use case, where the optimality of the solution is not that important.

To pass the options, I added many optional parameters to the solve function. This seemed to be more idiomatic for OCaml use than the object defined in the glpk-js backend. Moreover, it should not break existing code too much (I removed direct access to Simplex.solve and Milp.solve from the mli in order to factorize the code).

I voluntarily omitted some parameters, like callbacks, as it is less obvious how to add them. Here is the full list of omitted parameters: @param msg_lev Message level (default: Msg.ALL) @param br_tech Branch technique (default: Iocp.Br.DTH) @param bt_tech Backtrack technique (default: Iocp.Bt.BLB) @param cb_func Callback function (default: C.null) @param cb_info Callback information (default: C.null) @param pp_tech Preprocessing technique (default: Iocp.Pp.ALL)

[adelaett]

This PR still misses the correct parameters for the first step of the solving. Moreover, some additional information is required for the return values.

[ktahar]

Thank you for the patch. This is what I should have done on initial development... I agree with your approach of adding many optional parameters (object stuffs in glpk-js are due to JS convention).

I believe that applicable parameters depends on the problem class (and consequently, solvers used).

• Simplex.solve: only simplex solver is used for LP (without integer vars). Then we need to use Smcp (simplex optimizer control parameter) only to set parameters.
• Milp.solve: both simplex and integer optimizers are used for MILP. Then we need to use both Smcp and Iocp (integer optimizer control parameter).

-- A little confusing, but this is due to GLPK's API.

Can I wait for your update?

[adelaett]

Indeed, I will update the PR with those changes.

[adelaett]

Hi, here is an update on this PR.

I added the return values and parameters for both simplex and intopt algorithms.

I added a test for the simplex algorithm for when the problem is only feasible (after 0 iterations of the simplex). I did not add tests for every combination of the parameters.

I also modified the knapsack problem to build a hard instance for MILP testing. I found a bug in glpk this way, where the solution given by the solver is incorrect (breaking constraints). For $n=18$, the capacity constraint is broken. I believe this is because of floating point arithmetic. I did not test the same instance on Gurobi.

let () =
  let n = 18 in
  let task =
    { items=
        List.init n (fun i ->
            {profit= 2. ** float_of_int i; weight= 2. ** float_of_int i} )
    ; capacity=
        (2. ** float_of_int (n - 1)) -. 1. (* Just under sum of all weights *)
    }
  in
  (* Build and solve *)
  let result = solve task in
  (* Print selected items *)
  Format.printf "Task: %a\n" pp_task task ;
  Format.printf "Solution: %a\n" (pp_instance Format.pp_print_float) result

INTEGER OPTIMAL SOLUTION FOUND
Task: { Test_milp_parameters.items =
        [{ Test_milp_parameters.profit = 1.; weight = 1. };
          { Test_milp_parameters.profit = 2.; weight = 2. };
          { Test_milp_parameters.profit = 4.; weight = 4. };
          { Test_milp_parameters.profit = 8.; weight = 8. };
          { Test_milp_parameters.profit = 16.; weight = 16. };
          { Test_milp_parameters.profit = 32.; weight = 32. };
          { Test_milp_parameters.profit = 64.; weight = 64. };
          { Test_milp_parameters.profit = 128.; weight = 128. };
          { Test_milp_parameters.profit = 256.; weight = 256. };
          { Test_milp_parameters.profit = 512.; weight = 512. };
          { Test_milp_parameters.profit = 1024.; weight = 1024. };
          { Test_milp_parameters.profit = 2048.; weight = 2048. };
          { Test_milp_parameters.profit = 4096.; weight = 4096. };
          { Test_milp_parameters.profit = 8192.; weight = 8192. };
          { Test_milp_parameters.profit = 16384.; weight = 16384. };
          { Test_milp_parameters.profit = 32768.; weight = 32768. };
          { Test_milp_parameters.profit = 65536.; weight = 65536. };
          { Test_milp_parameters.profit = 131072.; weight = 131072. }];
        capacity = 131071. }
Solution: { Test_milp_parameters.x =
                                         [|0.; 0.; 0.; 0.; 0.; 0.; 0.; 0.;
                                           0.; 0.; 0.; 0.; 0.; 0.; 0.; 0.;
                                           0.; 1.|];
                                         space_left = -1.;
                                         total_amount = 131072. }

I will extract one from my own instances, as the mip_gap functionality is not tested inside the glpk software.

[adelaett]

Hi, I added a test for the mip_gap parameter. The PR should be ready for review. Tell me if you want me to add some testing for other parameters.

[ktahar]

Thanks a lot for completing this. I found that the broken constraint of the instance (knapsack n=18) can be fixed by setting tol_int to 1e-6 (or smaller). I think something like rounding error was happening; because the default tol_int is 1e-5, the weight of lightest item (1) was too insignificant for capacity (131071>1e5). To resolve this kind of issue, I added tol_int and tol_gap params.

[adelaett]

Thanks for investigating. I was afraid to use tol_int and tol_gap params since it indicated "modify only if you know what you do" in the documentation. It's still pretty strange for me to not have any error messages and just a bad solution returned by the solver. I hope other solvers have checks implemented!