Price-and-branch algorithm for mixed integer linear programming

摘要

A method includes forming a working mixed integer linear program (MILP) from a given MILP for job allocation to allocate people to jobs at least by choosing a subset of variables from the MILP. Only person/job combinations that are deemed most valuable are chosen for the subset. The working MILP includes the chosen subset of variables but no other variables from the given MILP. The working MILP is solved to determine a solution. Using the solution, a special linear program is formed and solved to determine a price of each constraint relative to the solution. Using the prices, variables that are not in the working MILP are evaluated to determine any variables that can contribute to an improved solution. The variables evaluated as contributing to an improved solution are added to the working MILP. The working MILP with the added variables is solved. Apparatus and program products are also disclosed.