dminghao / business_analysis_linear_programing

Linear Programing Implementation

In this project we use two python packages (SciPy, PuLP) to solve Linear Programing problems.

Table of Contents

• Getting Started
  • Install
  • Troubleshoot
• Implementation
  • SciPy
    • HowTo
    • Example
  • PuLP
    • HowTo
    • Example
• About
  • Contributing
  • References
  • License

This repo consist of the original ICE2 MSword document and the correct answer MSexcel document implemented in MS Excel. For some problems in the ICE2, both implementation methods are used, and some others are only implemented with one. Please check out the Contributing document for contributing to this repo (implementing more methods, etc.).

Getting Started

Install

Require Python 3 or higher

• Install SciPy

  pip install SciPy

• Install PuLP

  pip install pulp

Troubleshoot

If encounter error:

• Solver not found
• NoneType Error

PuLP solver is missing -> Install PuLP solver

• For Mac:

  brew install glpk

• For Conda environment:

  conda install -c conda-forge glpk

Implementation

SciPy

SciPy (pronounced “Sigh Pie”) is open-source software for mathematics, science, and engineering.

HowTo

Use linprog to minimize a linear objective function subject to linear equality and inequality constraints. For maximization, invert objective function's coefficients.

res = scipy.optimize.linprog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, bounds=None, method='revised simplex', callback=None, options=None, x0=None)

NOTE: Below is a lite version of linprog function's official documentation

Parameters

Param Name	Data Type	Required	Explanation
c	1-D array	✔	The coefficients of the linear objective function to be minimized.
A_ub	2-D array	❌	The inequality constraint matrix. Each row of A_ub specifies the coefficients of a linear inequality constraint on x.
b_ub	1-D array	❌	The inequality constraint vector. Each element represents an upper bound on the corresponding value of A_ub @ x
A_eq	2-D array	❌	The equality constraint matrix. Each row of A_eq specifies the coefficients of a linear equality constraint on x.
b_eq	1-D array	❌	The equality constraint vector. Each element of A_eq @ x must equal the corresponding element of b_eq.
bounds	Tuple array	❌	A sequence of (min, max) pairs for each element in x, defining the minimum and maximum values of that decision variable. Use None to indicate that there is no bound. By default, bounds are (0, None) (all decision variables are non-negative). If a single tuple (min, max) is provided, then min and max will serve as bounds for all decision variables.
method	Enumerated	❌	{interior-point, revised simplex, simplex}
callback	Callable	❌	If a callback function is provided, it will be called at least once per iteration of the algorithm. The callback function must accept a single scipy.optimize.OptimizeResult object.
options	dict	❌	maxiter : int -> Maximum number of iterations to perform. disp : bool -> Set to True to print convergence messages. autoscale : bool -> Set to True to automatically perform equilibration. Consider using this option if the numerical values in theconstraints are separated by several orders of magnitude. presolve : bool -> Set to False to disable automatic presolve. rr : bool -> Set to False to disable automatic redundancy removal.
x0	1-D array	❌	Guess values of the decision variables, which will be refined by the optimization algorithm. This argument is currently used only by the revised simplex method, and can only be used if x0 represents a basic feasible solution.

Returns

The linprog function returns a scipy.optimize.OptimizeResult class, consisting of the fields:

Atribute	Data Type	Explianation
x	1-D array	The current solution vector.
fun	float	The current value of the objective function c @ x.
success	bool	True when the algorithm has completed successfully.
slack	1-D array	The (nominally positive) values of the slack, b_ub - A_ub @ x.
con	1-D array	The (nominally zero) residuals of the equality constraints, b_eq - A_eq @ x.
phase	int	The phase of the algorithm being executed.
status	int	0 -> Optimization proceeding nominally. 1 -> Iteration limit reached. 2 -> Problem appears to be infeasible. 3 -> Problem appears to be unbounded. 4 -> Numerical difficulties encountered.
nit	int	The current iteration number.
message	str	A string descriptor of the algorithm status.

Example

from scipy.optimize import linprog

linprog is a linear programming function in the optimize package of SciPy library. We will use the question 1(c) as an tutorial example. The example objective function is min[-4x-5y]

obj = [-4, -5]

Defining the objective function's coefficients, and in this case, there are two independent variables (x, y) in this objective function.

lhs_ineq = [[4,  5], 
            [6,  3], 
            [4, 10], 
            [1, 0], 
            [0, 1]] 

Defining the left hand side of the constraints

rhs_ineq = [101,            
            120,
            160, 
            40, 
            30] 

Defining the right hand side of the constraints. The scipy set the inequality as <= by default. If you want to plug in an >= inequality relationship, simply change the signs to negative.

bnd = [(0, float("inf")),
       (0, float("inf"))]

Defining the boundary of the two decision veriabales. If you have multiple desicion veriables, simply add more boundries in the bnd=[ ]

opt = linprog(c=obj3, A_ub=lhs_ineq, b_ub=rhs_ineq,
                bounds=bnd,
               method="simplex")

Defining the opt in order to give the scipy a sense of what we problem are solving at all. Print "opt" to see the optimal solution for the question.

     con: array([], dtype=float64)
     fun: -101.0
 message: 'Optimization terminated successfully.'
     nit: 5
   slack: array([ 0. , 21.6,  0. , 29.5, 18.2])
  status: 0
 success: True
       x: array([10.5, 11.8])

