# Operations Research Stack Exchange Community Digest

## Top new questions this week:

### Branch and Price algorithm is exact?

I know that the Column Generation algorithm delivers an exact solution when you are solving a linear programming optimization problem. I want to know that, does this column generation approach deliver ...

optimization combinatorial-optimization column-generation branch-and-bound branch-and-price

### Are there any good models for min-max vehicle routing problem?

I am trying to model a min-max VRP problem with multiple delivery vehicles and I have come up with a model using branch and cut but I do not think it is strong enough as it takes lot of time to ...

mixed-integer-programming integer-programming vehicle-routing

### Min-cost flow with per-edge flow conservation

I am trying to solve a linear program that is identical to a min-cost flow problem, except for a difference in the flow-conservation constraint. Instead of the summed outgoing flow equaling the summed ...

linear-programming integer-programming network-flow

### Column Generation algorithm for VRP with Min makespan objective function

I want to solve a VRP with a column generation algorithm. The objective of the problem is makespan minimization. In more detail, I want to minimize the arrival time of the last vehicle in the depot. I ...

optimization mixed-integer-programming combinatorial-optimization vehicle-routing column-generation

### Faster implementation of "or" constraints in ILP

I have implemented a set of "or" constraints in my ILP using binary decision variables (as in this method). It works fine for smaller problems, but when I try to increase the number of ...

linear-programming integer-programming constraint binary-variable indicator-constraints

### How to evalute the quality of a solver (beyond solution quality and time efficiency)?

I built a solver for a classic scheduling problem. It has some exact methods and some heuristics methods. I want to judge the quality of the work beyond time efficiency and solution quality. For ...

solver reference-request applications

### How to decide between a inaccurate system and a accurate system with capacity constraints to do a stream of jobs

Let's say you have a list of at most N Jobs to be done which are coming in a stream. There are two kinds of systems that can do the job: System 1: A very fast system, which however, only does the job ...

optimization combinatorial-optimization

## Greatest hits from previous weeks:

### Open source MILP solver for quick “good enough” solution

I have a problem that I have already posted elsewhere in OR.stack, but the question is focused around a large binary MILP (about 1 million decision variables). Ultimately, I am more time constrained ...

optimization mixed-integer-programming integer-programming python

### Is This Constraint Convex?

I have a constraint that I believe to be convex and not affine which I think means that I can implement a relaxation. I will first define the full constraint, and then build up my (informal) reasoning ...

constraint convexity nonconvex-programming lp-relaxation

### How to implement a "generic" solver for scheduling problems?

I have been accepted for an internship for 6 months. The aim of this internship is to implement a "generic" solver for scheduling/production planning problems. This solver will bill a small prototype ...

solver scheduling algorithms software metaheuristics

### Polyhedra, Polyhedron, Polytopes and Polygon

About Polyhedra, Polyhedron, Polytopes and Polygon, what do they mean in the context of linear programming and what is the difference between them?

linear-programming terminology polyhedra

### Is there any relationship between KKT and duality?

I noticed the similarities between KKT and complementary slackness, but I do not fully understand it.

linear-programming duality kkt-conditions

### In an integer program, how I can force a binary variable to equal 1 if some condition holds?

Suppose we have a binary or continuous variable $x$, a binary variable $y$, and a constant $b$, and we want to enforce a relationship like If $x \gtreqless b$, then $y = 1$. How can we write ...

mixed-integer-programming linear-programming constraint integer-programming logical-constraints

### How to choose between high number of binary variables or fewer number of integer (not only 0 and 1) variables in a IP formulation?

When I have to write the formulation of an IP, I usually have the choice between writing $i\times j$ binary variables with two indices such as $x_{i,j}$ or, writing $j$ integer variables $x_i$. Is ...

modeling integer-programming binary-variable

## Can you answer these questions?

### Is this a common generalization of the independent set problem?

Suppose a minimum weighted independent set in a conflict graph with $n$ vertices. The basic version is where each vertex $i$ is associated with a weight $c_i$. i.e., there is a vector $C$ for the ...

reference-request graphs set-covering

### Non-numeric argument to binary operator in MILPModel of ompr package

I am familiar with how to use ompr::MIPModel but I am trying to learn how to use MILPModel to take advantage of the model build speed. A simplified version of my model is below. I have two decision ...

r