Graph Coloring with Linear Programming (LP)
A Study on Real-World Map Regions
Project Overview
Investigate the feasibility and constraints of coloring a real-world map's regions using linear programming techniques. This project aims to represent such regions in a graph, apply various coloring constraints through LP, and visually represent the results.
1.Map Selection: Choosing a real-world map, preferably with more than 18 regions, to ensure complexity. This map should not represent countries or U.S. states.2. 2.Graph Representation: Transform the chosen map into a graph, wherein each region is a vertex, and shared borders indicate edges.
3.Basic Coloring:
- Objective: Minimize the number of colors used, ensuring that adjacent regions are distinctly colored.
- LP Design: Use binary variables and constraints to represent the coloring rules.
4. Advanced Coloring:
- Objective: Impose constraints such that two regions with a shared neighbor cannot be of the same color.
- LP Design Modification: Adjust constraints to satisfy this additional requirement.
5. Dual Coloring:
- Objective: Assign two colors to each region, ensuring no two adjacent regions share any color.
- LP Design Modification: Revise the binary variables and constraints to cater to dual coloring.
6. Validity Assurance:
- Use subgraphs to argue the minimum number of colors derived from the LP results.
- Compare LP results with manual solutions, if feasible.
7. Visualization and Representation:
- Craft colored drawings of the graph and map based on LP results.
- Use software tools or manual drawings to depict the color-coded regions clearly.
My Contributions
1. Map Acquisition and Processing:
- Identified and selected an appropriate real-world map with complex regions to ensure a challenging problem.
- Processed this map to clearly depict boundaries and regions.
2. Graph Formulation:
- Expertly transformed the chosen map into a graph format.
- Ensured accurate representation by cross-referencing multiple sources.
3. LP Model Creation:
- Designed the LP models for basic, advanced, and dual coloring scenarios.
- Innovated in constraint formulation to achieve accurate and minimal coloring.
4. Execution and Analysis:
- Utilized `lpsolve` to run the LP models and gather results.
- Analyzed the output meticulously, drawing inferences about color distribution, regions, and potential improvements.
5. Visualization:
- Played a pivotal role in visualizing the results. Created clear, colored representations of both the graph and map.
- Ensured that visual representations align with LP results.
6. Validity Checks:
- Proactively identified subgraphs to argue and validate the coloring results.
- Developed supporting arguments for each coloring scenario, strengthening the project's credibility.7. Documentation and Report Writing:
- Spearheaded the documentation process, ensuring a comprehensive report detailing every step, from map selection to result interpretation.
- Incorporated visual elements, code snippets, and LP outputs in an organized manner to facilitate understanding.
