May-14-2023, 11:02 PM
I have a relatively simple binary integer optimization problem and I am using Google OR-Tools' linear solver. I started the project in C#, but have since decided to port to Python and finish from there. The problem I having is making sure that the solution uses exactly n elements from those available. In C#, this line had the desired result:
solver.Add(solver.LinearExprArrayHelper.Sum(x) == n);What I believe to be the equivalent line in Python, results in no optimal solution to the problem:
solver.Add(solver.Sum(x) == n)The full code is based largely on the example on the OR-Tools page for mixed integer programming using arrays to define the model. Any guidance would be much appreciated. Thanks!
from ortools.linear_solver import pywraplp import random def create_data_model(points, salaries, capacity, num_vars, num_constraints): """Stores the data for the problem.""" data = {'constraint_coeffs': [salaries], 'bounds': [capacity], 'obj_coeffs': points, 'num_vars': num_vars, 'num_constraints': num_constraints} return data def main(): points = [] for i in range(20): points.append(random.randint(5, 40)) salaries = [] for i in range(20): salaries.append(round_nearest_hundred(random.randint(5000, 10000))) data = create_data_model(points, salaries, 35000, len(salaries), 1) # Create the mip solver with the SCIP backend. solver = pywraplp.Solver.CreateSolver('SCIP') if not solver: return x = {} for j in range(data['num_vars']): x[j] = solver.IntVar(0, 1, 'x[%i]' % j) print('Number of variables =', solver.NumVariables()) for i in range(data['num_constraints']): constraint = solver.RowConstraint(0, data['bounds'][i], '') for j in range(data['num_vars']): constraint.SetCoefficient(x[j], data['constraint_coeffs'][i][j]) print('Number of constraints =', solver.NumConstraints()) # In Python, you can also set the constraints as follows. # for i in range(data['num_constraints']): # constraint_expr = \ # [data['constraint_coeffs'][i][j] * x[j] for j in range(data['num_vars'])] # solver.Add(sum(constraint_expr) <= data['bounds'][i]) solver.Add(solver.Sum(x) == 5) # <-- This is the line causing me issues. objective = solver.Objective() for j in range(data['num_vars']): objective.SetCoefficient(x[j], data['obj_coeffs'][j]) objective.SetMaximization() # In Python, you can also set the objective as follows. # obj_expr = [data['obj_coeffs'][j] * x[j] for j in range(data['num_vars'])] # solver.Maximize(solver.Sum(obj_expr)) status = solver.Solve() if status == pywraplp.Solver.OPTIMAL: print('Objective value =', solver.Objective().Value()) for j in range(data['num_vars']): print(x[j].name(), ' = ', x[j].solution_value()) print() print('Problem solved in %f milliseconds' % solver.wall_time()) print('Problem solved in %d iterations' % solver.iterations()) print('Problem solved in %d branch-and-bound nodes' % solver.nodes()) else: print('The problem does not have an optimal solution.') def round_nearest_hundred(a: int): return round(a / 100) * 100 if __name__ == '__main__': main()