Parallel-Processing VLSI Architecture for Mixed Integer Linear Programming

This paper describes parallel processor architecture for a mixed integer linear programming (MILP) solver to realize motion planning and hybrid system control in robot applications. It features pipeline architecture with an MILP-specific configuration and two-port SRAM. Based on the architecture, both FPGA and VLSI implementations have been done to solve sample problems including 16 variables. The FPGA implementation can reduce the power consumption to 13 W: an 85.4% reduction compared to a 3.0-GHz processor (Pentium 4; Intel Corp.). The VLSI solver further reduces the power to 6.4 W using 0.18-mu m CMOS technology.