Operations Research Stack Exchange
Operations Research Stack Exchange

Most Popular

more tags
1500 questions
6
votes
2 answers

What is a general procedure to prove that the LP relaxation of an IP delivers the optimal IP solution?

Say that I have a binary IP $$z=\max_x \{c^\top x: Ax=b, x\in B^n\}$$ where $B^n$ is the set of $n$-dimensional $0-1$ vectors. Its LP relaxation will be $$z^{LP}=\max_x \{c^\top x: Ax=b, 0\leq x\leq 1\}$$ I empirically observe that $z^{LP}=z$ and…
k88074
  • 1,661
  • 8
  • 18
6
votes
3 answers

How to improve the quality of code in OR?

So I noticed, that a lot of students taking OR-classes come from non-computer science backgrounds (e.g. buissiness administration). They typically had only one other class in their first semester where they had to write (typically java) code, and…
PSLP
  • 2,401
  • 9
  • 33
6
votes
1 answer

Can I replace the objective function $f$ with $g$ if $g \ge f$?

I am working on a project where the customer requested to change the current objective function $f$ to another function $g$ (both linear). It is easy to prove that $f \le g$ and as both are linear funcions my guess is that the hyperplane each define…
huig
  • 83
  • 6
6
votes
1 answer

How are indicator constraints implemented?

I wonder how systems like CPLEX, GUROBI, etc implement indicator constraints. Do they just implement Big M equivalents? If yes, what is then the justification for using them? Edit The question does not concern when to prefer using BigM constraints…
Clement
  • 2,252
  • 7
  • 13
6
votes
2 answers

Priority List Constraint

I used the Vehicle Routing Problem example that has the objective of minimizing total distance traveled for each vehicle. Suppose that each order to pick up for each vehicle at each node has a priority list, i.e. expedited vs standard. How can I…
Mario Huang
  • 101
  • 3
6
votes
1 answer

Convert summation of min functions into linear constraints for optimization

I have the following optimization problem: $$ \mbox{maximize } j^{*} \mbox{ subject to:} \sum_{j^{*}\leq j\leq J} \min({\bf A}_j,{\bf B}_j) \geq \lambda, \lambda \in \mathbb{R} \mbox{ and } {\bf A}_j,{\bf B}_j > 0 \forall j $$ where the values of…
jackson95
  • 63
  • 4
6
votes
2 answers

What is the definition for an integer-friendly constraint?

I have seen some papers claiming that their proposed model is integer-friendly. I would like to get more information about what type of constraints we can call integer-friendly. Probably, it can be better understood if I have some examples. Here is…
Mostafa
  • 2,104
  • 10
  • 28
6
votes
1 answer

Is there a name for this variation of the assignment problem?

I'm given two matrices: $A$, an $n\times n$ adjacency matrix of a graph. The graph is unweighted, undirected and has no self-edges or multi-edges. $X$, an $n\times n$ symmetric matrix of edge weights for items $x_1,\dots,x_n$ where entry $(i,j)$…
user3636
  • 63
  • 3
6
votes
0 answers

Proof that the leaving variable cannot be selected as the entering one in the next round

Using the Dantzig's pivoting rule, can it be proven that the leaving variable of one round cannot be selected as the entering variable in the next round?
Clement Cloucharde
  • 61
  • 2
6
votes
1 answer

Linearize a product of an integer variable (not just binary) and a continuous variable?

I have a constraint in my formulation that contains multiplication of an integer variable $y$ and a continuous variable $x$, which is $xy=q$ where $y$ is the number of units in which $q$ gets equally divided to get the quantity $x$ in each unit. Is…
optimizationguy
  • 61
  • 3
6
votes
2 answers

Lagrangian Relaxation for Two-Stage Stochastic Program

I have a two-stage stochastic program as follows: \begin{align}\max&\quad f^\top y+\sum_{s}p_sc_s^\top x_s\\\text{s.t.}&\quad Ay=b\\&\quad W_sX_s+Ty \le h_s \quad \forall s \in S \\&\quad P_sx_s \le q_s \quad \forall s \in S \\&\quad x_s \ge…
Amin
  • 2,150
  • 7
  • 20
6
votes
2 answers

How to handle bigM in sub-problem of benders decomposition?

Suppose you want to solve a MIP with Benders decomposition and the binary variables ($y_i$) are fixed in the master problem but these variables are used in the sub-problem with bigM like $x_{ij} \le M.y_i \quad \lambda_{ij}$ where $\lambda_{ij}$ is…
Amin
  • 2,150
  • 7
  • 20
6
votes
1 answer

When using column generation, can I delete a node with negative reduced cost from my subproblem?

I am solving a minimization problem with a column generation procedure. The master problem is of the form $$ \min \sum_{i\in \Omega}c_i \lambda_i $$ subject to $$ \sum_{i\in \Omega \mid v \in i } \lambda_i = 1 \quad \forall v \in V $$ Columns…
Kuifje
  • 13,324
  • 1
  • 23
  • 56
6
votes
2 answers

Find a point inside non-empty difference of ellipsoids

Given two ellipsoids \begin{align}\mathcal{E}_1 &= \{ X \mid X^\top A_1 X + 2B_1^\top X + C_1 \leq 0\}\\\mathcal{E}_2 &= \{ X \mid X^\top A_2 X + 2 B_2^\top X + C_2 \leq 0\}\end{align} are both non-empty, it is possible to test if $\mathcal{E}_1…
C Marius
  • 507
  • 2
  • 7
6
votes
3 answers

Is it abnormal for a model to take 8+ hours to solve?

I am building my first optimization model, it is quite large and also a non-linear problem. I have had my model solving on the NEOS Optimization Server and after 8 hours of trying to solve, the server cut out because it reached a time limit. So what…
GrayLiterature
  • 2,309
  • 7
  • 27
1 2 3
…
99 100