Most Popular
1500 questions
6
votes
2 answers
Linear Program: Verify whether a feasible solution is an extreme point
My question is about a Linear Program (LP) of the form $\bf Ax\ge b$ with $\bf x\ge0$.
From a theoretical standpoint: Given a feasible solution $\mathbf{x^{(0)}}$, how can we check (verify) whether it is an extreme point?
I found this on the web,…
Shuxue Jiaoshou
- 155
- 7
6
votes
8 answers
Ideal programming language for an operations researcher
No single programming language will meet every need. However, there should be a language that most operations research scientists prefer to master.
I have coded different algorithms in Matlab and Python so far, but they may not be fast enough in…
mdslt
- 615
- 3
- 8
6
votes
1 answer
Absolute value in an equality constraint
What is the best way to model or represent an equality constraint which includes an absolute term in the expression:
$$ x = |y| $$
$x \in \mathbb{R^+}$ and $y \in \mathbb{R}$
Ahmed
- 113
- 4
6
votes
1 answer
What exactly is the optimality-gap or what does it say in integer linear programming?
I am working since a few months with gurobi and did figure out, that the gap says how far a feasible solutions is away from the optimal solution. However, what does say it exactly?
The gurobi docs says it depends on the upper and lower objective…
Mike
- 147
- 1
- 6
6
votes
1 answer
Valid Inequality Example (Wolsey Example 9.3)
I was following Wolsey Example 9.3: Let $X = \{(x,y) \in (R^{m}_+,B^1) : \sum_{i=1}^m x_i \leq my\}$. Now consider the valid inequality $x_i \leq y$ and show that it is facet defining.
My question is why is this a valid inequality? For example one…
Joshua
- 61
- 2
6
votes
2 answers
Good sources on developing mathematical models
What are good sources (literature, internet, etc) on learning to model real-world problems using mathematical formulations?
In particular, I would like to know sources which establish the relationship between the meaning of a mathematical construct…
decision maker
- 119
- 5
6
votes
1 answer
Quadratic constraints in JuMP
I am a bit new to programming and am currently working with solving optimization problems in JuMP in Julia.
I got a tip from the JuMP page that I should also use @constraint if a term is quadratic. However, how do I know if a constraint is…
Annaquest
- 63
- 4
6
votes
1 answer
How to solve this linear program with an exponential number of constraints?
Consider the following convex program:
\begin{align*}
\min g(x) && \text{such that}
\\
f_i(x) &\geq b_1 && \text{ for } i \in 1,\ldots,n;
\\
f_i(x)+f_j(x) &\geq b_1+b_2 && \text{ for } i,j \in 1,\ldots,n;
\\
f_i(x)+f_j(x)+f_k(x) &\geq b_1+b_2+b_3 &&…
Erel Segal-Halevi
- 989
- 5
- 18
6
votes
2 answers
When should we avoid linearizing a quadratic term?
Some solvers like Gurobi can handle mixed-integer quadratically-constrained quadratic models regardless of their nonconvexity. I have some experience that Gurobi can handle instances of the max $k$-cut problem with nonconvex objective function…
Ramin Fakhimi
- 189
- 8
6
votes
0 answers
Benders decomposition for a dense MILP
I am trying to solve a large MILP, but it seems like dense problems can be very difficult for moderns solvers. I tried to solve the problem described below considering only constraints (1) and (2) that is the case where x is from the binary set B…
Enthusiast
- 109
- 3
6
votes
2 answers
How to represent a constraint on the kth-smallest function?
How can I represent the following set of constraints in a linear program, where $c_1,\ldots, c_n$ are constants and $f_1,\ldots,f_n$ are functions of the optimization variables?
The smallest of $f_1(x),\ldots,f_n(x)$ is at least $c_1$;
The…
Erel Segal-Halevi
- 989
- 5
- 18
6
votes
0 answers
Graph coloring problem while counting cliques
Let $G$ be a graph with a set of nodes $V$ and a set of edges $E$.
Let $G'$ be a graph with the same set of nodes $V$ but a second set of edges $E'$.
For a set of nodes $X\subset V$, we denote $f(X)$ as the number of cliques (using the edges $E'$)…
Jin Kazama
- 93
- 4
6
votes
1 answer
When was the exploration and exploitation tradeoff first mentioned in literature?
I've recently been exploring Reinforcement Learning (RL) methods in my work and the exploration-exploitation dilemma is always mentioned. It almost feels like the exploration-exploitation dilemma stemmed from RL research. However, when we think…
jkschin
- 365
- 2
- 5
6
votes
1 answer
How to Model Path Being Only Through Adjacent Cells
I am trying to develop a MILP for a path planning problem. I am operating on a grid of cells that represents a map. The arrangement of cells in the grid represents the placement of the cells in real life on a physical space. I would like to generate…
Raghav Thakar
- 325
- 1
- 10
6
votes
2 answers
Metaheuristics vs Column generation for VRP
I am solving a vrp and its variants (pick up drop off, milk-run problem) using genetic algorithms. The issue that I am getting with the genetic algorithm is the randomness associated with the algorithm. Although randomness is an expected property of…
mars
- 629
- 4
- 8