branchcut.py

import pulp
from typing import List, Tuple, Dict
import numpy as np
import abc


class LPSolver(abc.ABC):
    def __init__(self, edges, constraints, num_verts_a, num_verts_b):
        pass
    
    def solve(self):
        pass
    
    def is_solution_optimal(self):
        pass
    
    def is_problem_infeasible(self):
        pass
    
    def is_solution_integer(self):
        pass
    
    def get_value_of_solution(self):
        pass
    
    def _make_variables(self, num_verts_a, num_verts_b):
        pass
    
    def _set_costs(self, edges):
        pass


class PulpLPSolver(LPSolver):
    def __init__(self, edges, constraints, num_verts_a, num_verts_b):
        self.problem: pulp.LpProblem = pulp.LpProblem("Relaxed: Minimize Crossings", pulp.LpMinimize)
        self.constraints = constraints
        
        self.variables = self._make_variables(num_verts_a, num_verts_b)
        self._set_costs(edges)
        
    def solve(self):
        self.problem.solve()
    
    def is_solution_optimal(self):
        return self.problem.status == pulp.LpStatusOptimal
    
    def is_problem_infeasible(self):
        return self.problem.status == pulp.LpStatusInfeasible
    
    def get_integer_and_fractional_variables_of_solution(self):
        fractional_variables = []
        integer_variables = []
        if self.is_solution_optimal():
            var: pulp.LpVariable
            # collects all y variables which are fractional
            for var in self.problem.variables():
                name = var.getName()
                if name.startswith("y"):
                    if var.value() != 0 or var.value() != 1:
                        fractional_variables.append(name)
                    else:
                        integer_variables.append(name)
        return integer_variables, fractional_variables
    
    def get_value_of_solution(self):
        if self.problem.status == pulp.LpStatusOptimal:
            return self.problem.value()
        else:
            return None
        
    def _make_variables(self, num_verts_a, num_verts_b):
        return {
                (i, j): pulp.LpVariable(f"y_{i}_{j}", 0, 1, cat="Continuous")
                for i in range(num_verts_a + 1, num_verts_a + num_verts_b + 1)
                for j in range(num_verts_a + 1, num_verts_a + num_verts_b + 1) if i < j
            }
    
    def _set_costs(self, edges):
        # c doesn't have to be binary: c and its corresponding y have to have the same category.
        # c will automatically be binary if the corresponding y is binary and continuous otherwise
        # since c = y or c = 1 - y
        costs = {
                (i, j, k, l): pulp.LpVariable(f"c_{i}_{j}_{k}_{l}", 0, 1) 
                for (i, j) in edges
                for (k, l) in edges
            }# if i < j and k < l and i < k and j != l}
        
        for (i, j) in edges:
            for (k, l) in edges:
                if k > i:  # Da die Liste sortiert ist, brauchen wir nur k > i zu prüfen
                    #if (i, j, k, l) not in c:
                        #c[(i, j, k, l)] = LpVariable(f"c_{i}_{j}_{k}_{l}", 0, 1, cat='Binary')
                    if j > l:
                        self.problem += costs[(i, j, k, l)] == self.variables[(l, j)]
                    elif l > j:
                        self.problem += costs[(i, j, k, l)] == 1 - self.variables[(j, l)]
    

def _cut(constraints: Dict[Tuple], constraints_pool: Dict[Tuple]) -> Dict[Tuple]:
    """
    Adds cutting planes: Adds constraints from constraints_pool to constraints.
    """
    new_constraints = constraints.copy()
    return new_constraints

def _branch(solved_problem: pulp.LpProblem, variables: Dict[Tuple]):
    """
    Branches on a binary variable: Sets a relaxed variable to either 0 or 1.
    """
    pass

def _parse_graph_file() -> Tuple[List[Tuple]]:
    pass

def solve(edges: List[Tuple]):
    """
    Solves an ILP using Branch-and-Cut.
    """
    edges, constraints, num_verts_a, num_verts_b = _parse_graph_file()
    problem = PulpLPSolver(edges, constraints, num_verts_a, num_verts_b)
    problems = [problem]
    
    x_star = None
    v_star = -np.Inf
    while len(problems) > 0:
        constraints_violated = True
        current_problem = problems.pop(0)
        # this while loop is necessary for step 6
        while constraints_violated:
            current_problem.solve()

            # problem infeasible, go to next problem in queue
            if current_problem.is_problem_infeasible():
                break

            if current_problem.is_solution_optimal():
                # not an improvement, go to next problem in queue
                if pulp.value(current_problem) >= v_star:
                    break
                # current solution improves the value of the solution, continue evaluation of the solution
                else:
                    # step 5
                    # check if solution is integer: if yes, set current solution as best solution
                    integer_variables, fractional_variables = current_problem.get_integer_and_fractional_variables_of_solution()
                    if len(fractional_variables) == 0:
                        v_star = pulp.value(current_problem)
                        x_star = current_problem
                        continue

                    # step 6
                    # get constraints that are fulfilled by the integer vars but violated by the fractional ones
                    violated_constraints = _get_violated_constraints(integer_variables, fractional_variables)
                    
                    # add the violated constraints back to the LP and go back to the inner while loop
                    if len(violated_constraints) > 0:
                        current_problem += violated_constraints
                    else:
                        constraints_violated = False