search

google / or-tools

Google's Operations Research tools:
https://developers.google.com/optimization/
Apache License 2.0
11.25k stars 2.13k forks source link

Model infeasible with linearization_level=2 and cmake, works with bazel #3690

Closed mwahbi closed 1 year ago

mwahbi commented 1 year ago

What version of OR-Tools and what language are you using? Version: 9.5.2498 (from main) Language: Python 3.10

Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi) CP-SAT

What operating system (Linux, Windows, ...) and version? Windows

What did you do? Steps to reproduce the behavior:

from google.protobuf import text_format
from ortools.sat.python import cp_model

def main():
    run = 0
    conflicts = {"OPTIMAL", "INFEASIBLE"}
    model = cp_model.CpModel()
    text_format.Parse(open("bug_proto.txt").read(), model.Proto())
    while run < 10000 and conflicts:
        solver = cp_model.CpSolver()
        # solver.parameters.log_search_progress = True
        solver.parameters.num_search_workers = 8
        status = solver.Solve(model)
        status = solver.StatusName(status)
        objective = solver.ObjectiveValue()
        print(f"{run=:04d} {status=} {objective=}")
        conflicts.discard(status)
        run += 1

if __name__ == '__main__':
    main()

What did you expect to see I am expecting status='OPTIMAL'

What did you see instead? With solver.parameters.num_search_workers = 1 the status is always 'OPTIMAL'. With solver.parameters.num_search_workers = 8 the status is sometimes 'INFEASIBLE' and sometimes 'OPTIMAL'.

Make sure you include information that can help us debug (full error message, model Proto). Proto

Anything else we should know about your project / environment Build from main using cmake

lperron commented 1 year ago

I ran it 20 times on main. It always return OPTIMAL.

mwahbi commented 1 year ago

Bonjour @lperron,

Bellow is the output with the log activated for me. Could this be a problem of OS? 

Starting CP-SAT solver v9.5.2498
Parameters: log_search_progress: true num_search_workers: 8

Initial optimization model '': (model_fingerprint: 0xb23c71c9861dccf2)
Search strategy: on 27 variables, CHOOSE_FIRST, SELECT_MAX_VALUE
Search strategy: on 27 variables, CHOOSE_FIRST, SELECT_MAX_VALUE
Search strategy: on 0 variables, CHOOSE_FIRST, SELECT_MIN_VALUE
Search strategy: on 0 variables, CHOOSE_FIRST, SELECT_MIN_VALUE
Search strategy: on 27 variables, CHOOSE_FIRST, SELECT_MIN_VALUE
#Variables: 498 (#ints:54 in floating point objective)
  - 117 Booleans in [0,1]
  - 137 different domains in [-1076,371797] with a largest complexity of 539.
  - 2 constants in {0,1}
#kBoolAnd: 5 (#enforced: 5) (#literals: 17)
#kBoolOr: 6 (#enforced: 6) (#literals: 13)
#kInterval: 410
#kLinMax: 54 (#expressions: 108)
#kLinear1: 272 (#enforced: 272)
#kLinear2: 412 (#enforced: 10) (#complex_domain: 4)
#kLinear3: 84
#kLinearN: 1 (#terms: 5)
#kNoOverlap2D: 20 (#rectangles: 956, #quadratic_areas: 84)

