  


New symmetries in mixedinteger linear optimization
Philipp M. Christophel(philipp.christophelsas.com) Abstract: We present two novel applications of symmetries for mixedinteger linear programming. First we propose two variants of a new heuristic to improve the objective value of a feasible solution using symmetries. These heuristics can use either the actual permutations or the orbits of the variables to find better feasible solutions. Then we introduce a new class of symmetries for binary MILP problems. Besides the usual permutation of variables, these symmetries can also take the complement of the binary variables. This is useful in situations when two opposite decisions are actually symmetric to each other. We discuss the theory of these symmetries and present a computational method to compute them. Examples are presented to illustrate the usefulness of these techniques. Keywords: complement, symmetry, heuristics Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Citation: Technical report Download: [PDF] Entry Submitted: 07/28/2014 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  