Check the results. If the success is True, then the scipy find an optimal solution for you. If that is false, there are multiple reasons. The first, you might enter the wrong constraints. Second, there might no optimal solution in the fesiable region of the constraints you set.

PuLP

PuLP is an LP modeler written in Python. PuLP can generate MPS or LP files and use external libraries (GLPK, CPLEX, etc.) to solve linear problems.

HowTo

Use LpProblem to model a maximize or minimize linear problem subject to linear equality and inequality constraints.

NOTE: Below is a lite version of PuLP libary's official documentation

Constants

• LpSenses

  Key	Str Value	Int Value
  LpMaximize	“Maximize”	-1
  LpMinimize	“Minimize”	1

• LpStatus

  Key	Str Value	Int Value
  LpStatusOptimal	“Optimal”	1
  LpStatusNotSolved	“Not Solved”	0
  LpStatusInfeasible	“Infeasible”	-1
  LpStatusUnbounded	“Unbounded”	-2
  LpStatusUndefined	“Undefined”	-3

• LpConstraintSenses

  Key	Str Value	Int Value
  LpConstraintEQ	“==”	0
  LpConstraintLE	“<=”	-1
  LpConstraintGE	“>=”	1

Classes

• LpProblem
  • Parameters
    • name -> name of the problem used in the output .lp file
    • sense -> of the LP problem objective. Either LpMinimize (default) or LpMaximize.
  • Returns -> An LP Problem model/object
• LpVariable
  • Parameters
    • name -> The name of the variable used in the output .lp file
    • lowBound -> The lower bound on this variable’s range. Default is negative infinity
    • upBound -> The upper bound on this variable’s range. Default is positive infinity
    • cat -> The category this variable is in, LpInteger, LpBinary or LpContinuous(default)
    • e -> Used for column based modelling: relates to the variable’s existence in the objective function and constraints
  • Returns -> An LP Variable object
• LpAffineExpression
  • A linear combination of LpVariable
  • Parameters
    • e
      • None -> i.e. None => constant
      • (LpVariable,coefficient) list -> e.g. "[(x1,10),(x2,-15)]" => 10*x1 + -15*x2 + constant
    • constant -> 0 (default)
    • name -> The name of expression used in the output .lp file
  • Returns -> An LP Expression object
• LpConstraint
  • Parameters
    • e -> an instance of LpAffineExpression
    • sense -> LpConstraintEQ, LpConstraintGE, or LpConstraintLE (0, 1, or -1)
    • name -> The name of constraint used in the output .lp file
    • rhs -> numerical value of constraint target
  • Returns -> An Lp Constraint object
• lpSum
  • Takes in a list of LpAffineExpression or LpVariable and combined everything to one LpAffineExpression

Procedure

1. Initiate a LpProblem with one of the LpSenses const
2. Define LpVariable(s)
3. Initiate a LpAffineExpression with LpVariable(s) and corresponding coefficients as the objective function
4. LpProblem += objective function
5. Define LpConstraint(s) with LpAffineExpression and LpConstraintSenses as problem constraints
6. foreach problem constraints -> LpProblem += constraint
7. print(LpProblem)

Example

from pulp import LpMaximize, LpProblem, LpStatus, lpSum, LpVariable

import necessary functions from pulp library, where LpMaximize is the maximizing objective model for lp problem.

The first step is to initialize an instance of LpProblem to represent model

# Create the model
model = LpProblem(name="dog_cat_food_profit", sense=LpMaximize)

X1 = bags of Dog food to produce
X2 = bags of Cat food to produce

# Initialize the decision variables
x = LpVariable(name="X1", lowBound=0) 
y = LpVariable(name="X2", lowBound=0)

Add the objective function to the model MAX: 4 X1 + 5 X2

obj_func = 4 * x + 5 * y
model += obj_func

Add the constraints to the model

4 X1 + 5 X2 ≤100 (meat)

6 X1 + 3 X2 ≤120 (corns)

4 X1 + 10 X2 ≤ 160 (filler)

X1 ≤ 40 (Dog food demand) and X2 ≤ 30 (Cat food demand)

model += (4*x + 5*y <= 101, "meat_constraint") 
model += (4*x + 5*y <= 101, "meat_constraint") 
model += (4*x + 10*y <= 160, "filler_constraint")
model += (x <= 40, "dog_food_constraint")
model += (y <= 30, "cat_food_constraint")

Below is the result output

dog_cat_food_profit:
MAXIMIZE
4*X1 + 5*X2 + 0
SUBJECT TO
meat_constraint: 4 X1 + 5 X2 <= 101

corns_constraint: 6 X1 + 3 X2 <= 120

filler_constraint: 4 X1 + 10 X2 <= 160

dog_food_constraint: X1 <= 40

cat_food_constraint: X2 <= 30

VARIABLES
X1 Continuous
X2 Continuous

About

This project was initiated by @DMinghao @HLiu-970725 @LYLwithDCT @ReynaYC

Contributing

Please check out the CONTRIBUTING document

License

By contributing, you agree that your contributions will be licensed under its MIT License.

References

• https://www.scipy.org/
• https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.html#scipy.optimize.linprog
• https://github.com/coin-or/pulp
• https://coin-or.github.io/pulp/
• http://www.gnu.org/software/glpk/glpk.html