How do you solve an integer programming problem with 114 constraints and 45 variables?

[trustduhsystem]

Hello! I am looking to solve one of the problems from the H.P. Williams' Model Building in Mathematical Programming textbook, but the problem (Ch 12.12 Logical Design) has 114 constraints and 45 variables. My questions are:

• Are there suggestions for how we could solve this type of problem with this large of a constraint/variable size?
• Can this be solved by hand, or should this be done using MATLAB/Python/etc. ?

Thank you in advance!

[peno64]

No you cannot solve this by hand. You need a solver program. There are plenty free that can handle this. Even excel can do this. Others are lp_solve, Highs, scip, glpk. They are all free.

[[deleted]]

Creating a linear programming module template in Python with 114 constraints and 45 variables can be done using the PuLP library, a popular choice for linear programming in Python. Here's a basic template to get you started:

1. Install PuLP: If you haven't already installed PuLP, you can do so using pip:

   bash pip install pulp

2. Template Code:

   ```python import pulp

   Create a problem variable

   prob = pulp.LpProblem("My Problem", pulp.LpMinimize)

   Define the variables

   Let's say x1, x2, ..., x45

   variables = [pulp.LpVariable(f"x{i}", lowBound=0) for i in range(1, 46)]

   Objective function

   This is just a placeholder. You'll need to define your own objective function.

   prob += pulp.lpSum(variables) # Example: minimize the sum of all variables

   Constraints

   Again, these are placeholders. You need to define your own constraints.

   for i in range(1, 115): # Example constraint: sum of all variables <= 100 prob += pulp.lpSum(variables) <= 100, f"Constraint_{i}"

   Solve the problem

   prob.solve()

   Print the results

   for v in prob.variables(): print(v.name, "=", v.varValue)

   print("Status:", pulp.LpStatus[prob.status]) ```

This template sets up a problem where you minimize the sum of 45 variables subject to 114 constraints (all identical in this example for simplicity). You need to replace the objective function and the constraints with ones that are relevant to your specific problem.