How can the optimodel tool be used automatically in large-scale problems #1
Comments
|
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. |
|
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. |
|
The error message is as follows, could you help me take a look： 00:00:00.816 INFO optimodel.tool.boolean: ======================================== 00:00:07.100 INFO optimodel.tool.boolean: ======================================== 00:00:07.282 INFO optimodel.tool.boolean: ======================================== 00:00:07.791 INFO optimodel.tool.boolean: ======================================== 00:00:08.910 INFO optimodel.tool.boolean: ======================================== |
|
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). |
|
err: |
|
when i use command:optimodel.boolean --cnf . / SubsetMILP:solver=gurobi |
|
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: and normally the constraints should be saved in the .system file. But now you have Or you can run from scratch Let me know if this works. |
|
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. |
|
Do you mean the filename is different? Can you just put it in PATH under the right name? |
|
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). |
|
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. |
|
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. |
|
@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. |
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.
The text was updated successfully, but these errors were encountered: