Multicriteria Decision Making¶
Goal programming is a variation of linear programming considering more than one objective (goals) in the objective function. Goal programming solutions do not always achieve all goals and they are not optimal; they achieve the best or most satisfactory solution possible.
Goal Constraint Requirements:
All goal constraints are equalities that include deviational variables \(d^-\) and \(d^+\)
A negative deviational variable, \(d^-\), is the amount by which a goal level is under-achieved
A positive deviational variable, \(d^+\), is the amount by which a goal level is exceeded
At least one or both deviational variables in a goal constraint must equal zero
The objective function seeks to minimize the deviation from the respective goals in the order of the goal priorities.
Goal programming example:¶
Solve the following problem:
\[\begin{split}
\begin{align}
&\text{min}\\
&\qquad z=P_1d_1^-,P_2d_2^-,P_3d_3^+,P_4d_1^+\\
&\text{s.t.}\\
&\qquad x_1+2x_2+d_1^--d_1^+=40\\
&\qquad 40x_1+50x_2+d_2^--d_2^+=1600\\
&\qquad 4x_1+3x_2+d_3^--d_3^+=120\\
&\qquad x_i,d_j^-,d_j^+ \ge 0~ \text{and integer}
\end{align}
\end{split}\]
!pip install gurobipy
# Import gurobi library
from gurobipy import * # This command imports the Gurobi functions and classes.
import numpy as np
m = Model('multiobj')
# Add Variables
x = m.addVars(range(2), name='x', lb=0, vtype = GRB.INTEGER)
dm = m.addVars(range(3), name='dm', lb=0, vtype = GRB.INTEGER)
dp = m.addVars(range(3), name='dp', lb=0, vtype = GRB.INTEGER)
#totSlack = m.addVar(name='totSlack')
m.update()
# Add Constraints
c1 = m.addConstr(1 *x[0] + 2*x[1] + 1*dm[0] - 1*dp[0] == 40)
c2 = m.addConstr(40*x[0] + 50*x[1] + 1*dm[1] - 1*dp[1] == 1600)
c3 = m.addConstr(4 *x[0] + 3*x[1] + 1*dm[2] - 1*dp[2] == 120)
# Add Objective Function
m.ModelSense = GRB.MINIMIZE
m.setObjectiveN(dm[0], index=0, priority=3)
m.setObjectiveN(dm[1], index=1, priority=2)
m.setObjectiveN(dp[2], index=2, priority=1)
m.setObjectiveN(dp[0], index=3, priority=0)
# Optimize Model
m.optimize()
# Output formatted solution
for v in m.getVars():
print(v.varName, v.x)
#print('Obj :', m.objVal)
Collecting gurobipy
Downloading gurobipy-9.5.0-cp37-cp37m-manylinux2014_x86_64.whl (11.5 MB)
|████████████████████████████████| 11.5 MB 12.7 MB/s
?25hInstalling collected packages: gurobipy
Successfully installed gurobipy-9.5.0
Restricted license - for non-production use only - expires 2023-10-25
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)
Thread count: 1 physical cores, 2 logical processors, using up to 2 threads
Optimize a model with 3 rows, 8 columns and 12 nonzeros
Model fingerprint: 0xedfe4e5b
Variable types: 0 continuous, 8 integer (0 binary)
Coefficient statistics:
Matrix range [1e+00, 5e+01]
Objective range [1e+00, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [4e+01, 2e+03]
---------------------------------------------------------------------------
Multi-objectives: starting optimization with 4 objectives ...
---------------------------------------------------------------------------
Multi-objectives: applying initial presolve ...
---------------------------------------------------------------------------
Presolve time: 0.00s
Presolved: 3 rows and 8 columns
---------------------------------------------------------------------------
Multi-objectives: optimize objective 1 () ...
---------------------------------------------------------------------------
Presolve removed 3 rows and 8 columns
Presolve time: 0.00s
Presolve: All rows and columns removed
Explored 0 nodes (0 simplex iterations) in 0.07 seconds (0.00 work units)
Thread count was 1 (of 2 available processors)
Solution count 1: 0
Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
---------------------------------------------------------------------------
Multi-objectives: optimize objective 2 () ...
---------------------------------------------------------------------------
Loaded user MIP start with objective 0
Explored 0 nodes (0 simplex iterations) in 0.11 seconds (0.00 work units)
Thread count was 1 (of 2 available processors)
Solution count 1: 0
Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
---------------------------------------------------------------------------
Multi-objectives: optimize objective 3 () ...
---------------------------------------------------------------------------
Loaded user MIP start with objective 40
Presolve removed 5 rows and 8 columns
Presolve time: 0.00s
Presolve: All rows and columns removed
Explored 0 nodes (0 simplex iterations) in 0.14 seconds (0.00 work units)
Thread count was 1 (of 2 available processors)
Solution count 2: 0 40
Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
---------------------------------------------------------------------------
Multi-objectives: optimize objective 4 () ...
---------------------------------------------------------------------------
Loaded user MIP start with objective 24
Presolve removed 4 rows and 6 columns
Presolve time: 0.00s
Presolved: 2 rows, 2 columns, 4 nonzeros
Variable types: 0 continuous, 2 integer (0 binary)
Root relaxation: objective 1.500000e+01, 0 iterations, 0.00 seconds (0.00 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
* 0 0 0 15.0000000 15.00000 0.00% - 0s
Explored 1 nodes (0 simplex iterations) in 0.18 seconds (0.00 work units)
Thread count was 2 (of 2 available processors)
Solution count 2: 15 24
Optimal solution found (tolerance 1.00e-04)
Best objective 1.500000000000e+01, best bound 1.500000000000e+01, gap 0.0000%
---------------------------------------------------------------------------
Multi-objectives: solved in 0.24 seconds (0.00 work units), solution count 3
x[0] 15.0
x[1] 20.0
dm[0] 0.0
dm[1] 0.0
dm[2] 0.0
dp[0] 15.0
dp[1] 0.0
dp[2] 0.0
Altered goal programming example:¶
Solve the following problem:
\[\begin{split}
\begin{align}
&\text{min}\\
&\qquad z=P_1d_1^-,P_2d_2^-,P_3d_3^+,P_4d_1^+,4P_5d_5^-+5P_5d_6^-\\
&\text{s.t.}\\
&\qquad x_1+2x_2+d_1^--d_1^+=40\\
&\qquad 40x_1+50x_2+d_2^--d_2^+=1600\\
&\qquad 4x_1+3x_2+d_3^--d_3^+=120\\
&\qquad d_1^++d_4^--d_4^+=10 \\
&\qquad x_1+d_5^-=30\\
&\qquad x_2+d_6^-=20\\
&\qquad x_i,d_j^-,d_j^+ \ge 0~ \text{and integer}
\end{align}
\end{split}\]
from gurobipy import *
m = Model('multiobj')
# Add Variables
x = m.addVars(range(2), name='x', lb=0, vtype = GRB.INTEGER)
dm = m.addVars(range(6), name='dm', lb=0, vtype = GRB.INTEGER)
dp = m.addVars(range(4), name='dp', lb=0, vtype = GRB.INTEGER)
#totSlack = m.addVar(name='totSlack')
m.update()
# Add Constraints
c1 = m.addConstr(1 *x[0] + 2 *x[1] + 1*dm[0] - 1*dp[0] == 40)
c2 = m.addConstr(40*x[0] + 50*x[1] + 1*dm[1] - 1*dp[1] == 1600)
c3 = m.addConstr(4 *x[0] + 3 *x[1] + 1*dm[2] - 1*dp[2] == 120)
c4 = m.addConstr( 1*dp[0] + 1*dm[3] - 1*dp[3] == 10)
c5 = m.addConstr(1 *x[0] + 1*dm[4] == 30)
c6 = m.addConstr( 1 *x[1] + 1*dm[5] == 20)
# Add Objective Function
m.ModelSense = GRB.MINIMIZE
m.setObjectiveN(dm[0], index=0, priority=4)
m.setObjectiveN(dm[1], index=1, priority=3)
m.setObjectiveN(dp[2], index=2, priority=2)
m.setObjectiveN(dp[3], index=3, priority=1)
m.setObjectiveN(4*dm[4]+5*dm[5], index=4, priority=0)
# Optimize Model
m.optimize()
# Output formatted solution
for v in m.getVars():
print(v.varName, v.x)
#print('Obj :', m.objVal)
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)
Thread count: 1 physical cores, 2 logical processors, using up to 2 threads
Optimize a model with 6 rows, 12 columns and 19 nonzeros
Model fingerprint: 0x2a5ffb2a
Variable types: 0 continuous, 12 integer (0 binary)
Coefficient statistics:
Matrix range [1e+00, 5e+01]
Objective range [1e+00, 5e+00]
Bounds range [0e+00, 0e+00]
RHS range [1e+01, 2e+03]
---------------------------------------------------------------------------
Multi-objectives: starting optimization with 5 objectives ...
---------------------------------------------------------------------------
Multi-objectives: applying initial presolve ...
---------------------------------------------------------------------------
Presolve removed 2 rows and 2 columns
Presolve time: 0.00s
Presolved: 4 rows and 10 columns
---------------------------------------------------------------------------
Multi-objectives: optimize objective 1 () ...
---------------------------------------------------------------------------
Presolve removed 4 rows and 10 columns
Presolve time: 0.00s
Presolve: All rows and columns removed
Explored 0 nodes (0 simplex iterations) in 0.05 seconds (0.00 work units)
Thread count was 1 (of 2 available processors)
Solution count 1: 0
Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
---------------------------------------------------------------------------
Multi-objectives: optimize objective 2 () ...
---------------------------------------------------------------------------
Loaded user MIP start with objective 0
Explored 0 nodes (0 simplex iterations) in 0.07 seconds (0.00 work units)
Thread count was 1 (of 2 available processors)
Solution count 1: 0
Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
---------------------------------------------------------------------------
Multi-objectives: optimize objective 3 () ...
---------------------------------------------------------------------------
Loaded user MIP start with objective 60
Presolve removed 6 rows and 10 columns
Presolve time: 0.00s
Presolve: All rows and columns removed
Explored 0 nodes (0 simplex iterations) in 0.10 seconds (0.00 work units)
Thread count was 1 (of 2 available processors)
Solution count 2: 0 60
Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
---------------------------------------------------------------------------
Multi-objectives: optimize objective 4 () ...
---------------------------------------------------------------------------
Loaded user MIP start with objective 5
Presolve removed 7 rows and 10 columns
Presolve time: 0.00s
Presolve: All rows and columns removed
Explored 0 nodes (0 simplex iterations) in 0.13 seconds (0.00 work units)
Thread count was 1 (of 2 available processors)
Solution count 1: 5
Optimal solution found (tolerance 1.00e-04)
Best objective 5.000000000000e+00, best bound 5.000000000000e+00, gap 0.0000%
---------------------------------------------------------------------------
Multi-objectives: optimize objective 5 () ...
---------------------------------------------------------------------------
Loaded user MIP start with objective 60
Presolve removed 8 rows and 10 columns
Presolve time: 0.00s
Presolve: All rows and columns removed
Explored 0 nodes (0 simplex iterations) in 0.16 seconds (0.00 work units)
Thread count was 1 (of 2 available processors)
Solution count 1: 60
Optimal solution found (tolerance 1.00e-04)
Best objective 6.000000000000e+01, best bound 6.000000000000e+01, gap 0.0000%
---------------------------------------------------------------------------
Multi-objectives: solved in 0.18 seconds (0.00 work units), solution count 2
x[0] 15.0
x[1] 20.0
dm[0] 0.0
dm[1] 0.0
dm[2] 0.0
dm[3] 0.0
dm[4] 15.0
dm[5] 0.0
dp[0] 15.0
dp[1] 0.0
dp[2] 0.0
dp[3] 5.0
Problem Example: C9Q8¶
Solve the following goal programming model:
\[\begin{split}
\begin{align}
&\text{min}\\
&\qquad z=P_1d_1^-+P_1d_1^+,P_2d_2^-,P_3d_3^-,3P_4d_2^++5P_4d_3^+\\
&\text{s.t.}\\
&\qquad x_1+x_2+d_1^--d_1^+=800\\
&\qquad 5x_1+d_2^--d_2^+=2500\\
&\qquad 3x_2+d_3^--d_3^+=1400\\
&\qquad x_i,d_j^-,d_j^+ \ge 0~ \text{and integer}
\end{align}
\end{split}\]
from gurobipy import *
m = Model('C9Q8')
# Add Variables
x = m.addVars(range(2), name='x', lb=0, vtype = GRB.INTEGER)
dm = m.addVars(range(3), name='dm', lb=0, vtype = GRB.INTEGER)
dp = m.addVars(range(3), name='dp', lb=0, vtype = GRB.INTEGER)
#totSlack = m.addVar(name='totSlack')
m.update()
# Add Constraints
c1 = m.addConstr(1*x[0] + 1*x[1] + 1*dm[0] - 1*dp[0] == 800)
c2 = m.addConstr(5*x[0] + 1*dm[1] - 1*dp[1] == 2500)
c3 = m.addConstr( 3*x[1] + 1*dm[2] - 1*dp[2] == 1400)
# Add Objective Function
m.ModelSense = GRB.MINIMIZE
m.setObjectiveN(dm[0]+dp[0], index=0, priority=3)
m.setObjectiveN(dm[1], index=1, priority=2)
m.setObjectiveN(dm[2], index=2, priority=1)
m.setObjectiveN(3*dp[1]+5*dp[2], index=3, priority=0)
# Optimize Model
m.optimize()
# Output formatted solution
for v in m.getVars():
print(v.varName, v.x)
#print('Obj :', m.objVal)
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)
Thread count: 1 physical cores, 2 logical processors, using up to 2 threads
Optimize a model with 3 rows, 8 columns and 10 nonzeros
Model fingerprint: 0xa4b28e54
Variable types: 0 continuous, 8 integer (0 binary)
Coefficient statistics:
Matrix range [1e+00, 5e+00]
Objective range [1e+00, 5e+00]
Bounds range [0e+00, 0e+00]
RHS range [8e+02, 2e+03]
---------------------------------------------------------------------------
Multi-objectives: starting optimization with 4 objectives ...
---------------------------------------------------------------------------
Multi-objectives: applying initial presolve ...
---------------------------------------------------------------------------
Presolve time: 0.00s
Presolved: 3 rows and 8 columns
---------------------------------------------------------------------------
Multi-objectives: optimize objective 1 () ...
---------------------------------------------------------------------------
Presolve removed 3 rows and 8 columns
Presolve time: 0.00s
Presolve: All rows and columns removed
Explored 0 nodes (0 simplex iterations) in 0.04 seconds (0.00 work units)
Thread count was 1 (of 2 available processors)
Solution count 1: 0
Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
---------------------------------------------------------------------------
Multi-objectives: optimize objective 2 () ...
---------------------------------------------------------------------------
Loaded user MIP start with objective 0
Explored 0 nodes (0 simplex iterations) in 0.06 seconds (0.00 work units)
Thread count was 1 (of 2 available processors)
Solution count 1: 0
Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
---------------------------------------------------------------------------
Multi-objectives: optimize objective 3 () ...
---------------------------------------------------------------------------
Loaded user MIP start with objective 1400
Presolve removed 5 rows and 8 columns
Presolve time: 0.00s
Presolve: All rows and columns removed
Explored 0 nodes (0 simplex iterations) in 0.09 seconds (0.00 work units)
Thread count was 1 (of 2 available processors)
Solution count 2: 500 1400
Optimal solution found (tolerance 1.00e-04)
Best objective 5.000000000000e+02, best bound 5.000000000000e+02, gap 0.0000%
---------------------------------------------------------------------------
Multi-objectives: optimize objective 4 () ...
---------------------------------------------------------------------------
Loaded user MIP start with objective 0
Explored 0 nodes (0 simplex iterations) in 0.10 seconds (0.00 work units)
Thread count was 1 (of 2 available processors)
Solution count 1: 0
Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
---------------------------------------------------------------------------
Multi-objectives: solved in 0.12 seconds (0.00 work units), solution count 2
x[0] 500.0
x[1] 300.0
dm[0] 0.0
dm[1] 0.0
dm[2] 500.0
dp[0] 0.0
dp[1] 0.0
dp[2] 0.0
Problem Example: C9Q10¶
Solve the following goal programming model:
\[\begin{split}
\begin{align}
&\text{min}\\
&\qquad z=P_1d_1^-,5P_2d_2^-+2P_2d_3^-,P_3d_4^+\\
&\text{s.t.}\\
&\qquad 8x_1+6x_2+d_1^--d_1^+=480\\
&\qquad x_1+d_2^--d_2^+=40\\
&\qquad x_2+d_3^--d_3^+=50\\
&\qquad d_1^++d_4^--d_4^+=20\\
&\qquad x_i,d_j^-,d_j^+ \ge 0~ \text{and integer}
\end{align}
\end{split}\]
from gurobipy import *
m = Model('C9Q10')
# Add Variables
x = m.addVars(range(2), name='x', lb=0, vtype = GRB.INTEGER)
dm = m.addVars(range(4), name='dm', lb=0, vtype = GRB.INTEGER)
dp = m.addVars(range(4), name='dp', lb=0, vtype = GRB.INTEGER)
#totSlack = m.addVar(name='totSlack')
m.update()
# Add Constraints
c1 = m.addConstr(8*x[0] + 6*x[1] + 1*dm[0] - 1*dp[0] == 480)
c2 = m.addConstr(1*x[0] + 1*dm[1] - 1*dp[1] == 40)
c3 = m.addConstr( 1*x[1] + 1*dm[2] - 1*dp[2] == 50)
c4 = m.addConstr( 1*dp[0] + 1*dm[3] - 1*dp[3] == 20)
# Add Objective Function
m.ModelSense = GRB.MINIMIZE
m.setObjectiveN(dm[0], index=0, priority=2)
m.setObjectiveN(5*dm[1]+2*dm[2], index=1, priority=1)
m.setObjectiveN(dp[3], index=2, priority=0)
# Optimize Model
m.optimize()
# Output formatted solution
for v in m.getVars():
print(v.varName, v.x)
#print('Obj :', m.objVal)
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)
Thread count: 1 physical cores, 2 logical processors, using up to 2 threads
Optimize a model with 4 rows, 10 columns and 13 nonzeros
Model fingerprint: 0x30f2088f
Variable types: 0 continuous, 10 integer (0 binary)
Coefficient statistics:
Matrix range [1e+00, 8e+00]
Objective range [1e+00, 5e+00]
Bounds range [0e+00, 0e+00]
RHS range [2e+01, 5e+02]
---------------------------------------------------------------------------
Multi-objectives: starting optimization with 3 objectives ...
---------------------------------------------------------------------------
Multi-objectives: applying initial presolve ...
---------------------------------------------------------------------------
Presolve time: 0.00s
Presolved: 4 rows and 10 columns
---------------------------------------------------------------------------
Multi-objectives: optimize objective 1 () ...
---------------------------------------------------------------------------
Presolve removed 4 rows and 10 columns
Presolve time: 0.00s
Presolve: All rows and columns removed
Explored 0 nodes (0 simplex iterations) in 0.05 seconds (0.00 work units)
Thread count was 1 (of 2 available processors)
Solution count 1: 0
Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
---------------------------------------------------------------------------
Multi-objectives: optimize objective 2 () ...
---------------------------------------------------------------------------
Loaded user MIP start with objective 100
Presolve removed 5 rows and 10 columns
Presolve time: 0.00s
Presolve: All rows and columns removed
Explored 0 nodes (0 simplex iterations) in 0.08 seconds (0.00 work units)
Thread count was 1 (of 2 available processors)
Solution count 2: 0 100
Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
---------------------------------------------------------------------------
Multi-objectives: optimize objective 3 () ...
---------------------------------------------------------------------------
Loaded user MIP start with objective 120
Presolve removed 6 rows and 10 columns
Presolve time: 0.00s
Presolve: All rows and columns removed
Explored 0 nodes (0 simplex iterations) in 0.10 seconds (0.00 work units)
Thread count was 1 (of 2 available processors)
Solution count 1: 120
Optimal solution found (tolerance 1.00e-04)
Best objective 1.200000000000e+02, best bound 1.200000000000e+02, gap 0.0000%
---------------------------------------------------------------------------
Multi-objectives: solved in 0.11 seconds (0.00 work units), solution count 2
x[0] 40.0
x[1] 50.0
dm[0] 0.0
dm[1] -0.0
dm[2] -0.0
dm[3] 0.0
dp[0] 140.0
dp[1] 0.0
dp[2] 0.0
dp[3] 120.0