结论：退伍军人没有违规的情况下，公司一般不可以随意辞退。公司若需辞退退伍军人，必须严格遵守《中华人民共和国劳动合同法》及《中华人民共和国退役军人保障法》等相关法律法规，确保程序合法且充分保障退伍军人的合法权益。
一、合法辞退的情形
根据《中华人民共和国劳动合同法》第三十九条，公司在以下情形下可以辞退退伍军人（这些情形同样适用于所有劳动者）：
- 在试用期间被证明不符合录用条件：若退伍军人在试用期内未能达到岗位标准，如不能完成工作任务或不符合技能要求，且公司有充分证据，则可辞退。
- 严重违反用人单位的规章制度：退伍军人若严重违反公司合理合法的规章制度，如多次旷工或导致重大事故，公司可依据制度辞退。但需确保规章制度制定程序合法，且员工确实违规。
- 严重失职，营私舞弊，给用人单位造成重大损害：退伍军人因重大过错导致公司经济损失或泄露机密，公司可辞退并无需补偿。需证明失职与损害间的因果关系及“重大损害”标准。
- 与其他用人单位建立劳动关系影响本职工作：若退伍军人同时与其他单位建立劳动关系，严重影响本职工作或拒不改正，公司可辞退。
- 劳动合同无效：因特定情形（如欺诈）导致劳动合同无效，公司可辞退退伍军人。
- 被依法追究刑事责任：退伍军人被判处刑罚时，公司有权解除劳动合同。
二、不得随意辞退的情形及后果
若退伍军人未出现上述法定辞退情形，公司不得随意辞退。否则，根据《中华人民共和国劳动合同法》第八十七条，公司需支付赔偿金，计算标准为经济补偿金的二倍。经济补偿金按劳动者在本单位工作年限，每满一年支付一个月工资；六个月以上不满一年按一年计；不满六个月支付半个月工资。具体计算公式如下：
- 经济补偿金：\(经济补偿金 = 工作年限 \times 月工资\)（其中，工作年限满一年按一年计，六个月以上不满一年按一年计，不满六个月按半个月计）
- 赔偿金：\(赔偿金 = 2 \times 经济补偿金\)
三、退伍军人的特殊保护政策
国家对于退伍军人有着特殊的安置和保护政策，旨在保障他们的合法权益和就业稳定性。这些政策不仅体现在就业方面的优先权，还包括社会保障等方面的优惠待遇。因此，公司在处理退伍军人劳动关系时，必须严格遵守相关法律法规，确保不侵犯其合法权益。
四、实际操作建议
- 合规审查：公司在考虑辞退退伍军人前，应进行严格的合规审查，确保辞退行为符合《中华人民共和国劳动合同法》及相关法律法规的规定。
- 沟通协商：在决定辞退前，建议公司与退伍军人进行充分的沟通协商，了解其具体情况和诉求，寻求双方都能接受的解决方案。
- 法律咨询与风险防控：如遇复杂或争议较大的情况，公司应及时向我咨询，以确保决策的法律合规性和风险可控性。
总之，退伍军人作为劳动者享有与其他员工同等的法律保护。公司在处理退伍军人劳动关系时，必须严格遵守相关法律法规，不得随意辞退。如确需解除劳动合同，应依法进行并承担相应的经济责任。若您有更多关于劳动纠纷、工伤赔偿、劳动仲裁等方面的问题，欢迎直接向我咨询。