Closed JackokieZhao closed 1 year ago
Hi,
Hi,
You can export the .lp file from gurobi as:
gurobi_model.write(exported.lp)
Ref: https://www.gurobi.com/documentation/9.5/refman/py_model_write.html
When I run the command "bdd_solver_cl -i test.lp -s mma_cuda", it throws the error "bdd_solver_cl: /opt/BDD/src/bdd_cuda_base.cu:475: void LPMP::bdd_cuda_base
Gurobi can solve the problem within 5s, Running time: 4.653985500335693 seconds, total cost: 988000.
Details: The following is my source code. ` def gurobi_scell(params, positions, dl_chl, ul_chl): """ Solve maximum covering location problem Input: ues_pos: input ues_pos, Numpy array in shape of [N,2] num_bs: the number of sites to select radius: the radius of circle positions: the candidate sites, which will randomly generated inside the ConvexHull wrapped by the polygon MIPFocus: Return: opt_sites: locations K optimal sites, Numpy array in shape of [K,2] f: the optimal value of the objective function """
K = dl_chl.shape[1]
M = len(positions)
p1_sc = C_AP + C_Fiber + C_ins_Fiber + C_pw_micBS + C_pw_FH + C_ren_micTower
p3_sc = C_pw_server_room + C_om + C_ren_server_room + C_cen_BBU
# Channel fading.
G_D_dB = dl_chl
G_U_dB = ul_chl
P_D_dB = 45
P_U_dB = 23
# Minmum SNR for access.
N_D_dB = -100
N_U_dB = -100
P_D_SNR_dB = P_D_dB + G_D_dB - N_D_dB
P_D_SNR_dB = (P_D_SNR_dB >= 0).astype(int)
P_U_SNR_dB = P_U_dB + G_U_dB - N_U_dB
P_U_SNR_dB = (P_U_SNR_dB >= 0).astype(int)
# Build model which is a class from gurobi.
model = Model()
x_m = model.addVars(M, vtype=GRB.BINARY, name="base")
model.update()
# Add constraints
for k in range(K):
model.addConstr(1 <= quicksum(x_m[m]*P_D_SNR_dB[m, k] * P_U_SNR_dB[m, k] for m in range(M)))
# ==============================================================================
# ============================== Objective =============================
# ===============================================================================
model.setObjective(p1_sc * quicksum(x_m[m] for m in range(M)) + p3_sc, GRB.MINIMIZE)
# - W_R_C * quicksum(x_u[i] * x_d[i] for i in range(pot_num)), GRB.MINIMIZE)
model.setParam('OutputFlag', 0)
for key, val in params.items():
if key != 'solver_name':
model.setParam(key, val)
model.optimize()
model.write("test.lp")
idx = np.array(np.where(np.array([x_m[m].X for m in range(M)]) > 0)).flatten()
mic_bs_pos = positions[idx]
# Compute the link base station.
p_u = P_U_SNR_dB[idx, :]
mic_link = np.argmax(p_u, axis=0)
return mic_bs_pos, mic_link, model.ObjVal`
The output is:
(base) ➜ Deployment git:(master) ✗ bdd_solver_cl -i test.lp -s mma_cuda [bdd solver] Parse lp file [ILP parser] ILP has variables that are not present in any constraint [ILP parser] ILP can bedivided into 2 subproblems execution time for parse_file is 265 ms execution time for bdd_solver_options is 274 ms [bdd solver] ILP has 1387 variables and 100 constraints [bdd solver] ILP has 1387 variables and 100 constraints after preprocessing [bdd preprocessor] convert 100 linear inequalities. [bdd preprocessor] #threads = 40 [bdd preprocessor] final #BDDs = 100 execution time for add_ilp is 250 ms Num vars: 1386, Num BDDs: 100, Num Nodes: 62532 execution time for initialize is 344 ms execution time for populate_bdd_nodes is 132 ms execution time for reorder_bdd_nodes is 0 ms execution time for compress_bdd_nodes_to_layer is 0 ms execution time for set_special_nodes_indices is 0 ms Hops: [0 - 1], # BDD nodes: 100 Hops: [1 - 142], # BDD nodes: 200 Hops: [142 - 156], # BDD nodes: 198 Hops: [156 - 157], # BDD nodes: 196 Hops: [157 - 162], # BDD nodes: 194 Hops: [162 - 169], # BDD nodes: 192 Hops: [169 - 184], # BDD nodes: 190 Hops: [184 - 187], # BDD nodes: 188 Hops: [187 - 194], # BDD nodes: 186 Hops: [194 - 202], # BDD nodes: 184 Hops: [202 - 207], # BDD nodes: 182 Hops: [207 - 210], # BDD nodes: 180 Hops: [210 - 214], # BDD nodes: 178 Hops: [214 - 224], # BDD nodes: 174 Hops: [224 - 226], # BDD nodes: 168 Hops: [226 - 229], # BDD nodes: 166 Hops: [229 - 230], # BDD nodes: 164 Hops: [230 - 231], # BDD nodes: 160 Hops: [231 - 236], # BDD nodes: 158 Hops: [236 - 237], # BDD nodes: 156 Hops: [237 - 244], # BDD nodes: 154 Hops: [244 - 246], # BDD nodes: 152 Hops: [246 - 250], # BDD nodes: 150 Hops: [250 - 256], # BDD nodes: 148 Hops: [256 - 259], # BDD nodes: 146 Hops: [259 - 270], # BDD nodes: 144 Hops: [270 - 277], # BDD nodes: 142 Hops: [277 - 280], # BDD nodes: 140 Hops: [280 - 282], # BDD nodes: 136 Hops: [282 - 284], # BDD nodes: 134 Hops: [284 - 287], # BDD nodes: 132 Hops: [287 - 294], # BDD nodes: 128 Hops: [294 - 297], # BDD nodes: 126 Hops: [297 - 303], # BDD nodes: 122 Hops: [303 - 304], # BDD nodes: 120 Hops: [304 - 307], # BDD nodes: 116 Hops: [307 - 308], # BDD nodes: 110 Hops: [308 - 314], # BDD nodes: 108 Hops: [314 - 315], # BDD nodes: 106 Hops: [315 - 316], # BDD nodes: 104 Hops: [316 - 320], # BDD nodes: 102 Hops: [320 - 321], # BDD nodes: 100 Hops: [321 - 322], # BDD nodes: 98 Hops: [322 - 330], # BDD nodes: 96 Hops: [330 - 333], # BDD nodes: 94 Hops: [333 - 334], # BDD nodes: 92 Hops: [334 - 337], # BDD nodes: 90 Hops: [337 - 339], # BDD nodes: 88 Hops: [339 - 341], # BDD nodes: 86 Hops: [341 - 345], # BDD nodes: 84 Hops: [345 - 346], # BDD nodes: 82 Hops: [346 - 347], # BDD nodes: 80 Hops: [347 - 350], # BDD nodes: 78 Hops: [350 - 352], # BDD nodes: 76 Hops: [352 - 360], # BDD nodes: 74 Hops: [360 - 362], # BDD nodes: 72 Hops: [362 - 364], # BDD nodes: 70 Hops: [364 - 365], # BDD nodes: 68 Hops: [365 - 367], # BDD nodes: 66 Hops: [367 - 369], # BDD nodes: 64 Hops: [369 - 371], # BDD nodes: 62 Hops: [371 - 372], # BDD nodes: 60 Hops: [372 - 373], # BDD nodes: 58 Hops: [373 - 374], # BDD nodes: 56 Hops: [374 - 376], # BDD nodes: 54 Hops: [376 - 377], # BDD nodes: 52 Hops: [377 - 379], # BDD nodes: 50 Hops: [379 - 383], # BDD nodes: 48 Hops: [383 - 386], # BDD nodes: 44 Hops: [386 - 387], # BDD nodes: 42 Hops: [387 - 390], # BDD nodes: 38 Hops: [390 - 393], # BDD nodes: 34 Hops: [393 - 397], # BDD nodes: 32 Hops: [397 - 398], # BDD nodes: 30 Hops: [398 - 400], # BDD nodes: 26 Hops: [400 - 403], # BDD nodes: 24 Hops: [403 - 404], # BDD nodes: 22 Hops: [404 - 405], # BDD nodes: 20 Hops: [405 - 406], # BDD nodes: 16 Hops: [406 - 408], # BDD nodes: 14 Hops: [408 - 410], # BDD nodes: 12 Hops: [410 - 411], # BDD nodes: 10 Hops: [411 - 421], # BDD nodes: 6 Hops: [421 - 424], # BDD nodes: 4 Hops: [424 - 425], # BDD nodes: 2 execution time for bdd_cuda is 501 ms bdd_solver_cl: /opt/BDD/src/bdd_cuda_base.cu:475: void LPMP::bdd_cuda_base<REAL>::update_costs(COST_ITERATOR, COST_ITERATOR, COST_ITERATOR, COST_ITERATOR) [with COST_ITERATOR = __gnu_cxx::__normal_iterator<double*, std::vector<double> >; REAL = float]: Assertion
std::distance(cost_hi_begin, cost_hi_end) <= this->nr_variables()' failed.
[1] 166913 IOT instruction (core dumped) bdd_solver_cl -i test.lp -s mma_cuda`
This is the .lp file.
https://drive.google.com/file/d/1xmwVg0MQOzbLHZhKTwmVfMmqXdx_SR6k/view?usp=share_link
Thanks for providing the .lp file. The issue is we assume that each variable is present atleast once in a some constraint. For the provided file there are some which are not in any constraint. A simple way to fix this is by presolving first (which will remove such variables) and then do:
model.presolve().write("test.lp")
(edit: there is still an error, I am looking into it)
Maybe " each variable is present at least once in a constraint" is not a general case... But, you still do a good job! If it can be extended to a general LP or NLP, it will be more useful! I wish the algorithm can work in my job and I will also cite it.
In addition, the work will be more popular if it has a python interface. I am thinking about how to call the BDD in my python source code.
Constant
and also remove it from Bounds
(line 5899). Basically we assume that the input instance does not contain already fixated values. python setup.py install
in the root directory. An example to run is:import BDD.ILP_instance_py as ilp_instance_bbd
import BDD.bdd_cuda_learned_mma_py as bdd_solver
bdd_ilp_instance = ilp_instance_bbd.read_ILP('YOUR_LP_FILE.LP')
solver = bdd_solver.bdd_cuda_learned_mma(bdd_ilp_instance, False, 1.0)
## DUAL SOLVER:
omega = 0.5 # parameter from FastDOG paper.
num_dual_iterations = 10000 # maximum allowed number of iterations, solver can terminate early due to convergence criteria below:
relative_improvement_slope = 1e-6 # good values are in [1e-6, 1e-9], smaller values will terminate early.
time_limit = 3600 # in seconds
solver.non_learned_iterations(omega, num_dual_iterations, relative_improvement_slope, time_limit)
solver.distribute_delta() # make deferred min-marginals zero.
lowerbound = solver.lower_bound()
## PRIMAL HEURISTIC:
init_delta = 1.1
delta_growth_rate = 1.1
num_dual_iterations_in_primal_rounding = 200
verbose = True
primal_solution = solver.primal_rounding_incremental(init_delta, delta_growth_rate, num_dual_iterations_in_primal_rounding, verbose)
The setup.py cannot be installed in my machine. The output log is as following:
(base) ➜ BDD git:(main) ✗ python ./setup.py install running install /home/jackokie/Program/anaconda/lib/python3.9/site-packages/setuptools/command/install.py:34: SetuptoolsDeprecationWarning: setup.py install is deprecated. Use build and pip and other standards-based tools. warnings.warn( /home/jackokie/Program/anaconda/lib/python3.9/site-packages/setuptools/command/easy_install.py:144: EasyInstallDeprecationWarning: easy_install command is deprecated. Use build and pip and other standards-based tools. warnings.warn( running bdist_egg running egg_info writing src/BDD.egg-info/PKG-INFO writing dependency_links to src/BDD.egg-info/dependency_links.txt writing top-level names to src/BDD.egg-info/top_level.txt file src/bdd_cuda_torch.py (for module bdd_cuda_torch) not found reading manifest file 'src/BDD.egg-info/SOURCES.txt' adding license file 'LICENSE' writing manifest file 'src/BDD.egg-info/SOURCES.txt' installing library code to build/bdist.linux-x86_64/egg running install_lib running build_py file src/bdd_cuda_torch.py (for module bdd_cuda_torch) not found file src/bdd_cuda_torch.py (for module bdd_cuda_torch) not found running build_ext Testing gcc... ...has version 9.5.0 Found suitable gcc/g++ version gcc g++ CMake Error: CMake was unable to find a build program corresponding to "Ninja". CMAKE_MAKE_PROGRAM is not set. You probably need to select a different build tool. CMake Error: CMAKE_CXX_COMPILER not set, after EnableLanguage -- Configuring incomplete, errors occurred! See also "/home/jackokie/Downloads/BDD/build/temp.linux-x86_64-cpython-39/CMakeFiles/CMakeOutput.log". Traceback (most recent call last): File "/home/jackokie/Downloads/BDD/./setup.py", line 115, in <module> setup( File "/home/jackokie/Program/anaconda/lib/python3.9/site-packages/setuptools/__init__.py", line 87, in setup return distutils.core.setup(**attrs) File "/home/jackokie/Program/anaconda/lib/python3.9/site-packages/setuptools/_distutils/core.py", line 185, in setup return run_commands(dist) File "/home/jackokie/Program/anaconda/lib/python3.9/site-packages/setuptools/_distutils/core.py", line 201, in run_commands dist.run_commands() File "/home/jackokie/Program/anaconda/lib/python3.9/site-packages/setuptools/_distutils/dist.py", line 969, in run_commands self.run_command(cmd) File "/home/jackokie/Program/anaconda/lib/python3.9/site-packages/setuptools/dist.py", line 1208, in run_command super().run_command(command) File "/home/jackokie/Program/anaconda/lib/python3.9/site-packages/setuptools/_distutils/dist.py", line 988, in run_command cmd_obj.run() File "/home/jackokie/Program/anaconda/lib/python3.9/site-packages/setuptools/command/install.py", line 74, in run self.do_egg_install() File "/home/jackokie/Program/anaconda/lib/python3.9/site-packages/setuptools/command/install.py", line 123, in do_egg_install self.run_command('bdist_egg') File "/home/jackokie/Program/anaconda/lib/python3.9/site-packages/setuptools/_distutils/cmd.py", line 318, in run_command self.distribution.run_command(command) File "/home/jackokie/Program/anaconda/lib/python3.9/site-packages/setuptools/dist.py", line 1208, in run_command super().run_command(command) File "/home/jackokie/Program/anaconda/lib/python3.9/site-packages/setuptools/_distutils/dist.py", line 988, in run_command cmd_obj.run() File "/home/jackokie/Program/anaconda/lib/python3.9/site-packages/setuptools/command/bdist_egg.py", line 165, in run cmd = self.call_command('install_lib', warn_dir=0) File "/home/jackokie/Program/anaconda/lib/python3.9/site-packages/setuptools/command/bdist_egg.py", line 151, in call_command self.run_command(cmdname) File "/home/jackokie/Program/anaconda/lib/python3.9/site-packages/setuptools/_distutils/cmd.py", line 318, in run_command self.distribution.run_command(command) File "/home/jackokie/Program/anaconda/lib/python3.9/site-packages/setuptools/dist.py", line 1208, in run_command super().run_command(command) File "/home/jackokie/Program/anaconda/lib/python3.9/site-packages/setuptools/_distutils/dist.py", line 988, in run_command cmd_obj.run() File "/home/jackokie/Program/anaconda/lib/python3.9/site-packages/setuptools/command/install_lib.py", line 11, in run self.build() File "/home/jackokie/Program/anaconda/lib/python3.9/site-packages/setuptools/_distutils/command/install_lib.py", line 112, in build self.run_command('build_ext') File "/home/jackokie/Program/anaconda/lib/python3.9/site-packages/setuptools/_distutils/cmd.py", line 318, in run_command self.distribution.run_command(command) File "/home/jackokie/Program/anaconda/lib/python3.9/site-packages/setuptools/dist.py", line 1208, in run_command super().run_command(command) File "/home/jackokie/Program/anaconda/lib/python3.9/site-packages/setuptools/_distutils/dist.py", line 988, in run_command cmd_obj.run() File "/home/jackokie/Downloads/BDD/./setup.py", line 33, in run self.build_extension(ext) File "/home/jackokie/Downloads/BDD/./setup.py", line 112, in build_extension subprocess.check_call(['cmake', ext.sourcedir] + cmake_args, cwd=self.build_temp, env=env) File "/home/jackokie/Program/anaconda/lib/python3.9/subprocess.py", line 373, in check_call raise CalledProcessError(retcode, cmd) subprocess.CalledProcessError: Command '['cmake', '/home/jackokie/Downloads/BDD', '-DCMAKE_LIBRARY_OUTPUT_DIRECTORY=/home/jackokie/Downloads/BDD/build/lib.linux-x86_64-cpython-39/BDD', '-DPYTHON_EXECUTABLE=/home/jackokie/Program/anaconda/bin/python', '-DWITH_CUDA=ON', '-DCMAKE_GENERATOR=Ninja', '-DCMAKE_BUILD_TYPE=Release']' returned non-zero exit status 1.
Please try again with the latest code.
Please try again with the latest code.
Great! It can be installed for python. Thanks for your work! I have run the code https://github.com/LPMP/BDD/issues/14#issuecomment-1487071152. But the simulation in python is about 111s, but it's 6s in the command line. Why there's such a large range of different computer languages? And, the lower bound is also different between python and the command line. Also, could you tell me how to get the results for the problem in the command line? What about python?
The command
primal_solution = solver.primal_rounding_incremental(init_delta, delta_growth_rate, num_dual_iterations_in_primal_rounding, verbose)
throws the following error:
File "/home/jackokie/Program/anaconda/lib/python3.9/runpy.py", line 197, in _run_module_as_main
return _run_code(code, main_globals, None,
File "/home/jackokie/Program/anaconda/lib/python3.9/runpy.py", line 87, in _run_code
exec(code, run_globals)
File "/home/jackokie/.vscode-server/extensions/ms-python.python-2023.4.1/pythonFiles/lib/python/debugpy/adapter/../../debugpy/launcher/../../debugpy/main.py", line 39, in
Invoked with:
I just wish the work was more perfect. There is no hostility. Thanks!
You are right. I will work on getting these things in order in coming days.
OK. Keep in touch. Looking forward to the improvement of the job.
Another test question: The pyomo exported .lp file cannot be solved in the BDD library. The following is pyomo exported file: `* Source Pyomo model name=hello *\
min x3: +6 x1 +5 x2
s.t.
c_ux4: +1 x1 +1 x2 <= 5
c_ux5: +3 x1 +2 x2 <= 12
c_e_ONE_VAR_CONSTANT: ONE_VAR_CONSTANT = 1.0
bounds 0 <= x1 <= +inf 0 <= x2 <= +inf end`
I see many possible issues in the LP file.
c_e_ONE_VAR_CONSTANT: ONE_VAR_CONSTANT = 1.0
is redundant, please remove it. Subject To:
instead of s.t.
in the .LP format. See here. I have added python interface. Please check py-interface
Hi. The solver output a lower bound with many times iterations. But the lower bound is different with the Gurobi objective value. For example, the objective value is 402800 in Gurobi, but its lower bound is 189199.9 in the BDD output. I don't konw whether the lower bound can be regarded as the objective value in BDD. And, I still cannot acquire the solved results for the variables.
I try to solve 0-1 linear programming problem. I don't know how to acquire the solved binary variables. Whether the final solution of original problem is "obj", and "sol" in the following code ? If this is the case, the BDD solution is different from the Gurobi. In the Gurobi, the total number of 1 is 5 while it's 6 in the BDD solutions. In addition, the objective value in Gurobi is 39600 while it's 475200 in the BDD. So, I really don't know how to get the right solutions in the BDD.
The problem is attached in the following link. https://drive.google.com/file/d/1xmwVg0MQOzbLHZhKTwmVfMmqXdx_SR6k/view?usp=sharing
from BDD.bdd_solver_py import bdd_solver as bdd_solver
from BDD.bdd_solver_py import bdd_solver_options as bdd_solver_options
opts = bdd_solver_options("test.lp")
# Set solver options from preset categories:
opts.auto_set_parameters("fastdog_gpu") # valid options are "fastdog_cpu", "fastdog_gpu", "fastdog_hybrid"
opts.bdd_solver_type = bdd_solver_options.bdd_solver_types.mma_cuda
# Initialize solver:
solver = bdd_solver(opts)
# Solve dual problem:
solver.solve_dual()
assert solver.lower_bound() + 1e-5 >= -6.0
# Run primal heuristic:
obj, sol = solver.round()
assert obj == -6.0
fastdog_cpu
. obj
is the objective values of primal solution and sol
is the variable assignment.
If I have a million variables, can the solver work? Could you please explain how to build a problem file for the BDD?
In addition, the compile will break for the reason "/home/XXX/Downloads/BDD/include/run_solver_util.h(68): error: namespace "std" has no member "cout". If I add "# include" in the header file, the compile will work.