kibaekkim
commented
2 years ago Below I am just copying my email reply for the record.
The main reason that DSP is slower than CPLEX is that the instance size is too small. It is expected that the decomposition methods may outperform the for large-scale problem instances (e.g., with a large number of scenarios) with parallel computation of the subproblems.
The other reason is by the nature of branching on first-stage continuous variables for global optimality. Detailed method is available in the paper: https://link.springer.com/article/10.1007/s12532-021-00212-y In the aspect, your instance is particularly difficult to solve because the first-stage variables are continuous whereas the second stage has integers. I call this class of problems the most difficult one in stochastic linear programming.
I found that enabling a rounding heuristic reduces the number of nodes solved and solution time. You can create a parameter file (e.g., params.txt) with the following line:
bool DW/HEURISTICS/ROUNDING trueand add the argument --param params.txt to your command line.
But, ideally if you want to see the outperformance of DSP over CPLEX, you can try increasing the number of scenarios and running DSP in parallel. Please let me know if you need any help.
I am a research fellow at the University of Bologna (Italy). Currently, I am dealing with Stochastic Optimization and I am interested in using the DSP solver to solve a MIP problem whose mathematical formulation presents a block-structure model. I downloaded and installed the solver, and I successfully run the test instances you provide. But, when I tried to solve an instance of my problem, I experienced unsatisfactory performances.
The underlying problem of the problem at hand is a resource planning problem. The input consists of a set of resources used to meet demands for a set of customers, and the objective is to determine the quantity of each resource to activate to satisfy the demands. Given the unit cost c_i of each resource i, the demand lambda_j of each customer j, and the service rate mu_ij of resource i for customer j, the problem is to decide the activation level of each resource and the assignment of customers to resources, in such a way that the demand of the customers is satisfied at minimum cost. Variables x_i and y_ij define the activation level of resource i and the amount of resource i allocated to customer j, respectively. The y variables are imposed to be integer, i.e., resources must be assigned to customers in integer multiples.
An instance of the problem I am trying to solve using DSP consists of a set of scenarios in which the demand of each customer varies. Activation variables x_i are first-stage variables (i.e., the resource levels must be decided before knowing the actual demand), while y_ij variables are second-stage variables (they also present a scenario index).
I am trying to solve an instance with 8 resources, 12 customers and 5 scenarios. I am attaching both the MPS files and the DEC file that I generated. intCCP_1_0_5_10.zip Since the problem is a MIP, I run DSP using the Dantzig-Wolfe Decomposition (option “--algo dw”) and default parameters. With this setting, DSP takes 532.29 seconds to find the optimal solution, while Cplex only requires 0.01 seconds. Do you have any idea why the DSP solver can take so long? Is the problem suitable to being solved by the DSP solver?
Many thanks in advance for your time.