Local-ILP Heuristic

[Stuart Rogers]

Local-ILP is a recent LP-free primal heuristic for solving ILPs that may be useful for CP-SAT. While Local-ILP does not offer a free software implementation, it seems to be competitive with Gurobi.

https://arxiv.org/abs/2305.00188

[Laurent Perron]

Thanks

Le sam. 12 août 2023, 10:57, Stuart Rogers <stum...@gmail.com> a écrit :

Local-ILP is a recent LP-free primal heuristic for solving ILPs that may be useful for CP-SAT. While Local-ILP does not offer a free software implementation, it seems to be competitive with Gurobi.

https://arxiv.org/abs/2305.00188

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/e0c9bee0-0707-415b-aae1-79e48dcd8368n%40googlegroups.com.

[Stuart Rogers]

There is a Local-ILP executable on GitHub: https://github.com/shaowei-cai-group/Local-ILP

[Stuart Rogers]

The executable doesn't work for me when I try to run it on an AMD x86_64 CPU running Ubuntu 20.04.5.

$ ./Local-ILP input.mps 5
Segmentation fault (core dumped)

[Stuart Rogers]

The executable does indeed work. I forgot to provide the name of the solution file.

$ ./Local-ILP input.mps 600 input.sol

[aire...@gmail.com]

It gives me this error:

zzzz@Ubuntu-2004-focal-64-minimal:~/temp/Local-ILP/bin$ sudo sh ./Local-ILP  large_model.mps 600 output.sol
./Local-ILP: 1: @8: not found
./Local-ILP: 1:ELF: not found
./Local-ILP: 1: Syntax error: "|" unexpected

[Laurent Perron]

wrong platform. It is dynamically linked against specific versions.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/d50c04f1-dfba-4c2a-a3f8-b49d24c236cfn%40googlegroups.com.

[Laurent Perron]

I ran it on a few examples:

  it only accepts pure integral problems, which is fine by me

  with sbc_cat_small examples, it finds a solution with value 52750 then gets stuck. CP-SAT finds 35750 in 2s

Still I like the 3 phases. I need to read the paper carefully.

  

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

[Laurent Perron]

I ran with pure ls (feasibility_jump + violation_ls)

Starting search at 1.18s with 4 workers.

4 first solution subsolvers: [jump, jump_decay_perturb, jump_decay_rnd_on_rst, jump_no_rst]

4 incomplete subsolvers: [violation_ls(2), violation_ls_decay(2)]

3 helper subsolvers: [neighborhood_helper, synchronization_agent, update_gap_integral]

#1       1.18s best:89800 next:[0,89750]  jump_decay_rnd_on_rst(batch:1 #lin_moves:121/2'705 #weight_updates:17)

#2       1.18s best:64900 next:[0,64850]  jump_decay_perturb(batch:1 #lin_moves:171/3'517 #weight_updates:30)

#3       1.19s best:63000 next:[0,62950]  violation_ls_decay(batch:1 #solutions_imported:1 #lin_moves:17/1'087 #weight_updates:89)

#4       1.19s best:62600 next:[0,62550]  violation_ls_decay(batch:1 #solutions_imported:1 #lin_moves:17/1'088 #weight_updates:89)

#5       1.19s best:62200 next:[0,62150]  violation_ls_decay(batch:2 #solutions_imported:2 #lin_moves:19/1'624 #weight_updates:99)

#6       1.19s best:62100 next:[0,62050]  violation_ls_decay(batch:2 #solutions_imported:2 #lin_moves:19/1'689 #weight_updates:99)

#7       1.19s best:61100 next:[0,61050]  violation_ls_decay(batch:3 #solutions_imported:3 #lin_moves:124/5'872 #weight_updates:154)

#8       1.19s best:61000 next:[0,60950]  violation_ls_decay(batch:3 #solutions_imported:3 #lin_moves:21/2'215 #weight_updates:106)

#9       1.19s best:54400 next:[0,54350]  violation_ls_decay(batch:4 #solutions_imported:4 #lin_moves:126/6'386 #weight_updates:156)

#10      1.19s best:53700 next:[0,53650]  violation_ls_decay(batch:4 #solutions_imported:4 #lin_moves:41/3'598 #weight_updates:122)

#11      1.20s best:53600 next:[0,53550]  violation_ls_decay(batch:5 #solutions_imported:5 #lin_moves:128/6'979 #weight_updates:158)

#12      1.20s best:53500 next:[0,53450]  violation_ls_decay(batch:5 #solutions_imported:5 #lin_moves:43/4'173 #weight_updates:125)

