Prolema com update, insert e delete em tabelas relacionais

Boa tarde toda vez que tento executar o insert em tabela relacionado recebo o erro abaixo, alguem pode me ajudar?

Cannot add or update a child row: a foreign key constraint fails (akiocs_pabx.localidades, CONSTRAINT localidades_ibfk_1 FOREIGN KEY (empresa_id) REFERENCES clientes (cliente_id) ON DELETE CASCADE ON UPDATE CASCADE)

A tabela clientes possui empresas cadastradas, as empresas podem ter um ou mais localidades.

Portanto ao cadastrar a localidade faz-se a referencia ao registro da empresa em que essa localidade pertence e armazena este registro no campo empresa_id`.