Heuristic solution for continuous and binary variables
AnsweredGood day.
I am solving optimization problem by Gurobi.
In the first case, I defined variables as binary using the following command:
x = [model.addVar(vtype=gp.GRB.BINARY, name="x%s" % i) for i in range(n)]
with the following Output:
Set parameter NonConvex to value 2 Gurobi Optimizer version 10.0.2 build v10.0.2rc0 (mac64[arm]) CPU model: Apple M1 Thread count: 8 physical cores, 8 logical processors, using up to 8 threads Optimize a model with 0 rows, 100 columns and 0 nonzeros Model fingerprint: 0xdf68950c Model has 298 quadratic objective terms Variable types: 0 continuous, 100 integer (100 binary) Coefficient statistics: Matrix range [0e+00, 0e+00] Objective range [1e+00, 5e+00] QObjective range [2e+00, 4e+00] Bounds range [1e+00, 1e+00] RHS range [0e+00, 0e+00] Found heuristic solution: objective 222.0000000 Found heuristic solution: objective 227.0000000 Found heuristic solution: objective 288.0000000 Presolve removed 0 rows and 15 columns Presolve time: 0.05s Presolved: 249 rows, 334 columns, 747 nonzeros Variable types: 0 continuous, 334 integer (334 binary) Root relaxation: objective 3.000000e+02, 130 iterations, 0.00 seconds (0.00 work units) Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time 0 0 300.00000 0 85 288.00000 300.00000 4.17% - 0s 0 0 293.50000 0 101 288.00000 293.50000 1.91% - 0s 0 0 289.83333 0 152 288.00000 289.83333 0.64% - 0s 0 0 289.63235 0 176 288.00000 289.63235 0.57% - 0s 0 0 289.63235 0 172 288.00000 289.63235 0.57% - 0s 0 0 289.63235 0 59 288.00000 289.63235 0.57% - 0s 0 0 cutoff 0 288.00000 288.00000 0.00% - 0s Cutting planes: Implied bound: 2 Clique: 13 MIR: 3 Zero half: 32 RLT: 7 Explored 1 nodes (918 simplex iterations) in 0.13 seconds (0.08 work units) Thread count was 8 (of 8 available processors) Solution count 3: 288 227 222 Optimal solution found (tolerance 1.00e-04) Best objective 2.880000000000e+02, best bound 2.880000000000e+02, gap 0.0000%
In the second case, I solved the same problem, but defined the variables as continuous to relax the problem using the following code:
x = [model.addVar(vtype=gp.GRB.CONTINUOUS, name="x%s" % i, lb=0, ub=1) for i in range(n)]
because I heard that the optimizers can solve the relaxed version more efficiently than the discrete one. I get the following output:
Set parameter NonConvex to value 2 Gurobi Optimizer version 10.0.2 build v10.0.2rc0 (mac64[arm]) CPU model: Apple M1 Thread count: 8 physical cores, 8 logical processors, using up to 8 threads Optimize a model with 0 rows, 100 columns and 0 nonzeros Model fingerprint: 0x295b0a6f Model has 298 quadratic objective terms Coefficient statistics: Matrix range [0e+00, 0e+00] Objective range [1e+00, 5e+00] QObjective range [2e+00, 4e+00] Bounds range [1e+00, 1e+00] RHS range [0e+00, 0e+00] Presolve removed 0 rows and 1 columns Continuous model is non-convex -- solving as a MIP Found heuristic solution: objective 222.0000000 Found heuristic solution: objective 227.0000000 Presolve removed 0 rows and 15 columns Presolve time: 0.05s Presolved: 249 rows, 334 columns, 747 nonzeros Found heuristic solution: objective 240.0000000 Variable types: 0 continuous, 334 integer (334 binary) Found heuristic solution: objective 252.0000000 Root relaxation: objective 3.000000e+02, 130 iterations, 0.00 seconds (0.00 work units) Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time 0 0 300.00000 0 85 252.00000 300.00000 19.0% - 0s H 0 0 270.0000000 300.00000 11.1% - 0s 0 0 293.50000 0 97 270.00000 293.50000 8.70% - 0s H 0 0 278.0000000 293.50000 5.58% - 0s 0 0 291.00000 0 134 278.00000 291.00000 4.68% - 0s 0 0 291.00000 0 112 278.00000 291.00000 4.68% - 0s 0 2 291.00000 0 103 278.00000 291.00000 4.68% - 0s H 3 8 281.0000000 290.50000 3.38% 123 0s H 5 8 287.0000000 290.25000 1.13% 122 0s * 13 1 4 288.0000000 289.00000 0.35% 78.6 0s Cutting planes: Gomory: 4 MIR: 3 Zero half: 57 RLT: 6 Explored 21 nodes (1919 simplex iterations) in 0.15 seconds (0.10 work units) Thread count was 8 (of 8 available processors) Solution count 9: 288 287 281 ... 222 Optimal solution found (tolerance 1.00e-04) Best objective 2.880000000000e+02, best bound 2.880000000000e+02, gap 0.0000%
As expected, the both cases arrive at the same solution.
However, at the initial steps before starting MIP, in the first case, the heuristic finds better objective (288.00) compared to the second case (252.00). Would you please let me know if there is a difference in heuristic method for binary and continuous variables?
Moreover, may I get some information in output log of heuristic method's process?
Thanks a lot
-
Hi,
Some heuristics can only run on certain types of variables (due to the assumptions made) or are more effective for certain types of variables.
The same thing for other parts of the solution process such as presolve, you can see in the MIP case we are able to remove more variables (15 vs 1).There is no way of getting more information about the heuristics being run.
You can experiment with some heuristic-related parameters see the MIP section under parameters.In any case, It seems that there is not much difference in solving time.
Lastly, there is a convenient function to relax the problem: model.relax().
Cheers,
David0
Please sign in to leave a comment.
Comments
1 comment