PulP adding constraints too slowly

Question

I have read this post

PuLP very slow when adding many constraints

and still remain oblivious to a solution.

def choose_lines_to_satisfy_image(lines_list_high_res, image_low_res, lines_to_low_res_matrix, allowed_diff_between_targe_pixel_and_result):
    problem = LpProblem("Solving Lines Discretely", LpMinimize)  # minimize or maximize doesn't matter
    problem += 0  # objective function must be added first. it is zero, because we are only looking for a feasable solution. nothing to optimize.

    number_of_lines = len(lines_list_high_res)
    lines_names_list = []

    for i in range(len(lines_list_high_res)):
        line_name = str(i)
        lines_names_list.append(line_name)

    print("len(lines_names_list)")
    print(len(lines_names_list))
    line_variables = LpVariable.dicts("line", lines_names_list, lowBound=0, upBound=1, cat=LpInteger)
    # print('dicts = ')
    # print(line_variables)#can't do this. python hangs. want it? spit it to a log file.

    num_of_lines, num_of_low_res_pixels = lines_to_low_res_matrix.shape
    if len(lines_list_high_res) != num_of_lines:
        print("oh crap")
        return

    # add constraints
    # each constraint is: |pixel-expected-value - pixel-actual-value| < allowed_diff_between_targe_pixel_and_result
    # which translates to 2 constraints:
    # 1) sum(lines coefficients through pixel) < pixel-expected-value + allowed_diff_between_targe_pixel_and_result
    # 2) sum(lines coefficients through pixel) < pixel-expected-value - allowed_diff_between_targe_pixel_and_result
    for pixel_low_res_ind in range(num_of_low_res_pixels):
        print("setting constraints for low res pixel # ", pixel_low_res_ind, " out of ", num_of_low_res_pixels)
        pixel_low_res_x, pixel_low_res_y = ind2sub(image_low_res.shape, pixel_low_res_ind)

        constraint_1_name = "Constraint 1 for pixel " + str(pixel_low_res_ind)
        constraint_2_name = "Constraint 2 for pixel " + str(pixel_low_res_ind)

        #TODO this should be done for only the lines that pass through the pixel. how shall I know which ones?
        constraint_predicate_1 = lpSum([line_variables[str(j)] * lines_to_low_res_matrix[j][pixel_low_res_ind] for j in range(num_of_lines)]) \
                                 <= image_low_res[pixel_low_res_x][pixel_low_res_y] + allowed_diff_between_targe_pixel_and_result
        #TODO this should be done for only the lines that pass through the pixel. how shall I know which ones?
        constraint_predicate_2 = lpSum([line_variables[str(j)] * lines_to_low_res_matrix[j][pixel_low_res_ind] for j in range(num_of_lines)]) \
                                 >= image_low_res[pixel_low_res_x][pixel_low_res_y] - allowed_diff_between_targe_pixel_and_result

        problem += constraint_predicate_1, constraint_1_name
        problem += constraint_predicate_2, constraint_2_name

    #TODO make this path relative
    print("writing problem to file")
    problem.writeLP("D:/git/stav/python/threadart/linear_problems/problem.lp")
    print("solving problem")
    problem.solve(PULP_CBC_CMD(msg=0))

I have used lpSum and still the creation of constraints takes over an hour. Also, there is no indication of the progression of the solution.

I have 4096 constraints, each containing about 8500 variables. They are sparse to some extent, but I did not mention that anywhere (Should I?)

Please tell me how I can speed up the problem creation process to something more realistic.

I wouldn't mind creating some file the Pulp would read myself (i noticed there is a problem.write () method, but no problem.read())

Thanks!

First profile your program (e.g. using line_profiler) to check what exactly is taking that long. Then you can think about changes and in the worst-case, leaving pulp for a more low-level representation (e.g. using cylp). The *no indication of the progression of the solution* is probably due to ```mgs=0``` (if we are talking about solver-verbosity here). — sascha, Mar 21 '18 at 23:56
@sascha i let it run, and it took about 16 hours on my machine to solve the system. 1. it gave some negative variables (Didn't I tell it to limit to between 0 and 1?) 2. if not `mgs=0`, then what? the doc doesn't say — Gulzar, Mar 22 '18 at 14:11
Obviously msg=1 or higher (which would be evaluated as true if a boolean would be needed). The remainding stuff did also not really address my comment. Be more precise: what exactly takes how long. If profiling is infeasible because of 16h, make the problem smaller. — sascha, Mar 22 '18 at 14:14
First start on a smaller instance of your problem, then you can try and increase the speed. It sounds like you need to use the sparsity of you problem with and think of a way to only add constraints form lines that pass through your pixel. Also it seems that your problem is infeasible so make sure you check the status of the problem at the end. It probably is infeasible because you have the formulation wrong, To correct your formulation I suggest you start with a smaller problem and try to see what is going on. — Stuart Mitchell, Mar 22 '18 at 20:58

PulP adding constraints too slowly

0 Answers0