Optimization and Search Examples in Python

Overview

This repository contains a small collection of self-contained Python examples illustrating classic optimization and search techniques:

• Local search (hill climbing and random restart) for placing hospitals on a grid while minimizing travel distance.
• Constraint satisfaction for scheduling a set of tasks/exams without conflicts, using both a custom backtracking solver and the python-constraint library.
• Linear programming for a simple production planning problem using SciPy’s linprog solver.

The code is structured for teaching, experimentation, and quick demonstrations of operations research / AI search algorithms.

Purpose

The main goals of this project are to:

• Demonstrate different optimization paradigms on small, concrete examples.
• Provide simple reference implementations that are easy to read and modify.
• Support lectures or exercises on search, constraint satisfaction, and mathematical programming.

Typical use cases include classroom demos, self-study, or as a starting point for small assignments and experiments.

Project Structure

.
├── hospitals/
│   ├── hospitals.py              # Local search for hospital placement + visualization
│   └── assets/
│       ├── fonts/OpenSans-Regular.ttf
│       └── images/
│           ├── Hospital.png
│           └── House.png
├── scheduling/
│   ├── schedule0.py              # Naive backtracking CSP solver
│   └── schedule1.py              # CSP solved with python-constraint
├── production/
│   └── production.py             # Linear programming example using SciPy
├── lecture.pdf                   # Related lecture notes/slides (if provided)
└── requirements.txt              # Python dependencies

Requirements / Dependencies

• Python: 3.9+ (any recent 3.x version should work)
• Packages (see requirements.txt):
  • Pillow – image generation for the hospitals visualization.
  • scipy – linear programming solver (scipy.optimize.linprog).
  • python-constraint – constraint programming toolkit used in the scheduling example.

Install everything via:

pip install -r requirements.txt

Note: requirements.txt pins specific versions; if pip complains about a version (e.g., SciPy), adjust it to a compatible 1.x release for your Python version.

Installation

1. Clone or download this repository, then open a terminal in the project root:

   cd /path/to/optimization

2. (Recommended) Create and activate a virtual environment:

   python -m venv .venv
   source .venv/bin/activate   # On Windows: .venv\Scripts\activate

3. Install the dependencies:

   pip install -r requirements.txt

You are now ready to run the examples.

Usage

1. Hospitals – Local Search for Facility Location

This example places a fixed number of hospitals on a grid to minimize the sum of Manhattan distances from houses to their nearest hospital, using hill climbing (and optionally random restart) with visualization.

Run the example (from the project root):

cd hospitals
python hospitals.py

This will:

• Create a 10×20 grid with 3 hospitals and 15 randomly placed houses.
• Run hill climbing to improve hospital locations.
• Generate PNG images (e.g., hospitals000.png, hospitals001.png, …) in the hospitals/ directory showing the current hospitals, houses, and the total cost.

The script uses the assets/ directory relative to the current working directory, which is why you should cd hospitals before running it.

2. Scheduling – Constraint Satisfaction

These examples assign seven entities (A–G, e.g., courses or exams) to days of the week (Monday–Wednesday) subject to a set of binary “cannot-be-on-the-same-day” constraints. This is equivalent to a small graph coloring / exam timetabling problem.

From the project root, you can run:

python scheduling/schedule0.py  # Naive backtracking search
python scheduling/schedule1.py  # Using python-constraint

• schedule0.py implements naive backtracking: it recursively assigns days to variables in a fixed order and checks consistency after each assignment. It stops after finding one consistent schedule and prints it as a dictionary (e.g., {"A": "Monday", ...}).
• schedule1.py expresses the same problem using the python-constraint library. It adds all variables and constraints to a Problem instance and then iterates through all valid solutions, printing each one.

You can experiment by editing VARIABLES, CONSTRAINTS, or the list of allowed days to model different scheduling problems.

3. Production – Linear Programming

This example solves a small production planning / resource allocation problem using SciPy’s linear programming solver.

From the project root, run:

python production/production.py

The script:

• Defines an objective function of the form 50 x1 + 80 x2.
• Adds two linear inequality constraints.
• Calls scipy.optimize.linprog with the HiGHS method to compute an optimal solution.
• Prints the resulting optimal values for X1 and X2 (interpreted as hours, units, or similar depending on the original problem statement).

Key Components

hospitals/hospitals.py

• Class Space: Represents the grid world and current configuration of houses and hospitals.
  • add_house(row, col): Add a house at a given grid cell.
  • available_spaces(): All empty cells where a hospital could be placed.
  • hill_climb(maximum=None, image_prefix=None, log=False): Perform hill-climbing search starting from a random configuration; optionally logs intermediate steps and writes images.
  • random_restart(maximum, image_prefix=None, log=False): Run hill climbing multiple times from different random starts, keeping the best configuration.
  • get_cost(hospitals): Sum of distances from each house to its nearest hospital (lower is better).
  • get_neighbors(row, col): Valid neighbor cells for moving a hospital (up/down/left/right) that do not already contain a house or hospital.
  • output_image(filename): Draw the grid, houses, and hospitals using Pillow and save an annotated PNG image.

At the bottom of the file, a script section constructs a Space, randomly populates houses, and runs hill_climb with logging and image generation.

scheduling/schedule0.py (Naive Backtracking)

• Global VARIABLES and CONSTRAINTS define the CSP structure.
• backtrack(assignment): Recursive backtracking solver that tries assignments in order and returns the first complete, consistent assignment it finds.
• select_unassigned_variable(assignment): Picks the next unassigned variable in a fixed order.
• consistent(assignment): Checks whether all currently assigned variable pairs satisfy the inequality constraints.

When executed as a script, it calls backtrack({}) and prints the resulting schedule.

scheduling/schedule1.py (python-constraint Version)

• Uses Problem from python-constraint to model the same scheduling CSP.
• addVariables([...], ["Monday", "Tuesday", "Wednesday"]) sets up variables and their domains.
• For each pair in CONSTRAINTS, adds a binary constraint enforcing different days.
• Iterates over problem.getSolutions() and prints each valid assignment.

This provides a concise, library-based alternative to the manual backtracking in schedule0.py.

production/production.py

• Uses scipy.optimize.linprog with the HiGHS method to solve a small linear program.
• Encodes the objective coefficients and inequality constraints in the standard SciPy format.
• Checks result.success and prints the optimal decision variables if a feasible optimum exists.

Configuration

There are no separate configuration files or required environment variables. Configuration is done directly in the code:

• Hospitals (hospitals/hospitals.py):
  • Adjust height, width, and num_hospitals when creating the Space instance.
  • Change the number or distribution of houses by modifying the loop that calls add_house.
  • Tweak maximum, image_prefix, and log when calling hill_climb or random_restart.
  • The visualization code assumes the assets/ directory exists in the current working directory.
• Scheduling (scheduling/schedule0.py, scheduling/schedule1.py):
  • Modify VARIABLES, CONSTRAINTS, or the set of allowed days to represent different scheduling or graph coloring problems.
• Production (production/production.py):
  • Edit the cost vector and constraint matrices passed to linprog to describe different linear programs.

Contributing

This is a small, educational codebase. If you want to extend it (e.g., add new optimization examples, heuristics, or visualizations):

• Keep dependencies minimal and update requirements.txt if you add new ones.
• Ensure existing examples still run after your changes.
• Add short comments or docstrings to explain any new algorithms or parameters.

Feel free to fork the repository or propose changes according to your usual workflow.

License

No explicit LICENSE file is present in this repository. Unless a license is added, you should assume the code is all rights reserved and seek permission from the original author/instructor before redistributing or using it beyond personal or educational purposes.