Most Popular
1500 questions
12
votes
1 answer
Simplest way to eliminate redundant constraints due to a new cut
I have a polyhedral set for constraining $x$:
\begin{align}
\mathcal{P} = \{x \in \mathbb{R}^n_{+} : \ Dx \leq d \}
\end{align}
where $D \in \mathbb{R}^{m \times n}, d \in \mathbb{R}^m$. I find the Chebyshev center of this polyhedron, by solving:…
independentvariable
- 3,980
- 10
- 36
12
votes
1 answer
Complexity of verifying optimality in (mixed) integer programming
I looked around for a while, but I couldn't find a precise answer to the following question.
If I'm given a candidate solution for a (mixed) integer (convex) program, what's the complexity of deciding whether this solution (a point in the decision…
Tobia Marcucci
- 275
- 1
- 7
12
votes
1 answer
Recovering primal optimal solutions from dual sub gradient ascent using ergodic primal sequences
My question concerns recovering a primal optimal solution while performing dual sub gradient ascent. Denoting by $y_i$ the dual multiplier in the $i^{\text{th}}$ iteration, let
\begin{equation}
x_i = \underset{x \in X}{\operatorname{arg\,min}}…
batwing
- 1,458
- 6
- 15
12
votes
2 answers
Loss functions for specific probability distributions?
For a random variable $X$ with pdf $f(x)$, the loss function* is defined as
$$n(x) = \mathbb{E}[(X-x)^+] = \int_{x}^\infty (y-x)f(y)dy,$$
where $a^+ = \max\{a,0\}$. Or, for a discrete distribution,
$$n(x) = \mathbb{E}[(X-x)^+] = \sum_{y=x}^\infty…
LarrySnyder610
- 13,141
- 3
- 41
- 105
12
votes
4 answers
Normal demand and normal lead time; is lead-time demand normal?
In a continuous-review $(r,Q)$ inventory system under a type-1 service level constraint, if the demand per unit time is distributed as $N(\mu,\sigma^2)$ and the lead time, $L$, is a constant, then the lead-time demand also has a normal distribution.…
LarrySnyder610
- 13,141
- 3
- 41
- 105
11
votes
1 answer
Change coefficient in PuLP
Once a model is implemented in PuLP, how do you change a coefficient (e.g., $a_{ij}$, $b_i$ or $c_j$) of a program of the from $\min\{c^{\top}x: Ax=b, x\geq0\}$?
Specifically:
How to update coefficients or RHSs?
Once it is updated, do we have to…
Daniel Duque
- 1,355
- 6
- 20
11
votes
4 answers
Good resources for solving techniques (Metaheuristics, MILP, CP etc)
I want some resources (tutorials, online courses, lecture notes, articles, books, etc.) to learn the different techniques to solve OR problems (metaheuristics, CP, MILP, etc).
It would be better if the resources are practice-oriented, as near as…
Cloud
- 111
- 4
11
votes
2 answers
Fast validation of time windows in a routing problem
When solving a routing problem with time windows, unless you go for the arc-based math program that describes it, you have to check time windows "manually." For example, generating routes with any procedure would require this verification in the…
Daniel Duque
- 1,355
- 6
- 20
11
votes
2 answers
Assignment Problem with Decreasing Costs
Problem: I have $i$ jobs that I can assign to $j$ workers. Each job has a cost. Each worker can perform up to an arbitrary max number of jobs. However, there is a cost efficiency for each job that is assigned to the worker. For example, if two jobs…
David
- 309
- 1
- 4
11
votes
4 answers
Is there an open-source equivalent to LocalSolver?
I have a constraint programming problem that is easy to formulate and solve (with high solution quality) in LocalSolver. However, I would really prefer to use something open source for reproducibility. I tried using CP-SAT from Google OR-Tools,…
Kathryn Twomey
- 163
- 6
11
votes
1 answer
Termination Criteria of Solver in Pyomo
I am solving a nonlinear optimization problem using Pyomo with Ipopt as solver. The solver exits with the status:
EXIT: Optimal Solution Found.
This I can cross check by testing:results.solver.termination_condition == TerminationCondition.optimal,…
chupa_kabra
- 1,485
- 6
- 20
11
votes
2 answers
Finding an optimal set without forbidden subsets
Given $n$ items, I want to select a set items $S\subseteq\{1,2,\dots,n\}$ that maximize profit. The profit of item $i\in\{1,2,\dots,n\}$ is given by $p_i$ and may be assumed to be non-negative.
Additionally, I have a set $\mathscr{F}$ of forbidden…
Kevin Dalmeijer
- 6,167
- 1
- 17
- 48
11
votes
2 answers
Areas of mathematics to strengthen if interested in OR
I realize that this question may be off-topic, but I do not know where else can I find a 'social media' where OR practitioners hang out. I am about to finish my math BSc. and about to do my masters. I am interested in learning more OR, so I would…
AyamGorengPedes
- 431
- 2
- 11
11
votes
1 answer
Linear Programming - Motivation behind the Dual Simplex Method
I am trying to understand the motivation behind the Dual Simplex Method. However, I have run into some roadblocks while understanding the rationale behind the Dual Simplex Method. This is my current understanding of the Simplex, Primal and Dual…
MathMan
- 213
- 1
- 7
11
votes
5 answers
How to compute all paths between two given nodes in a network?
In this post, Erwin Kalvelagen describes a method to compute all paths between two nodes in a given network, such that:
no arc is used more than once
a given path does not contain more than $M$ arcs
Note that nodes can be revisited, and this is…
Kuifje
- 13,324
- 1
- 23
- 56