// Catalano Math Library
// The Catalano Framework
//
// Copyright © Diego Catalano, 2012-2018
// diego.catalano at live.com
//
//
//    This library is free software; you can redistribute it and/or
//    modify it under the terms of the GNU Lesser General Public
//    License as published by the Free Software Foundation; either
//    version 2.1 of the License, or (at your option) any later version.
//
//    This library is distributed in the hope that it will be useful,
//    but WITHOUT ANY WARRANTY; without even the implied warranty of
//    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
//    Lesser General Public License for more details.
//
//    You should have received a copy of the GNU Lesser General Public
//    License along with this library; if not, write to the Free Software
//    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
//

package Catalano.Math.Optimization;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Stack;

/**
 * Mixed Integer Linear Programming.
 * Branch and Bound method.
 * 
 * @author Diego Catalano
 */
public class MixedIntegerLinearProgramming {
    
    /**
     * The solution is infeasible.
     */
    public static final int INFEASIBLE = 0;
    
    /**
     * The solution exists.
     */
    public static final int OPTIMAL = 1;
    
    /**
     * The solution is unbounded.
     */
    public static final int UNBOUNDED = 2;
    
    /**
     * Objective of the function.
     */
    public enum Objective{
        
        /**
         * Minimize the function.
         */
        Minimize,
        
        /**
         * Maximize the function.
         */
        Maximize
    };
    
    private double tolL = 1e-5;
    private double tolU = 1D - 1e-5;
    private Objective objective;
    
    private LinearProgramming simplex;
    private int maxIteration = 100;
    
    private int[] type;
    
    private Solution sol;

    /**
     * Set type.
     * 1 means integer, 0 means double.
     * 
     * @param type Type.
     */
    public void setType(int[] type) {
        this.type = type;
    }
    
    /**
     * Get the coefficients.
     * @return Coefficients.
     */
    public double[] getCoefficients(){
        return sol.coef;
    }
    
    /**
     * Get the solution.
     * @return Solution.
     */
    public double getSolution(){
        return sol.z;
    }

    /**
     * Initialize a new instance of the MixedIntegerLinearProgramming class.
     * @param objective Objective.
     */
    public MixedIntegerLinearProgramming(Objective objective) {
        this(objective, 1E-5);
    }
    
    /**
     * Initialize a new instance of the MixedIntegerLinearProgramming class.
     * @param objective Objective.
     * @param tol Tolerance for round the integer.
     */
    public MixedIntegerLinearProgramming(Objective objective, double tol){
        this.objective = objective;
        this.tolL = tol;
        this.tolU = 1D - tol;
    }
    
    /**
     * Solve the problem.
     * @param function Function.
     * @param constraint List of constraints.
     * @return Status of the MILP.
     */
    public int Solve(double[] function, List constraint){
        
        int iter = 0;
        
        if(type == null)
            throw new IllegalArgumentException("The data type must be definied.");
        
        
        //Calculate node 0
        double value = Double.NaN;
        if(objective == Objective.Maximize){
            simplex = new LinearProgramming(LinearProgramming.Objective.Maximize);
        }
        else{
            simplex = new LinearProgramming(LinearProgramming.Objective.Minimize);
        }
        
        //Initial solution
        int status = simplex.Solve(function, constraint);
        if(status == 1){
            boolean c = CheckSolution(simplex.getCoefficients(), function.length);
            if(c){
                return 1;
            }
            else{
                
                //Initial bb
                Stack> stack = new Stack>();
                BranchAndBound(stack, constraint, simplex.getCoefficients(), function.length);
                
                List solutions = new ArrayList();
                
                while(stack.size() > 0){
                    
                    if(iter == maxIteration) break;
                    iter++;
                    
                    List p = stack.pop();
                    int s = simplex.Solve(function, p);
                    
                    if(s == 1){
                        
                        boolean b = CheckSolution(simplex.getCoefficients(), function.length);
                        
                        if(objective == Objective.Maximize){
                            if(b){
                                solutions.add(new Solution(simplex.getCoefficients(), simplex.getSolution()));
                                
                                if(Double.isNaN(value)){
                                    value = simplex.getSolution();
                                }
                                
                                value = Math.max(value, simplex.getSolution());
                                
                            }
                            else{
                                if(Double.isNaN(value))
                                    BranchAndBound(stack, p, simplex.getCoefficients(), function.length);
                                
                                if(Double.isNaN(value) == false && simplex.getSolution() > value){
                                    BranchAndBound(stack, p, simplex.getCoefficients(), function.length);
                                }
                            }
                        }
                        else{
                            if(b){
                                solutions.add(new Solution(simplex.getCoefficients(), simplex.getSolution()));
                                
                                if(Double.isNaN(value)){
                                    value = simplex.getSolution();
                                }
                                
                                value = Math.min(value, simplex.getSolution());
                                
                            }
                            else{
                                if(Double.isNaN(value))
                                    BranchAndBound(stack, p, simplex.getCoefficients(), function.length);
                                
                                if(Double.isNaN(value) == false && simplex.getSolution() < value){
                                    BranchAndBound(stack, p, simplex.getCoefficients(), function.length);
                                }
                            }
                        }
                    }
                }
                
                if(solutions.isEmpty()) return 0;
                
                if(objective == Objective.Maximize){
                    Collections.sort(solutions, new Comparator() {
                        @Override
                        public int compare(Solution o1, Solution o2) {
                            return Double.compare(o2.z, o1.z);
                        }
                    });
                }
                else{
                    Collections.sort(solutions, new Comparator() {
                        @Override
                        public int compare(Solution o1, Solution o2) {
                            return Double.compare(o1.z, o2.z);
                        }
                    });
                }
                
                sol = solutions.get(0);
                
                return 1;
                
            }
        }
        
        return status;
        
    }
    
    private void BranchAndBound(Stack> stack, List constraint, double[] solution, int n){
        
        int index = GetUpperValue(solution, n);
        
        double lower = Math.floor(solution[index]);
        double upper = Math.ceil(solution[index]);
        
        double[] v = new double[n];
        v[index] = 1;
        
        List c1 = new ArrayList(constraint);
        c1.add(new Constraint(v, Constraint.Symbol.GREATER_THAN, upper));
        
        List c2 = new ArrayList(constraint);
        c2.add(new Constraint(v, Constraint.Symbol.LESS_THAN, lower));
        
        stack.add(c1);
        stack.add(c2);
        
    }
    
    private int GetUpperValue(double[] solution, int n){
        
        double min = -Double.MAX_VALUE;
        int index = -1;
        for (int i = 0; i < n; i++) {
            if(solution[i] % 1 != 0){
                if(solution[i] > min){
                    min = Math.max(min, solution[i]);
                    index = i;
                }
            }

        }
        
        return index;
        
    }
    
    private boolean CheckSolution(double[] solution, int n){
        
        for (int i = 0; i < n; i++) {
            if(type[i] == 1){
                if(isInteger(solution[i]) == false)
                    return false;
            }

        }
        
        return true;
        
    }
    
    /**
     * Check if the value is integer within a certain tolerance.
     * @param value Value.
     * @return True if the value is integer, otherwise false.
     */
    private boolean isInteger(double value){
        double d = Math.abs(Math.floor(value) - value);
        if(d < tolL) return true;
        if(d - tolU >= 0) return true;
        return d < tolL;
    }
        
    class Solution {
        private double[] coef;
        private double z;

        public Solution(double[] coef, double z) {
            this.coef = coef;
            this.z = z;
        }
        
    }
}
 

Ads help maintain this website.