Method and system for decomposing a problem involving discrete optimization into a plurality of smaller subproblems and use of the method for solving the problem

A digital computer comprising:

• a central processing unit;
• a display device;
• a communication port for operatively connecting the digital computer to an optimization oracle;
• a memory unit comprising an application for preprocessing a problem involving discrete optimization over a plurality of variables, the application comprising:
• instructions for obtaining an indication of a problem involving discrete optimization;
• instructions for converting the problem involving discrete optimization into a problem suitable for a given optimization oracle architecture of the optimization oracle,
• instructions for providing a given number of times M the problem suitable for the given optimization oracle architecture to the optimization oracle,
• instructions for obtaining from the optimization oracle, for each providing of the problem, a plurality of configurations, each configuration generated by a call to the optimization oracle,
• instructions for obtaining a variable selection criterion, the variable selection criterion for determining at least one variable of the plurality of generated configurations to be fixed,
• instructions for determining at least one variable that matches the variable selection criterion and a corresponding value for each variable, and
• instructions for fixing the at least one determined variable at the corresponding value in the problem involving discrete optimization to thereby preprocess the problem to generate at least one subproblem;
• and
• instructions for providing an indication of the at least one generated subproblem and an indication of the at least one fixed variable;
• and
• a data bus for interconnecting the central processing unit, the display device, the communication port and the memory unit.

A non-transitory computer-readable storage medium for storing computer-executable instructions which, when executed, cause a digital computer to perform a method for preprocessing a problem involving discrete optimization over a plurality of variables, the method comprising:

• obtaining an indication of a problem involving discrete optimization;
• converting the problem involving discrete optimization into a problem suitable for a given optimization oracle architecture of the optimization oracle;
• providing a given number of times M the problem suitable for the given optimization oracle architecture to the optimization oracle;
• obtaining from the optimization oracle, for each providing of the problem, a plurality of configurations, each configuration generated by a call to the optimization oracle;
• obtaining a variable selection criterion, the variable selection criterion for determining at least one variable of the plurality of generated configurations to be fixed;
• determining at least one variable that matches the variable selection criterion and a corresponding value for each variable;
• fixing the at least one determined variable at the corresponding value in the problem involving discrete optimization to thereby preprocess the problem to generate at least one subproblem;
• and
• providing an indication of the at least one generated subproblem and an indication of the at least one fixed variable.