Starting presolve at 0.00s
[Scaling] Floating point objective has 54 terms with magnitude in [0.0065, 0.048] average = 0.02725
[Scaling] Objective coefficient relative error: 0
[Scaling] Objective worst-case absolute error: 0
[Scaling] Objective scaling factor: 2000
[ExtractEncodingFromLinear] #potential_supersets=27 #potential_subsets=0 #at_most_one_encodings=0 #exactly_one_encodings=0 #unique_terms=0 #multiple_terms=0 #literals=0 time=2.57e-05s
[SAT presolve] num removable Booleans: 330 / 600
[SAT presolve] num trivial clauses: 0
[SAT presolve] [0s] clauses:13 literals:32 vars:12 one_side_vars:0 simple_definition:8 singleton_clauses:0
[SAT presolve] [0.0010009s] clauses:13 literals:32 vars:12 one_side_vars:0 simple_definition:8 singleton_clauses:0
[SAT presolve] [0.0013567s] clauses:8 literals:24 vars:10 one_side_vars:8 simple_definition:0 singleton_clauses:0
[Probing] deterministic_time: 7.541e-05 (limit: 1) wall_time: 0.0008742 (112/112)
[Probing]  - new binary clause: 8
[Probing] implications and bool_or (work_done=368).
[DetectDuplicateConstraints] #duplicates=44 #without_enforcements=0 time=0.0004187s
[DetectDominatedLinearConstraints] #relevant_constraints=0 #work_done=0 #num_inclusions=0 #num_redundant=0 time=1.22e-05s
[ProcessSetPPC] #relevant_constraints=1 #num_inclusions=0 work=0 time=3.03e-05s
[FindBigLinearOverlap] #blocks=0 #saved_nz=0 #linears=0 #work_done=0/1e+09 time=9.2e-06s
[MergeClauses] #num_collisions=0 #num_merges=0 #num_saved_literals=0 work=0/100000000 time=9.9e-06s
[Probing] deterministic_time: 1.456e-05 (limit: 1) wall_time: 0.0001913 (33/33)
[DetectDuplicateConstraints] #duplicates=0 #without_enforcements=0 time=0.0004673s
[DetectDominatedLinearConstraints] #relevant_constraints=0 #work_done=0 #num_inclusions=0 #num_redundant=0 time=1.04e-05s
[ProcessSetPPC] #relevant_constraints=0 #num_inclusions=0 work=0 time=1.49e-05s
[FindBigLinearOverlap] #blocks=0 #saved_nz=0 #linears=0 #work_done=0/1e+09 time=8e-06s
[MergeClauses] #num_collisions=0 #num_merges=0 #num_saved_literals=0 work=0/100000000 time=1.16e-05s
[ExpandObjective] #propagations=0 #entries=0 #tight_variables=0 #tight_constraints=0 #expands=0 #issues=0 time=9.97e-05s

Presolve summary:
  - 326 affine relations were detected.
  - rule 'TODO dual: only one blocking constraint?' was applied 378 times.
  - rule 'affine: new relation' was applied 326 times.
  - rule 'at_most_one: dominated singleton' was applied 75 times.
  - rule 'at_most_one: empty or all false' was applied 1 time.
  - rule 'bool_and: non-reified.' was applied 1 time.
  - rule 'bool_and: x => x' was applied 216 times.
  - rule 'bool_or: always true' was applied 5 times.
  - rule 'bool_or: only one literal' was applied 1 time.
  - rule 'deductions: 220 stored' was applied 1 time.
  - rule 'domination: in exactly one' was applied 3 times.
  - rule 'duplicate: removed constraint' was applied 44 times.
  - rule 'enforcement: false literal' was applied 4 times.
  - rule 'enforcement: true literal' was applied 5 times.
  - rule 'exactly_one: removed literals' was applied 26 times.
  - rule 'exactly_one: satisfied' was applied 1 time.
  - rule 'exactly_one: singleton' was applied 25 times.
  - rule 'exactly_one: size one' was applied 1 time.
  - rule 'int_abs: propagate domain from x to abs(x)' was applied 27 times.
  - rule 'int_abs: store abs(x) == y' was applied 7 times.
  - rule 'linear: always true' was applied 272 times.
  - rule 'linear: divide by GCD' was applied 88 times.
  - rule 'linear: empty' was applied 28 times.
  - rule 'linear: fixed or dup variables' was applied 384 times.
  - rule 'linear: positive clause' was applied 1 time.
  - rule 'linear: reduced variable domains' was applied 151 times.
  - rule 'linear: remapped using affine relations' was applied 1258 times.
  - rule 'linear: simplified rhs' was applied 139 times.
  - rule 'no_overlap_2d: split into disjoint components' was applied 16 times.
  - rule 'presolve: 144 unused variables removed.' was applied 1 time.
  - rule 'presolve: iteration' was applied 2 times.
  - rule 'variables with 2 values: create encoding literal' was applied 28 times.
  - rule 'variables with 2 values: new affine relation' was applied 28 times.
  - rule 'variables: canonicalize affine domain' was applied 74 times.
  - rule 'variables: detect fully reified value encoding' was applied 108 times.
  - rule 'variables: detect half reified value encoding' was applied 216 times.
  - rule 'variables: only used in encoding' was applied 27 times.

