(binary) solution not satisfying constraint

Specific Domains Optimization (Mathematical)
1

Hello

I’m solving a small problem with Gurobi, which is given by println(cover)=

Min slack[1] + slack[2] + slack[7] + slack[9]
Subject to
 y[135] + y[136] + y[152] + y[158] + y[159] + y[200] + y[474] + y[550] + y[551] = 2.0
 y[135] + y[136] + y[152] + y[158] + y[159] + y[200] + y[474] + y[550] + y[551] + slack[1] ≥ 1.0
 y[135] + y[136] + y[158] + y[474] + y[550] + y[551] + slack[2] ≥ 1.0
 y[135] + y[136] + y[152] + y[158] + y[159] + y[200] + slack[7] ≥ 1.0
 y[135] + y[136] + y[152] + y[200] + y[474] + slack[9] ≥ 1.0
 slack[1] ≥ 0.0
 slack[2] ≥ 0.0
 slack[7] ≥ 0.0
 slack[9] ≥ 0.0
 y[135] binary
 y[136] binary
 y[152] binary
 y[158] binary
 y[159] binary
 y[200] binary
 y[474] binary
 y[550] binary
 y[551] binary

The returned solution is println(value.(y))=

1-dimensional DenseAxisArray{Float64,1,...} with index sets:
    Dimension 1, Any[134, 146, 158, 550, 551]
And data, a 5-element Array{Float64,1}:
 0.0
 0.0
 0.0
 0.0
 1.0

which does not satisfy the first constraint. How is that possible? (I can unfortunately not easily share the code).

Best,

Michael.

2

What are the values of raw_status(model), termination_status(model) and primal_status(model)?

3 
raw_status(model): Model was solved to optimality (subject to tolerances), and an optimal solution is available.
termination_status(model): OPTIMAL
primal_status(model): FEASIBLE_POINT

By the way, the solution has been found heuristically, as can be seen in the output:

Optimize a model with 5 rows, 9 columns and 20 nonzeros
Variable types: 4 continuous, 5 integer (5 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [0e+00, 0e+00]
  RHS range        [1e+00, 2e+00]
Found heuristic solution: objective 0.0000000

Explored 0 nodes (0 simplex iterations) in 0.00 seconds
Thread count was 1 (of 8 available processors)

Solution count 1: 0 

Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
4

Without code, it’s hard to offer advice.

It looks like there is a bug in your code because the printed values have 5 elements, but it looks like your model has many more. Moreover, y[134] appears in the solution, but not in the model.

1 Like
5

Oops, indeed, I pasted the wrong model. Here comes the correct one:

Min slack[1] + slack[2] + slack[7] + slack[9]
Subject to
 y[134] + y[146] + y[158] + y[550] + y[551] = 2.0
 y[134] + y[146] + y[158] + y[551] + slack[1] ≥ 1.0
 y[134] + y[551] + slack[2] ≥ 1.0
 y[134] + y[146] + y[158] + slack[7] ≥ 1.0
 y[134] + y[146] + slack[9] ≥ 1.0
 slack[1] ≥ 0.0
 slack[2] ≥ 0.0
 slack[7] ≥ 0.0
 slack[9] ≥ 0.0
 y[134] binary
 y[146] binary
 y[158] binary
 y[550] binary
 y[551] binary

I’ll see if I can create a small instance of the bug.