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  
asked by A.A 10 votes
answered by Kuifje 9 votes

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  
asked by Morpheus 5 votes

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  
asked by funky_capybara 5 votes

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  
asked by Bahar 4 votes
answered by RobPratt 4 votes

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  
asked by Animik 4 votes
answered by RobPratt 5 votes

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  
asked by Joffrey L. 4 votes
answered by Richard 3 votes

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  
asked by dg428 3 votes
answered by A.Omidi 1 vote

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  
asked by S moran 8 votes
answered by T_O 8 votes

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  
asked by GrayLiterature 13 votes
answered by Mark L. Stone 18 votes

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  
asked by Amira Zarglayoun 11 votes
answered by A.Omidi 8 votes

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  
asked by A.Omidi 14 votes
answered by TheSimpliFire 19 votes

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  
asked by Amos 8 votes
answered by Kevin Dalmeijer 21 votes

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  
asked by LarrySnyder610 22 votes
answered by LarrySnyder610 23 votes

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  
asked by JonathanZ 13 votes
answered by Marco Lübbecke 17 votes

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  
asked by Mostafa 1 vote

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 ...

asked by Ralph Asher 3 votes

Theoretical aspect of using extended formulation

If I can show a polyhedron Y is an extended formulation of polyhedron X and every extreme point in Y is integral, does that automatically imply the projection of Y onto the variable space of X gives ...

integer-programming polyhedra convex-hull  
asked by Octavia 1 vote
You're receiving this message because you subscribed to the Operations Research community digest.
Unsubscribe from this community digest       Edit email settings       Leave feedback       Privacy
Stack Overflow

Stack Overflow, 110 William Street, 28th floor, New York, NY 10038