公司不可以随意辞退退伍军人，除非存在法定情形。这一原则受到我国多项法律法规的严格保护，以下从多个角度进行详细阐述：

一、法定辞退情形

根据《中华人民共和国劳动合同法》第三十九条，公司在特定情形下可以解除与退伍军人的劳动合同，这些情形包括：

1. 在试用期间被证明不符合录用条件：若退伍军人在试用期内未能达到岗位标准，如不能完成工作任务或不符合技能要求，且公司有充分证据，则可辞退。
2. 严重违反用人单位的规章制度：退伍军人若严重违反公司合理合法的规章制度，如多次旷工或导致重大事故，公司可依据制度辞退。但需确保规章制度制定程序合法，且员工确实违规。
3. 严重失职，营私舞弊，给用人单位造成重大损害：退伍军人因重大过错导致公司经济损失或泄露机密，公司可辞退并无需补偿。需证明失职与损害间的因果关系及“重大损害”标准。
4. 与其他用人单位建立劳动关系影响本职工作：若退伍军人同时与其他单位建立劳动关系，严重影响本职工作或拒不改正，公司可辞退。
5. 劳动合同无效：因特定情形（如欺诈）导致劳动合同无效，公司可辞退退伍军人。
6. 被依法追究刑事责任：退伍军人被判处刑罚时，公司有权解除劳动合同。

二、不得随意辞退及后果

若退伍军人未出现上述法定辞退情形，公司不得随意辞退。否则，根据《中华人民共和国劳动合同法》第八十七条，公司需支付赔偿金，计算标准为经济补偿金的二倍。经济补偿金按劳动者在本单位工作年限，每满一年支付一个月工资；六个月以上不满一年按一年计；不满六个月支付半个月工资。具体计算公式为：

• 经济补偿金 = 劳动者在本单位工作的年限 × 劳动者月工资
• 赔偿金 = 经济补偿金 × 2

其中，月工资是指劳动者在劳动合同解除或者终止前十二个月的平均工资。若劳动者月工资高于用人单位所在直辖市、设区的市级人民政府公布的本地区上年度职工月平均工资三倍的，向其支付经济补偿的标准按职工月平均工资三倍的数额支付，向其支付经济补偿的年限最高不超过十二年。

三、经济补偿的支付

在合法辞退退伍军人（即非因其过错）时，公司需支付经济补偿金，具体标准同上。这是公司对劳动者合法权益的保障。

四、优先留用政策

在裁员过程中，公司应优先考虑留用退伍军人，特别是签订较长期限或无固定期限劳动合同的退伍军人，以及家庭有特殊困难的退伍军人。这体现了公司对特殊群体的关怀和社会责任。

五、违法辞退的救济途径

若公司违法辞退退伍军人，退伍军人可通过多种途径维护自身权益，包括与公司协商、请工会或第三方调解、向劳动争议仲裁委员会申请仲裁或向人民法院提起诉讼。

六、关注地方政策

此外，部分地区对退伍军人就业有特别政策支持和保护措施。公司在辞退退伍军人时，还需关注并遵守当地相关政策规定，以确保行为完全合法合规。

总结与建议：公司在处理与退伍军人的劳动关系时，必须严格遵守相关法律法规，不得随意辞退。在辞退决策中，应充分考虑退伍军人的特殊保护政策和法律规定，确保决策的合法性和合理性。若需辞退，必须依法进行，并支付相应的经济补偿金或赔偿金，以维护退伍军人的合法权益和社会稳定。如有任何疑问或需要进一步的法律帮助，请随时向我咨询。