Presolved optimization model '': (model_fingerprint: 0xac89265d5f915552)
Search strategy: on 27 variables, CHOOSE_FIRST, SELECT_MAX_VALUE
Search strategy: on 27 variables, CHOOSE_FIRST, SELECT_MAX_VALUE
Search strategy: on 0 variables, CHOOSE_FIRST, SELECT_MIN_VALUE
Search strategy: on 0 variables, CHOOSE_FIRST, SELECT_MIN_VALUE
Search strategy: on 0 variables, CHOOSE_FIRST, SELECT_MIN_VALUE
#Variables: 106 (#ints:54 in objective)
  - 2 in [-5,104]
  - 4 in [-1,104]
  - 7 in [0][3][11][14][22][25][33][36][44][47][55 ... 212][220][223][231][234][242][245][253][256][264]
  - 20 in [0,14]
  - 20 in [0,28]
  - 6 in [0,48]
  - 1 in [0,79]
  - 6 in [0,104]
  - 20 in [0,538]
  - 20 in [0,1076]
#kInterval: 410
#kLinMax: 54 (#expressions: 108)
#kNoOverlap2D: 24 (#rectangles: 516)

Preloading model.
#Bound   0.10s best:inf   next:[0.728,316.48] initial_domain
#Model   0.10s var:106/106 constraints:488/488

Starting search at 0.10s with 8 workers.
6 full problem subsolvers: [default_lp, fixed, no_lp, max_lp, core, reduced_costs]
1 first solution subsolver: [random_0]
11 incomplete subsolvers: [feasibility_pump, rins_lns_default, rens_lns_default, rnd_var_lns_default, rnd_cst_lns_default, graph_var_lns_default, graph_cst_lns_default, scheduling_random_intervals_lns
_default, scheduling_random_precedences_lns_default, scheduling_time_window_lns_default, scheduling_resource_windows_lns_default]
3 helper subsolvers: [synchronization_agent, neighborhood_helper, update_gap_integral]
#Bound   0.13s best:inf   next:[1.928,316.48] default_lp
#Done    0.14s reduced_costs [hint]

