🎬 CineOpt: Cinema Scheduling Optimization Framework

A High-Performance Decision Support System for Box Office Maximization under Screening Rate Constraints.

Overview • The Math • Algorithms • Installation • Usage • Results • Acknowledgements

---

📖 Overview

CineOpt is a specialized optimization framework designed to solve the Cinema Subset Selection Problem (CSSP).

In the highly competitive film distribution market, distributors often incentivize cinemas to maintain a specific Screening Rate ($\tau$) (e.g., $\ge 30%$) on opening day. The challenge for cinema chains is to select an optimal subset of cinemas to bundle together such that the aggregate screening rate meets the threshold while maximizing the total Box Office Revenue.

This project benchmarks various algorithmic strategies using real-world commercial data from the 2019 blockbuster "Movie X", demonstrating the trade-offs between computational efficiency, solution optimality, and engineering robustness.

✨ Key Features

• Real-World Dataset: Based on desensitized operational data from 384 cinemas during the Spring Festival season.
• Linearization Strategy: Transforms non-linear fractional constraints into linear constraints solvable by MILP engines.
• Comprehensive Benchmark: Compares Exact Methods (IP), Heuristics (Greedy), and Pseudo-Polynomial approaches (DP).
• Automated Visualization: Generates academic-grade plots to visualize the Efficiency vs. Optimality trade-off.

---

🧮 Mathematical Formulation

The core problem is modeled as a variant of the 0-1 Knapsack Problem with side constraints.

Given a set of cinemas $N = {1, \dots, n}$, for each cinema $i$:

• $v_i$: Total Box Office Revenue (Value)
• $s_i$: Film Sessions (Movie X)
• $t_i$: Total Sessions (All films)
• $\tau$: Target Screening Rate Threshold (e.g., 0.3)

Decision Variable: $x_i \in {0, 1}$ (Select cinema $i$ or not).

$$ \begin{aligned} \textbf{Maximize} \quad & \sum_{i=1}^{n} v_i x_i \\ \textbf{Subject to} \quad & \frac{\sum_{i=1}^{n} s_i x_i}{\sum_{i=1}^{n} t_i x_i} \ge \tau \\ & x_i \in {0, 1}, \quad \forall i \in {1, \dots, n} \end{aligned} $$

Linearization: The fractional constraint is transformed into a linear form for the IP solver: $$ \sum_{i=1}^{n} (s_i - \tau t_i) x_i \ge 0 $$

---

🧠 Algorithms

CineOpt implements and compares the following solvers:

Algorithm Class	Method	Complexity	Description
Exact	Integer Programming (IP)	NP-Hard (Worst Case)	The Gold Standard. Uses IBM CPLEX (Branch-and-Cut) to find the global optimum. Robust and fast (~80ms).
Heuristic	Greedy (Ratio)	$O(N \log N)$	Reduces problem to Knapsack-like structure. Sorts by profit-to-weight ratio. Fast but suboptimal.
Heuristic	Greedy (Sequential)	$O(N \log N)$	Naive sorting by screening rate. Serves as a baseline.
Pseudo-Poly	DP (Weight-based)	$O(N \cdot \sum w)$	Weight-based Dynamic Programming. Sensitive to precision scaling.
Pseudo-Poly	DP (Value-based)	$O(N \cdot \sum v)$	Value-based DP. Extremely slow for high-revenue datasets (Computationally expensive).

---

💻 Installation

This project relies on conda for environment management to ensure reproducibility.

1. Clone the repository

   git clone [https://github.com/0SliverBullet/CineOpt.git](https://github.com/0SliverBullet/CineOpt.git)
   cd CineOpt

2. Create the environment

   conda env create -f environment.yml

3. Activate the environment

   conda activate opt_env

---

🚀 Usage

1. Run Full Benchmark (Recommended)

The main.py orchestrator runs the entire pipeline: loading data, executing all solvers (IP, Greedy, DP), and generating comparison plots.

python main.py

2. Run Individual Solvers

You can run specific algorithms via CLI arguments for granular testing.

Integer Programming (IP):

python src/solvers/ip_solver.py

Greedy Algorithms:

# Options: sequential, ratio, all
python src/solvers/greedy_solver.py --method ratio

Dynamic Programming:

# Type: W (Weight) or V (Value)
# Scale: Precision multiplier (e.g., 10 for high precision, 1 for low)
python src/solvers/dp_solver.py --type W --scale 10

---

📊 Benchmark Results

Our experiments reveal that Integer Programming (IP) is the clear winner for this specific industrial problem.

Optimality: IP achieves the Global Optimum ($21.24M), recovering ~4% revenue lost by Greedy algorithms.

Efficiency: IP solves the problem in ~82ms, whereas high-precision DP approaches take hours due to the curse of dimensionality.

Trade-off: As shown in below, IP occupies the "Sweet Spot."

Visualization generated automatically by src/visualization/plot_results.py

---

📂 Project Structure

CineOpt/
├── config.py               # Global configuration & Hyperparameters
├── environment.yml         # Conda environment definition
├── main.py                 # Benchmark Pipeline Orchestrator
├── data/
│   ├── instances/          # Processed CSV instances
│   └── raw/                # Raw Excel sheets
├── output/
│   ├── figures/            # Generated plots (Bar charts)
│   └── solutions/          # Solver logs (.txt files)
└── src/
    ├── solvers/            # Core Algorithms
    │   ├── ip_solver.py    # CPLEX implementation
    │   ├── dp_solver.py    # Numba-accelerated DP
    │   └── greedy_solver.py
    ├── utils/
    │   ├── data_loader.py  # Data ingestion & Linearization logic
    │   └── recorder.py     # Result serialization
    └── visualization/
        └── plot_results.py # Matplotlib/Seaborn plotting engine

---

🙏 Acknowledgements

Course Project: This work was developed as part of CSE5025 Combinatorial Optimization course.

Data Source: Real-world operations data from the 2019 Spring Festival (Movie X).

Special Thanks:

A massive shoutout to Gemini 3.0 Pro by Google. This project was architected, coded, debugged, and documented in an intense 10-hour sprint with the assistance of Gemini 3.0 Pro. Its capabilities in mathematical modeling, algorithmic debugging (specifically Numba JIT and floating-point precision issues), and architectural design were instrumental in delivering this high-quality benchmark suite.

_{Made with ❤️ and Solver Magic by the CineOpt Team}