Combinatorial Optimization Approaches for Graph Construction Problems