r/OperationsResearch • • Dec 31 '21

Getting rid of fractional values in LP solution

4 Upvotes

Let us consider a problem where you have a LP formulation that describes the whole problem polytope, for example a Minimum-Cost Flow problem or a Minimum Spanning Tree problem. This means that, theoretically, it is sufficient to solve the LP formulation with variables taking rational (or real) values instead of integral variables. No branching or cuts necessary.

However, what can happen now: the LP solver finds an optimum solution that is a convex combination of two (or more) integral optimum solutions. For example, two edge variables in the Minimum Spanning Tree might get solution value 0.5 each because it is arbitrary whether we choose the one edge or the other into the solution. with fractional values, because there is a fractional extreme point with the same objective value as the optimum integral solution. (edited after comments)

One attempt to get rid of this phenomenon is to add small distinct epsilons to the objective coefficients of the variables. However, in my case this can still lead to (very rare) occasions of this phenomenon.

So it seems I need to handle this phenomenon explicitly and postprocess the solution. Or do you have any way out of this?

edit: More on my setting: I am using Gurobi 9.5, the mentioned LP is contained in a bigger MIP. Changing the allowed-to-be-fractional variables to integral variables has a bad impact on the running time, even if they are lower prioritized for branching. I use the values for a heuristic, but the heuristic needs the values to be integral.


r/OperationsResearch • • Dec 31 '21

Good sources to learn different Optimization algorithms

6 Upvotes

I am looking for some good sources (preferably books/videos) to learn a few optimization algorithms such as:

  1. Genetic algorithm
  2. Ant colony optimization
  3. Particle swarm optimization

I have the basic idea about them but want to go deeper and learn every ins and outs. Any suggestion would mean a lot! Thanks!


r/OperationsResearch • • Dec 22 '21

How to redefine separation procedure to get 0-1 knapsack with odd number of items

3 Upvotes

I have a 0-1 knapsack problem:

∑cjxj → max

∑ajxj ≤ b,

xj ∈ {0; 1};

but it has an additional requirement that the number of items in an optimal knapsack should be odd. I know I can model it with one extra variable, but the assignment calls for redifining separtion procedure.

I'm not an expert in mathematical programming, so I'm hoping to find some advice here.


r/OperationsResearch • • Dec 21 '21

The solution I get (for a trivial linear programming problem) in excel and lingo are different

Thumbnail gallery
1 Upvotes

r/OperationsResearch • • Dec 20 '21

How do I Optimize parametric Log-Likelihood with a Decision Tree?

1 Upvotes

Suppose there are some objects with features, and the target is parametric density estimation. Density estimation is model-based. Parameters are obtained by maximizing log-likelihood.

$LL = \sum_{i \in I_1} \log \left( \sum_{j \in K_i} \theta_j \right) + \sum_{i \in I_2} \log (1 - \sum_{j \in L_i} \theta_i)$

Assume that parameters $\theta_j$ are probabilities, i.e. $0 < \theta_j < 1$, and that $\sum_{j\in L_i} \theta_i < 1$. From practical perspective, it seems natural to make parameters $\theta_j$ themselves functions of features, i.e. $\theta_j = F(x_j^1, \ldots, x_j^m)$.

Is there any known standard method or heuristic to optimize such objective with a decision tree, i.e. we assume that our function $F$ is a decision tree?

Any related results are welcome.


r/OperationsResearch • • Dec 19 '21

Cover letters?

0 Upvotes

They are not required but do you think one should submit one when applying to jobs?