Optimization_Techniques/integer_programming_problem.py at main · HiraMohammedK/Optimization_Techniques · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
# -*- coding: utf-8 -*-
"""integer_programming_problem.ipynb

Automatically generated by Colaboratory.

Original file is located at
    https://colab.research.google.com/drive/1m5NA0QOxlGXwWy-7XXC3YyoXejhbKuFo
"""

def print_table(num_constraints, num_variables, table):
    for i in range(num_constraints + 1):
        for j in range(num_variables + 1):
            print(f"{table[i][j]:.2f}\t", end="")
        print()
    print()

def find_fractional_index(num_variables, solution):
    for i in range(num_variables):
        fractional_part = solution[i] - int(solution[i])
        if 0 < fractional_part < 1:
            return i
    return -1

def add_gomory_cut(num_constraints, num_variables, constraints, rhs, fractional_index, table):
    for i in range(num_constraints):
        table[i][num_variables] = int(constraints[i][fractional_index])
    table[num_constraints][num_variables] = 0

    sum_val = 0
    for i in range(num_variables):
        table[num_constraints][i] = -(constraints[i][fractional_index]
        - int(constraints[i][fractional_index]))
        sum_val += table[num_constraints][i] * table[i][num_variables]
    table[num_constraints][fractional_index] = 1 - sum_val
    table[num_constraints][num_variables] = int(rhs[fractional_index])

def simplex_method(num_constraints, num_variables, objective, constraints, rhs):
    table = [[0.0] * (num_variables + 1) for _ in range(num_constraints + 1)]

    for i in range(num_constraints):
        for j in range(num_variables):
            table[i][j] = constraints[i][j]
        table[i][num_variables] = rhs[i]

    while True:
        print_table(num_constraints, num_variables, table)

        pivot_column = 0
        min_ratio = table[num_constraints][0]

        for i in range(1, num_variables):
            if table[num_constraints][i] < min_ratio:
                min_ratio = table[num_constraints][i]
                pivot_column = i

        if min_ratio >= 0:
            print("Optimal solution found!")
            break

        pivot_row = 0
        min_theta = table[0][num_variables] / table[0][pivot_column]

        for i in range(1, num_constraints):
            theta = table[i][num_variables] / table[i][pivot_column]
            if 0 < theta < min_theta and table[i][pivot_column] > 0:
                min_theta = theta
                pivot_row = i

        pivot_element = table[pivot_row][pivot_column]

        for i in range(num_constraints + 1):
            for j in range(num_variables + 1):
                if i != pivot_row and j != pivot_column:
                    table[i][j] = table[i][j] - (table[pivot_row][j] * table[i][pivot_column]) / pivot_element

        for i in range(num_constraints + 1):
            if i != pivot_row:
                table[i][pivot_column] = 0

        for j in range(num_variables + 1):
            if j != pivot_column:
                table[pivot_row][j] = table[pivot_row][j] / pivot_element

        table[pivot_row][pivot_column] = 1
def solve_integer_lp(num_constraints, num_variables, objective, constraints, rhs):
    simplex_method(num_constraints, num_variables, objective, constraints, rhs)

    solution = [0.0] * num_variables

    for i in range(num_constraints):
        if constraints[i][-1] < num_variables:
            solution[int(constraints[i][-1])] = rhs[i]

    fractional_index = find_fractional_index(num_variables, solution)

    if fractional_index >= 0:
        table = [[0.0] * (num_variables + 1) for _ in range(num_constraints + 1)]
        for i in range(num_constraints + 1):
            for j in range(num_variables + 1):
                table[i][j] = 0.0

        for i in range(num_constraints):
            for j in range(num_variables):
                table[i][j] = constraints[i][j]
            table[i][num_variables] = rhs[i]

        add_gomory_cut(num_constraints, num_variables, constraints, rhs, fractional_index, table)
        solve_integer_lp(num_constraints + 1, num_variables, objective, constraints, rhs)
    else:
        print("Integer solution found:")
        for i in range(num_variables):
            print(f"x{i + 1} = {solution[i]:.2f}")

        objective_value = sum(objective[i] * solution[i] for i in range(len(solution)))
        print(f"Objective function value: {objective_value:.2f}")

def main():
    num_constraints = int(input("Enter the number of constraints: "))
    num_variables = int(input("Enter the number of variables: "))

    objective = []
    print("Enter the objective function coefficients:")
    for i in range(num_variables):
        objective.append(float(input(f"Coefficient for x{i + 1}: ")))

    constraints = []
    rhs = []

    print("Enter the constraint coefficients:")
    for i in range(num_constraints):
        print(f"Constraint {i + 1}:")
        constraint = []
        for j in range(num_variables):
            constraint.append(float(input(f"Coefficient for x{j + 1}: ")))
        constraints.append(constraint)
        rhs.append(float(input("RHS value: ")))

    solve_integer_lp(num_constraints, num_variables, objective, constraints, rhs)

if __name__ == "__main__":
    print("\n\tINTEGER LINE1AR PROGRAMMING USING SIMPLEX METHOD AND GOMORY'S CUT\n")
    main()