#13      1.20s best:52200 next:[0,52150]  violation_ls_decay(batch:6 #solutions_imported:6 #lin_moves:181/9'296 #weight_updates:214)

#14      1.20s best:49900 next:[0,49850]  violation_ls_decay(batch:6 #solutions_imported:6 #lin_moves:172/8'677 #weight_updates:156)

#15      1.20s best:49200 next:[0,49150]  violation_ls_decay(batch:7 #solutions_imported:7 #lin_moves:242/11'768 #weight_updates:230)

#16      1.20s best:49100 next:[0,49050]  violation_ls_decay(batch:7 #solutions_imported:7 #lin_moves:174/9'248 #weight_updates:158)

#17      1.20s best:48700 next:[0,48650]  violation_ls_decay(batch:8 #solutions_imported:8 #lin_moves:260/12'926 #weight_updates:242)

#18      1.21s best:48500 next:[0,48450]  violation_ls_decay(batch:8 #solutions_imported:8 #lin_moves:235/11'620 #weight_updates:172)

#19      1.21s best:48400 next:[0,48350]  violation_ls_decay(batch:9 #solutions_imported:9 #lin_moves:264/13'618 #weight_updates:244)

#20      1.21s best:47500 next:[0,47450]  violation_ls_decay(batch:9 #solutions_imported:9 #lin_moves:364/15'852 #weight_updates:201)

#21      1.25s best:46150 next:[0,46100]  violation_ls_decay(batch:10 #solutions_imported:10 #lin_moves:429/17'962 #weight_updates:218)

#22      1.26s best:40900 next:[0,40850]  violation_ls_decay(batch:10 #solutions_imported:10 #lin_moves:2'792/94'538 #weight_updates:555)

#23      1.26s best:40800 next:[0,40750]  violation_ls_decay(batch:11 #solutions_imported:11 #lin_moves:2'800/95'424 #weight_updates:557)

#24      1.26s best:40000 next:[0,39950]  violation_ls_decay(batch:12 #solutions_imported:12 #lin_moves:2'826/96'746 #weight_updates:569)

#25      1.26s best:39100 next:[0,39050]  violation_ls_decay(batch:13 #solutions_imported:13 #lin_moves:2'980/101'835 #weight_updates:618)

#26      1.26s best:38900 next:[0,38850]  violation_ls_decay(batch:12 #solutions_imported:12 #lin_moves:1'339/49'442 #weight_updates:372)

#27      1.26s best:37100 next:[0,37050]  violation_ls_decay(batch:13 #solutions_imported:13 #lin_moves:1'341/49'964 #weight_updates:374)

#28      1.31s best:36900 next:[0,36850]  violation_ls(batch:3 #solutions_imported:3 #lin_moves:6'036/296'592 #weight_updates:6'160)

#29      1.32s best:36800 next:[0,36750]  violation_ls(batch:3 #solutions_imported:3 #lin_moves:6'446/303'321 #weight_updates:5'876)

#30      1.42s best:36700 next:[0,36650]  violation_ls_decay(batch:15 #solutions_imported:15 #lin_moves:10'471/331'025 #weight_updates:1'365)

#31      1.43s best:36600 next:[0,36550]  violation_ls(batch:5 #solutions_imported:5 #lin_moves:12'438/596'711 #weight_updates:12'021)

#32      1.47s best:36500 next:[0,36450]  violation_ls_decay(batch:17 #solutions_imported:17 #lin_moves:21'274/699'084 #weight_updates:2'510)

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

[pierpaolo...@gmail.com]

I can't understand if this tool is freely usable. On the GitHub page linked in the discussion, the provided license is GPL, hence it looks as it should be freely available and modifiable with the same license, but no source is provided. 

[Stuart Rogers]

This paper proposes some LP-based heuristics to solve ILPs. https://arxiv.org/pdf/2212.08183.pdf

[Laurent Perron]

We are already working on this one.

It seems to be very focused on Boolean only medium sized problems.

Thanks

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/0563b07e-7870-4a6f-8330-bc290781906en%40googlegroups.com.

[Stuart Rogers]

Does CP-SAT use GLOP to solve the LP relaxation of ILPs that are not too large?

[Laurent Perron]

Glop is the base of the linear relaxation and cuts for linear and cp models.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/7926b015-0f8f-4200-b1ee-11802792993bn%40googlegroups.com.

[Stuart Rogers]

Here is the executable for a heuristic to solve MILPs. https://github.com/shaowei-cai-group/Local-MIP

[aire...@gmail.com]

Can you also mention OS and version details, last time I tried Local-ILP on Ubuntu 20.04 and it didn't work.

Thanks