Sub-solver search statistics:
  'default_lp':
    Search statistics:
      booleans: 6
      conflicts: 0
      branches: 6
      binary_propagations: 0
      integer_propagations: 65
      restarts: 0
    LP statistics:
      final dimension: 1 rows, 2 columns, 2 entries with magnitude in [1.000000e+00, 1.000000e+00]
      total number of simplex iterations: 1
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 5
      managed constraints: 2
      total cuts added: 0 (out of 0 calls)
    LP statistics:
      final dimension: 1 rows, 2 columns, 2 entries with magnitude in [1.000000e+00, 1.000000e+00]
      total number of simplex iterations: 1
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 5
      managed constraints: 2
      total cuts added: 0 (out of 0 calls)
    LP statistics:
      final dimension: 1 rows, 2 columns, 2 entries with magnitude in [1.000000e+00, 1.000000e+00]
      total number of simplex iterations: 1
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 5
      managed constraints: 2
      total cuts added: 0 (out of 0 calls)
    LP statistics:
      final dimension: 1 rows, 2 columns, 2 entries with magnitude in [1.000000e+00, 1.000000e+00]
      total number of simplex iterations: 1
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 5
      managed constraints: 2
      total cuts added: 0 (out of 0 calls)
    LP statistics:
      final dimension: 1 rows, 2 columns, 2 entries with magnitude in [1.000000e+00, 1.000000e+00]
      total number of simplex iterations: 1
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 5
      managed constraints: 2
      total cuts added: 0 (out of 0 calls)
    LP statistics:
      final dimension: 1 rows, 2 columns, 2 entries with magnitude in [1.000000e+00, 1.000000e+00]
      total number of simplex iterations: 1
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 5
      managed constraints: 2
      total cuts added: 0 (out of 0 calls)
    LP statistics:
      final dimension: 1 rows, 2 columns, 2 entries with magnitude in [1.000000e+00, 1.000000e+00]
      total number of simplex iterations: 1
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 5
      managed constraints: 2
      total cuts added: 0 (out of 0 calls)
    Skipping other LPs...
      - 52 total independent LPs.

  'fixed':
    Search statistics:
      booleans: 0
      conflicts: 0
      branches: 0
      binary_propagations: 0
      integer_propagations: 51
      restarts: 0
    LP statistics:
      final dimension: 1 rows, 2 columns, 2 entries with magnitude in [1.000000e+00, 1.000000e+00]
      total number of simplex iterations: 1
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 2
      managed constraints: 2
      total cuts added: 0 (out of 0 calls)
    LP statistics:
      final dimension: 1 rows, 2 columns, 2 entries with magnitude in [1.000000e+00, 1.000000e+00]
      total number of simplex iterations: 1
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 2
      managed constraints: 2
      total cuts added: 0 (out of 0 calls)
    LP statistics:
      final dimension: 1 rows, 2 columns, 2 entries with magnitude in [1.000000e+00, 1.000000e+00]
      total number of simplex iterations: 1
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 2
      managed constraints: 2
      total cuts added: 0 (out of 0 calls)
    LP statistics:
      final dimension: 1 rows, 2 columns, 2 entries with magnitude in [1.000000e+00, 1.000000e+00]
      total number of simplex iterations: 1
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 2
      managed constraints: 2
      total cuts added: 0 (out of 0 calls)
    LP statistics:
      final dimension: 1 rows, 2 columns, 2 entries with magnitude in [1.000000e+00, 1.000000e+00]
      total number of simplex iterations: 1
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 2
      managed constraints: 2
      total cuts added: 0 (out of 0 calls)
    LP statistics:
      final dimension: 1 rows, 2 columns, 2 entries with magnitude in [1.000000e+00, 1.000000e+00]
      total number of simplex iterations: 1
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 2
      managed constraints: 2
      total cuts added: 0 (out of 0 calls)
    LP statistics:
      final dimension: 1 rows, 2 columns, 2 entries with magnitude in [1.000000e+00, 1.000000e+00]
      total number of simplex iterations: 1
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 2
      managed constraints: 2
      total cuts added: 0 (out of 0 calls)
    Skipping other LPs...
      - 52 total independent LPs.

  'no_lp':
    Search statistics:
      booleans: 32
      conflicts: 0
      branches: 32
      binary_propagations: 0
      integer_propagations: 86
      restarts: 0

  'max_lp':
    Search statistics:
      booleans: 0
      conflicts: 0
      branches: 0
      binary_propagations: 0
      integer_propagations: 2
      restarts: 0
    LP statistics:
      final dimension: 127 rows, 106 columns, 284 entries with magnitude in [1.230915e-01, 1.000000e+00]
      total number of simplex iterations: 53
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 2
        - #DUAL_FEASIBLE: 1
      managed constraints: 140
      merged constraints: 6
      total cuts added: 20 (out of 78 calls)
        - 'NoOverlap2dXCompletionTimeMirror': 17
        - 'NoOverlap2dYCompletionTimeMirror': 3

  'core':
    Search statistics:
      booleans: 54
      conflicts: 0
      branches: 18
      binary_propagations: 22
      integer_propagations: 240
      restarts: 0

  'reduced_costs':
    Search statistics:
      booleans: 0
      conflicts: 1
      branches: 0
      binary_propagations: 0
      integer_propagations: 1
      restarts: 0
    LP statistics:
      final dimension: 62 rows, 106 columns, 187 entries with magnitude in [6.990763e-02, 1.000000e+00]
      total number of simplex iterations: 52
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 3
        - #DUAL_UNBOUNDED: 1
      managed constraints: 140
      merged constraints: 6
      total cuts added: 20 (out of 78 calls)
        - 'NoOverlap2dXCompletionTimeMirror': 17
        - 'NoOverlap2dYCompletionTimeMirror': 3

  'random_0':
    Search statistics:
      booleans: 0
      conflicts: 0
      branches: 0
      binary_propagations: 0
      integer_propagations: 52
      restarts: 0
    LP statistics:
      final dimension: 1 rows, 2 columns, 2 entries with magnitude in [1.000000e+00, 1.000000e+00]
      total number of simplex iterations: 1
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 3
        - #DUAL_FEASIBLE: 2
      managed constraints: 2
      total cuts added: 0 (out of 0 calls)
    LP statistics:
      final dimension: 1 rows, 2 columns, 2 entries with magnitude in [1.000000e+00, 1.000000e+00]
      total number of simplex iterations: 1
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 3
        - #DUAL_FEASIBLE: 2
      managed constraints: 2
      total cuts added: 0 (out of 0 calls)
    LP statistics:
      final dimension: 1 rows, 2 columns, 2 entries with magnitude in [1.000000e+00, 1.000000e+00]
      total number of simplex iterations: 1
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 3
        - #DUAL_FEASIBLE: 2
      managed constraints: 2
      total cuts added: 0 (out of 0 calls)
    LP statistics:
      final dimension: 1 rows, 2 columns, 2 entries with magnitude in [1.000000e+00, 1.000000e+00]
      total number of simplex iterations: 1
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 3
        - #DUAL_FEASIBLE: 2
      managed constraints: 2
      total cuts added: 0 (out of 0 calls)
    LP statistics:
      final dimension: 1 rows, 2 columns, 2 entries with magnitude in [1.000000e+00, 1.000000e+00]
      total number of simplex iterations: 1
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 3
        - #DUAL_FEASIBLE: 2
      managed constraints: 2
      total cuts added: 0 (out of 0 calls)
    LP statistics:
      final dimension: 1 rows, 2 columns, 2 entries with magnitude in [1.000000e+00, 1.000000e+00]
      total number of simplex iterations: 1
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 3
        - #DUAL_FEASIBLE: 2
      managed constraints: 2
      total cuts added: 0 (out of 0 calls)
    LP statistics:
      final dimension: 1 rows, 2 columns, 2 entries with magnitude in [1.000000e+00, 1.000000e+00]
      total number of simplex iterations: 1
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 3
        - #DUAL_FEASIBLE: 2
      managed constraints: 2
      total cuts added: 0 (out of 0 calls)
    Skipping other LPs...
      - 52 total independent LPs.

Objective bounds found per subsolver:
  'default_lp': 1
  'initial_domain': 1

CpSolverResponse summary:
status: INFEASIBLE
objective: NA
best_bound: NA
integers: 247
booleans: 6
conflicts: 0
branches: 6
propagations: 0
integer_propagations: 65
restarts: 0
lp_iterations: 53
walltime: 0.182911
usertime: 0.182911
deterministic_time: 0.000380957
gap_integral: 0
lperron commented 1 year ago

Some comments: