how to code binary integer programming model?

How can I write the matlab code for this binary integer pogramming model to find the optimal solution Z, and binary values of integer variables yi, xj :

Max Z= 23y1 + 25y2 + 54y3 + 74y4 + 13y5 + 33y6 + 47y7 + 92y8 + 17y9 + 39y10

Subject to:

0 ≥ y1

x1 ≥ y2

x1 + x6 ≥ y3

x6 ≥ y4

0 ≥ y5

x7 ≥ y6

0 ≥ y7

0 ≥ y8

0 ≥ y9

x4 ≥ y10

x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 ≤ 1

yi ∈ {0,1} , i = 1,2,.....,10

xj ∈ {0,1} , j = 1,2,.....,8

[Ive J]

check https://mathworks.com/help/optim/ug/intlinprog.html

Don't forget your objective func needs a minus sign

f = -[23, 25, 54, 74, 13, 33, 47, 92, 17, 39];

Also for simplicity name all your variables y1 to y18, where x1 to x8 are y11 to y18.

[Hajem Daham]

Thanks Ive J

Answer 1

[John D'Errico]

So you have 18 unknowns. What is the problem? What have you tried? You will call intlinprog, (older releases will call bintprog, which no longer exists in MATLAB) but still this is just a direct call tp intlinprog.

Learn to use indexing, and vectors, and arrays. Learn NOT to write numbered variables as you seem to be doing.

As I said, you have 18 unknowns, thus a vector of length 18 will be the result. I'll call it X. Think of the vector x as unknowns X(11) through X(18), and y is now X(1) through X(10). So the constraint x7 ≥ y6, becomes X(17) >= X(6).

Now using intlinprog, specify that ALL of the 18 unknowns are integer, with lower bounds of 0, and upper bounds of 1. That tells intlinprog this is a binary integer program.

When your call to intlinprog returns a result, then unpack the vector X into sub-vectors x and y as:

y = X(1:10);
x = X(11:18);

So read the help for intlinprog. If necessary, look at the examples provided with doc intlinporog.

help intlinprog

 INTLINPROG Mixed integer linear programming.
 
    X = INTLINPROG(f,intcon,A,b) attempts to solve problems of the form
 
             min f'*x    subject to:  A*x  <= b
              x                       Aeq*x = beq
                                      lb <= x <= ub
                                      x(i) integer, where i is in the index
                                      vector intcon (integer constraints)
 
    X = INTLINPROG(f,intcon,A,b) solves the problem with integer variables
    in the intcon vector and linear inequality constraints A*x <= b. intcon
    is a vector of positive integers indicating components of the solution
    X that must be integers. For example, if you want to constrain X(2) and
    X(10) to be integers, set intcon to [2,10].
 
    X = INTLINPROG(f,intcon,A,b,Aeq,beq) solves the problem above while
    additionally satisfying the equality constraints Aeq*x = beq. (Set A=[]
    and b=[] if no inequalities exist.)
 
    X = INTLINPROG(f,intcon,A,b,Aeq,beq,LB,UB) defines a set of lower and
    upper bounds on the design variables, X, so that the solution is in the
    range LB <= X <= UB. Use empty matrices for LB and UB if no bounds
    exist. Set LB(i) = -Inf if X(i) is unbounded below; set UB(i) = Inf if
    X(i) is unbounded above.
 
    X = INTLINPROG(f,intcon,A,b,Aeq,beq,LB,UB,X0) sets the initial point
    to X0.
 
    X = INTLINPROG(f,intcon,A,b,Aeq,beq,LB,UB,X0,OPTIONS) minimizes with
    the default optimization parameters replaced by values in OPTIONS, an
    argument created with the OPTIMOPTIONS function. See OPTIMOPTIONS for
    details.
 
    X = INTLINPROG(PROBLEM) finds the minimum for PROBLEM. PROBLEM is a
    structure with the vector 'f' in PROBLEM.f, the integer constraints in
    PROBLEM.intcon, the linear inequality constraints in PROBLEM.Aineq and
    PROBLEM.bineq, the linear equality constraints in PROBLEM.Aeq and
    PROBLEM.beq, the lower bounds in PROBLEM.lb, the upper bounds in
    PROBLEM.ub, the initial point in PROBLEM.x0, the options structure in
    PROBLEM.options, and solver name 'intlinprog' in PROBLEM.solver.
 
    [X,FVAL] = INTLINPROG(f,intcon,A,b,...) returns the value of the
    objective function at X: FVAL = f'*X.
 
    [X,FVAL,EXITFLAG] = INTLINPROG(f,intcon,A,b,...) returns an EXITFLAG
    that describes the exit condition. Possible values of EXITFLAG and the
    corresponding exit conditions are
 
      3  Optimal solution found with poor constraint feasibility.
      2  Solver stopped prematurely. Integer feasible point found.
      1  Optimal solution found.
      0  Solver stopped prematurely. No integer feasible point found.
     -1  Solver stopped by an output function or plot function.
     -2  No feasible point found.
     -3  Root LP problem is unbounded.
     -9  Solver lost feasibility probably due to ill-conditioned matrix.
 
    [X,FVAL,EXITFLAG,OUTPUT] = INTLINPROG(f,A,b,...) returns a structure
    OUTPUT containing information about the optimization process. OUTPUT
    includes the number of integer feasible points found and the final gap
    between internally calculated bounds on the solution. See the
    documentation for a complete description.
 
    See also LINPROG.

    Documentation for intlinprog
       doc intlinprog

[Hajem Daham]

Thanks John D'Errico