Bsrgvty

What approaches can I use for a Linear Programming problem with the additional constraint that if a decision variable falls below a certain threshold, then it should just be forced to 0.

I'm thinking about the following business scenario: My decision variables are shipment/ordering quantities for a set products, and I want to say that if an order quantity falls below a certain threshold, then I shouldn't bother ordering it as all and just set the value for that product to zero (i.e a supplier won't ship less than x amount of units).

Does this still count as a linear programming problem? Is it still convex? Does this increase the computational difficulty of the problem?

You asked several questions at once but these should be answered all at once too. The problem that you describe is no longer convex. An easy way of seeing this is that the linear combination of the following two feasible solutions:

1. Value of the product at its minimum feasible value (Ordering quantity at its given threshold).


2. Value of the product at zero (Ordering quality below threshold)

is not feasible (say the value of the product being between these two numbers is ruled out by your logic constraints). This violates the definition of convexity.

Even if your constraints are all linear, only using linear constraints is not enough to model nonconvexities. One of the most versatile tools that we have nowadays to model non-convexities is through integer variables. In the case of only linear constraints, this yields a (Mixed-)Integer Linear Programming problem.

Finally, since finding the optimal solutions over a nonconvex feasible region cannot rely solely on the algorithms that assume convexity (Simplex or traditional interior point methods for LP), by removing the convexity assumption, the algorithms to solve these more complicated problems are more computationally demanding. For example, in the case of having discrete variables, you might be forced to evaluate at least some of the discrete choices by fixing them separately (branching).

An alternative to using binary variables is to use semicontinuous variables, supported by some solvers. You still wind up with a discrete optimization problem (integer program), but the binary "buy/don't buy" variables and the related bounds are order sizes are handled internally by the solver rather than explicitly in your model. Some citations (shamelessly starting with one of my own):

• 
  Semicontinuous Variables (my blog; I refuse to waste hyphens where not needed)


• 
  Semi-continuous variables (Erwin Kalvelagen's blog)


• 
  semi-continuous variables (lp_solve documentation)

FICO document (part 2.10 page 8) explain this situation as follow:

• Lets $x_j$ has the situation that you explained. Define a binary variable for each of those variables like $x_j$ and call them $y_j$.


• for each variable that you already defined in the original model consider the lower bound and upper bound(defined $l_j$ and $u_j$). Lower bounds are simply your thresholds for each variable and upper bounds, if you don’t have maximum available ordering amounts, can be a defined big M.


• 
  

  finally add the following constraints to your model:

  
  
  

  $\forall j in textoriginal variables$:

  
  
  
  • $x_j geq l_j . y_j$
  
  
  • $x_j leq u_j . y_j$
  
  

One way to approach this in an integer linear programming formulation is using Big-M.

Let $x in mathbbZ$ with $x geq 0$ be your quantity variable for a product.
You now introduce a variable $y in 0, 1$ that will be assigned zero when you shouldn't be bother ordering, and one otherwise. Let's use this constraint:

• $x leq M y$

Here $M$ is a sufficiently large integer, an upper bound for the maximum quantity you will encounter in an order. So if $y = 1$, $x$ will be your quantity, if $y = 0$, $x$ will be limited to $0$.

Let $T$ be your threshold. We now need some "logic" to set $y$ to $1$ if $x geq T$ and to $0$ otherwise:

• $y leq x/T$

The case $x < T$ yields $y < 1$, i.e., $y = 0$, and the case $x geq T$ allows $y$ to be $1$.

So, we get, as Oguz Toragay already cited from the FICO document:

• $x geq T y$


• $x leq M y$

EDIT: A slightly different approach would be as follows: You could use a variable $z in mathbbZ, z geq 0,$ for quantities that are added on top of your threshold, and $y$ as described above. So replace all occurrences of $x$ by $z + T y$ and only use the constraint $z leq M y$. I guess it's not much of a difference for most MIP solvers, but it's worth trying.

Does this increase the computational difficulty of the problem?

Yes, in two ways:

1) The formulation is an integer formulation, that is, you cannot simply use simplex or barrier methods to solve it, you need to solve the LP relaxation and branch over the fractional variables.

2) The LP relaxation is bad (i.e. there will be a lot of branching, which is expensive). That's usually the issue with Big-M formulations.

As previous posts mentioned, you will need to use binary variables to deal with it. Might, this example be useful to you.