I'm a bit surprised but not shocked. If CPLEX applies a heuristic that targets improving the objective value (which is constant), it might not be very helpful. Also, as you noted, results likely will vary from one problem instance to the next.
It's possible (but far from assured) that you could get a feasible solution faster by relaxing some but not all constraints into the objective (minimize the total violation) while keeping some other constraints. On the plus side, CPLEX might find a feasible solution to the unrelaxed constraints faster. On the minus side, CPLEX would likely have to branch for a while to get the objective to optimal (zero).
------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
------------------------------
Original Message:
Sent: Mon July 24, 2023 05:30 PM
From: Marcus Garvie
Subject: Parameters for finding a single feasible solution of an MIP problem
I followed this advice. After downloading CPLEX v22.1 I got the following runtimes to find a feasible solution for the indicated parameter settings:
set emphasis mip 0 ---> 8.3 mins
set emphasis mip 1 ---> 8.91 mins
set emphasis mip 4 ---> 8.92 mins
set emphasis mip 5 ---> 11.51 mins
All pretty similar. Interesting that the default setting (the first) which balances optimality and feasibility was the best.
------------------------------
Marcus Garvie
Original Message:
Sent: Mon July 24, 2023 01:22 PM
From: Paul Rubin
Subject: Parameters for finding a single feasible solution of an MIP problem
If you omit the objective function (which is equivalent to minimizing 0), then the first feasible solution will be declared optimal and CPLEX will stop. So with no objective function the solution limit parameter has no effect.
You might want to try setting the emphasis switch to 4 (finding "hidden" feasible solutions) to see if it helps. Also, if you can upgrade to a newer version of CPLEX, there is now a mip emphasis setting of 5, which someone described to me as "heuristics on steroids".
Sorry, no idea about Gurobi.
------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
Original Message:
Sent: Mon July 24, 2023 10:32 AM
From: Marcus Garvie
Subject: Parameters for finding a single feasible solution of an MIP problem
Hi everyone,
I am solving pure binary linear programming problems in CPLEX v12.10, with no objective function. I understand the importance of tuning, which hasn't been very helpful in my problems (as my problems differ vastly in size and good parameters for one problem are not necessarily good parameters for another). I am interested in finding a single feasible solution as fast as possible. Are the following command line parameters (and commands) appropriate/sensible for all cases?
> set emphasis mip 1
> set mip limits solutions 1
> read [filename].lp
> opt
Is there any point using the 2nd parameter setting for the number of solutions when I've already set the 1st parameter setting? Another question I have is whether the equivalent Gurobi (v 10.0) parameter settings above are 'MIPFocus = 1' and 'SolutionLimit = 1' ?
Thank you,
Marcus garvie.
------------------------------
Marcus Garvie
------------------------------