How can the optimodel tool be used automatically in large-scale problems

[oybba]

Excuse me. How can the optimodel tool be used automatically in large-scale problems, such as finding the minimum CNF constraints of an 8-bit S-box? Or how can it be used manually? I have downloaded Gurobi on my computer.

[hellman]

Yes, the tool should be able to find minimum CNFs. Did you try to follow the "usage" section? ( https://github.com/hellman/optimodel#usage ) Let me know where you are stuck.

Also what do you mean by "constraints of an S-box"? It can be modeling evaluation (x,S(x)) - this can be done separately for each output bit; it can be modeling e.g. DDT support - then you need to write down the 16-bit set; it can be modeling DDT with probabilities - then you need to figure out multiple Boolean sets you need to model (depends on the technique to represent probabilities) and run each of them separately.

To sum up, the tool does not know about S-boxes, it just models subsets of bitstrings / Boolean functions.

[oybba]

When I use it, I divide the truth table of the S-box into two files: include and exclude. In the 4-bit S-box experiment, the exclude file contains 159 pieces of data, and the minimum CNF can be automatically generated in optimodel. However, in the 8-bit S-box experiment, the exclude file contains 33,150 pieces of data. I notice that optimodel defines it as a large-scale problem, but using the preset parameters for large-scale problems will report an error. I notice that in the usage, the author mentions that large-scale problems cannot be completely automated. What I want to ask is how optimodel manually processes the minimization of large-scale CNF. If you have time, I hope to get your answer.

[oybba]

The error message is as follows, could you help me take a look：
00:00:00.582 INFO root: starting at 2025-02-22.14:27:44
00:00:00.582 INFO root: added file handler at 2025-02-22.14:27:44
00:00:00.582 INFO optimodel.tool.boolean: Namespace(force=False, dontcare=False, cnf=True, dnf=False, fileprefix='./', commands=[])
00:00:00.583 INFO optimodel.tool.boolean: CNF format: using excluded set
00:00:00.583 INFO optimodel.tool.set_files: reading bzip2 file .//exclude.bz2
00:00:00.686 INFO optimodel.constraint_pool:ConstraintPool: no reorienting
00:00:00.810 INFO optimodel.constraint_pool:ConstraintPool: exclude: 33150 points, hash d4e9305aa80d768710cb7dddcdd9a559
00:00:00.810 INFO optimodel.constraint_pool:ConstraintPool: include: (not given) points, hash -1
00:00:00.816 INFO optimodel.tool.boolean: using output prefix .//cnf.
00:00:00.816 INFO optimodel.tool.boolean: commands: MaxCubes:Dense3 AutoSelect
00:00:00.816 INFO optimodel.tool.boolean:

00:00:00.816 INFO optimodel.tool.boolean: ========================================
00:00:00.816 INFO optimodel.tool.boolean: running command MaxCubes ('Dense3',) {}
00:00:00.816 INFO optimodel.tool.boolean: calling Quine-McCluskey algorithm MaxCubes_Dense3
00:00:01.130 INFO optimodel.tool.boolean: done Quine-McCluskey
00:00:01.130 INFO optimodel.tool.boolean: time cnf MaxCubes_Dense3 0.31 seconds
00:00:01.130 INFO optimodel.tool.boolean: filling the system with cubes...
00:00:07.090 INFO monolearn.LowerSetLearn:LowerSetLearn: saved state to file .//cnf.system.bz2
00:00:07.098 INFO monolearn.LowerSetLearn:LowerSetLearn: lower 70336: 1:1 2:1580 4:51073 8:17513 16:153 128:16
00:00:07.098 INFO monolearn.LowerSetLearn:LowerSetLearn: upper 0:
00:00:07.099 INFO monolearn.LowerSetLearn:LowerSetLearn: system is complete for lower!
00:00:07.100 INFO optimodel.tool.boolean: command MaxCubes returned None in 6.28 seconds
00:00:07.100 INFO optimodel.tool.boolean:

00:00:07.100 INFO optimodel.tool.boolean: ========================================
00:00:07.100 INFO optimodel.tool.boolean: running command AutoSelect () {}
00:00:07.100 WARNING optimodel.constraint_pool:ConstraintPool: finalizing ConstraintPool's system for using in subset covers
00:00:07.282 INFO optimodel.constraint_pool:ConstraintPool: finished finalizing
00:00:07.282 INFO optimodel.tool.boolean: AutoSelect with 70336 sets and 33150 elements
00:00:07.282 INFO optimodel.tool.boolean: using AutoLarge preset
00:00:07.282 INFO optimodel.tool.boolean:

00:00:07.282 INFO optimodel.tool.boolean: ========================================
00:00:07.282 INFO optimodel.tool.boolean: running command SubsetWriteGecco () {}
00:00:07.282 INFO optimodel.constraint_pool:ConstraintPool: saving META with 33150 variables (per exclude point), 70336 sets (per constraint) to .//cnf.subset.meta
00:00:07.462 INFO optimodel.constraint_pool:ConstraintPool: saving GECCO with 33150 variables (per exclude point), 70336 sets (per constraint) to .//cnf.subset.gecco
00:00:07.790 INFO optimodel.tool.boolean: command SubsetWriteGecco returned None in 0.51 seconds
00:00:07.790 INFO optimodel.tool.boolean:

00:00:07.791 INFO optimodel.tool.boolean: ========================================
00:00:07.791 INFO optimodel.tool.boolean: running command SubsetWriteMILP () {'solver': 'swiglpk'}
00:00:07.791 INFO optimodel.constraint_pool:ConstraintPool: creating MILP instance for writing
00:00:07.791 INFO optimodel.constraint_pool:ConstraintPool: InequalitiesPool.create_subset_milp(solver=swiglpk)
00:00:07.791 INFO optimodel.constraint_pool:ConstraintPool: 70336 ineqs 33150 exclude points
00:00:07.791 INFO optisolveapi.milp.base: MILP minimization with solver 'swiglpk'
00:00:08.573 INFO optimodel.constraint_pool:ConstraintPool: saving LP with 70336 variables (per ineq), 33150 constraints (per exclude point) to .//cnf.subset.lp
Writing problem data to './/cnf.subset.lp'...
314217 lines were written
00:00:08.718 INFO optimodel.constraint_pool:ConstraintPool: saving META with 33150 variables (per exclude point), 70336 sets (per constraint) to .//cnf.subset.meta
00:00:08.909 INFO optimodel.tool.boolean: command SubsetWriteMILP returned None in 1.12 seconds
00:00:08.910 INFO optimodel.tool.boolean:

00:00:08.910 INFO optimodel.tool.boolean: ========================================
00:00:08.910 INFO optimodel.tool.boolean: running command SubsetSCS ('largeneighborhoodsearch_2',) {'timeout': 10}
00:00:08.910 INFO optimodel.tool.boolean: SCS iter 1/1
00:00:08.910 INFO optimodel.constraint_pool:ConstraintPool: 70336 constraints/sets 33150 exclude points
00:00:08.910 INFO optimodel.constraint_pool:ConstraintPool: setcoveringsolver algorithm : largeneighborhoodsearch_2 timeout : 10
00:00:08.910 INFO optimodel.constraint_pool:ConstraintPool: $ setcoveringsolver --algorithm largeneighborhoodsearch_2 --input .//cnf.subset.gecco --unicost --time-limit 10 --certificate .//cnf.scs.solution --verbosity 10 --seed 377194562 --log2stderr
Traceback (most recent call last):
File "/usr/local/bin/optimodel.boolean", line 8, in
sys.exit(main())
File "/usr/local/lib/python3.10/dist-packages/optimodel/tool/boolean.py", line 283, in main
return ToolBoolean().main()
File "/usr/local/lib/python3.10/dist-packages/optimodel/tool/boolean.py", line 139, in main
self.run_command_string(cmd)
File "/usr/local/lib/python3.10/dist-packages/optimodel/tool/base.py", line 14, in run_command_string
ret = getattr(self, method)(*args, **kwargs)
File "/usr/local/lib/python3.10/dist-packages/monolearn/utils.py", line 139, in time_func
ret = func(*args, **kwargs)
File "/usr/local/lib/python3.10/dist-packages/optimodel/tool/constraint_base.py", line 97, in AutoSelect
return self.AutoLarge()
File "/usr/local/lib/python3.10/dist-packages/monolearn/utils.py", line 139, in time_func
ret = func(*args, **kwargs)
File "/usr/local/lib/python3.10/dist-packages/optimodel/tool/constraint_base.py", line 112, in AutoLarge
self.run_command_string(cmd)
File "/usr/local/lib/python3.10/dist-packages/optimodel/tool/base.py", line 14, in run_command_string
ret = getattr(self, method)(*args, **kwargs)
File "/usr/local/lib/python3.10/dist-packages/monolearn/utils.py", line 139, in time_func
ret = func(*args, **kwargs)
File "/usr/local/lib/python3.10/dist-packages/optimodel/tool/constraint_base.py", line 163, in SubsetSCS
self.pool.subset_by_setcoveringsolver(*args, **kwargs)
File "/usr/local/lib/python3.10/dist-packages/optimodel/constraint_pool.py", line 366, in subset_by_setcoveringsolver
subprocess.check_call(cmd, timeout=timeout + 5)
File "/usr/lib/python3.10/subprocess.py", line 364, in check_call
retcode = call(*popenargs, **kwargs)
File "/usr/lib/python3.10/subprocess.py", line 345, in call
with Popen(*popenargs, **kwargs) as p:
File "/usr/lib/python3.10/subprocess.py", line 971, in init
self._execute_child(args, executable, preexec_fn, close_fds,
File "/usr/lib/python3.10/subprocess.py", line 1863, in _execute_child
raise child_exception_type(errno_num, err_msg, err_filename)
FileNotFoundError: [Errno 2] No such file or directory: 'setcoveringsolver'

[hellman]

You are right, the default large-scale sequence of commands runs "setcoveringsolver" for heuristic approach to find a short subset of clauses. If you install it, it should work.

An alternative is to use another method for selecting a short subset of clauses. E.g. directly using MILP model (you can specify the solver e.g. if you have gurobi).

$ optimodel.cnf folder/ SubsetMILP:

Also, it writes down the MILP model to an .lp file which you can solve yourself externally, however there is no yet a tool here to convert an LP solution to the full CNF. Basically you can check the .lp.meta file, which contains at line #i: the index i, the points removed by this constraints, the constraint (the clause) a flag whether this constraint should be taken. So in your .LP solution, if you have variable "v_take_consXX" equal to 1, where XX is some number, then you just need to add the corresponding clause from line XX to your formula.

Same can be done with GECCO format (UCSP solvers).

[oybba]

err:
00:00:09.532 INFO optimodel.constraint_pool:ConstraintPool: $ setcoveringsolver --algorithm largeneighborhoodsearch_2 --input ./cnf.subset.gecco --unicost --time-limit 10 --certificate ./cnf.scs.solution --verbosity 10 --seed 605413091 --log2stderr
terminate called after throwing an instance of 'boost::wrapexceptboost::program_options::unknown_option'
what(): unrecognised option '--log2stderr'
00:00:09.646 ERROR optimodel.constraint_pool:ConstraintPool: Command '['setcoveringsolver', '--algorithm', 'largeneighborhoodsearch_2', '--input', './cnf.subset.gecco', '--unicost', '--time-limit', '10', '--certificate', './cnf.scs.solution', '--verbosity', '10', '--seed', '605413091', '--log2stderr']' died with <Signals.SIGABRT: 6>.

[oybba]

when i use command:optimodel.boolean --cnf . / SubsetMILP:solver=gurobi
error:00:00:00.853 INFO optimodel.tool.boolean: running command SubsetMILP () {'solver': 'gurobi'}
00:00:00.853 INFO optimodel.constraint_pool:ConstraintPool: InequalitiesPool.create_subset_milp(solver=gurobi)
00:00:00.853 WARNING optimodel.constraint_pool:ConstraintPool: finalizing ConstraintPool's system for using in subset covers
00:00:00.853 INFO optimodel.constraint_pool:ConstraintPool: finished finalizing
00:00:00.853 INFO optimodel.constraint_pool:ConstraintPool: 0 ineqs 33150 exclude points
00:00:00.853 INFO optisolveapi.milp.base: MILP minimization with solver 'gurobi'
Traceback (most recent call last):
File "/usr/local/bin/optimodel.boolean", line 8, in
sys.exit(main())
File "/usr/local/lib/python3.10/dist-packages/optimodel/tool/boolean.py", line 283, in main
return ToolBoolean().main()
File "/usr/local/lib/python3.10/dist-packages/optimodel/tool/boolean.py", line 139, in main
self.run_command_string(cmd)
File "/usr/local/lib/python3.10/dist-packages/optimodel/tool/base.py", line 14, in run_command_string
ret = getattr(self, method)(*args, **kwargs)
File "/usr/local/lib/python3.10/dist-packages/monolearn/utils.py", line 139, in time_func
ret = func(*args, **kwargs)
File "/usr/local/lib/python3.10/dist-packages/optimodel/tool/constraint_base.py", line 146, in SubsetMILP
self.pool.subset_by_milp(*args, **kwargs)
File "/usr/local/lib/python3.10/dist-packages/optimodel/constraint_pool.py", line 296, in subset_by_milp
v_take_ineq, milp = self.create_subset_milp(solver=solver)
File "/usr/local/lib/python3.10/dist-packages/optimodel/constraint_pool.py", line 281, in create_subset_milp
assert lst, "no solutions"
AssertionError: no solutions

[hellman]

Regarding setcoveringsolver, it seems the command line interface has changed (e.g. log2stderr was replaced by log-to-stderr). I was using the commit https://github.com/fontanf/setcoveringsolver/tree/894950189a5ec7a77672ee48eafa2969a9192f45 can you try to install this one?

I will see how much needs to be updated to accomodate the new version (ideally would be to include a portable version inside optimodel).

Regarding SubsetMILP, you need to run it in the existing folder with computed CNF system. E.g. you had in the first run:

00:00:08.910 INFO optimodel.constraint_pool:ConstraintPool: 70336 constraints/sets 33150 exclude points

and normally the constraints should be saved in the .system file. But now you have

00:00:00.853 INFO optimodel.constraint_pool:ConstraintPool: 0 ineqs 33150 exclude points

Or you can run from scratch

optimodel.boolean --cnf ./ MaxCubes:Dense3 SubsetMILP:solver=gurobi

Let me know if this works.

[oybba]

https://github.com/fontanf/setcoveringsolver/tree/894950189a5ec7a77672ee48eafa2969a9192f45

This version doesn't work either

the executable file in this version is not the setcoveringsolver specified in the preset command.

[hellman]

Do you mean the filename is different? Can you just put it in PATH under the right name?

[oybba]

https://github.com/fontanf/setcoveringsolver/tree/894950189a5ec7a77672ee48eafa2969a9192f45

This version can work! However, it seems unable to provide optimal solutions (files ending with .opt) like it does for small-scale problems.

Additionally, I noticed that solving the same problem using Gurobi takes a significant amount of time (more than a day).

[hellman]

Yes, setcoveringsolver it is a heuristic greedy solver. For optimal solution, you have to use MILP or optimal UCSP (Gecco format) solvers. You can try SubsetMILP with gurobi but it may take a long time if ever finish (you could track the evolution of the lower bound).

Sorry I was not precise in my first reply. For 8-bit S-boxes - 16-bit sets - finding the optimal minimum is really challenging. But the greedy heuristics should be good enough. Potentially you can try to solve the .lp file on a powerful machine / cluster. But it is not clear how much compute is needed.

[fontanf]

I take the liberty to intervene in this thread since this package uses some of my codes.

First, I apologize for the format change. I did a lot of refactoring in my codes last year that had some breaking changes.

If you have real-world difficult set covering problems, please do not hesitate to export and share them if you can. The efficiency of an algorithm on a problem highly depends on the shape of the instances used to design it. Currently, almost all the instances used when developing algorithms for set covering problems are synthetic data. The optimization community would be glad to get new difficult relevant instances to work on.

Also, please try the local search and large neighborhood search algorithms. The greedy may return solutions far from optimal, while these algorithm should quickly get much better solutions.

[hellman]

@fontanf thank you for your comment and for your tool! I know some people interested in this, we will try to collect some hard instances. Although I don't know if there are interesting ones in terms of structure and not due to a large instance size.