linear-programmingmixed-integer-programmingsimplex

How could constraints be dynamiclly defined with simplex method?


I try to correctly write a linear programming model for my problem. I want to minimize the sum of w_i and i have the following constraint:

(a_i+w_i ≤ w_j) XOR (a_j+w_j ≤ w_i)

a_i and a_j are integer constants
w_i and w_j are integer variables

in general, when we write the standard form of the system, we have equations where the write part represents the maximum or the minimum quantity of product, this quantity is well defined but in my problem both w_i and w_j are unknown, they should be computed by my ILP, so i can't define de budget b when writing the standard form an when formulating the first table which correspond to the standard form! how can i do this please?!

Re: i use the simplex method all variables are integer


Solution

  • (1) Strictly speaking, the Simplex Method is only for continuous problems.

    (2) INEQ1 OR INEQ2 can be done by adding binary variables. I have never seen a model with INEQ1 XOR INEQ2. I suspect in your case we just can use INEQ1 OR INEQ2.

    (3) An OR is often modeled as:

    a(i)+w(i) ≤ w(j) + M*δ(i,j)  
    a(j)+w(j) ≤ w(i) + M*(1-δ(i,j))
    δ(i,j) ∈ {0,1}
    

    Here M is a big-M: a large enough constant. Often we can limit these constraints to the case where i<j due to symmetry.