Unanswered Questions
862 questions with no upvoted or accepted answers
15
votes
1
answer
309
views
Integrality gap in bilevel binary linear programming problem
I have a bilevel max-min optimization problem over binary variables, with constraints expressed using linear inequalities. The inner (minimization) problem is
$$
\begin{alignat}2
\min\limits_x&\...
13
votes
0
answers
240
views
Unpopular/Obscure solvers/algorithms that you used
There are many (numeric) optimizers which solve some subset of the set of multi-objective, black-or-grey-or-white box, robust, stochastic, mixed-integer, non-linear, non-smooth, manifold-constrained ...
- 5,442
12
votes
0
answers
177
views
which method has been used to automatically reformulate logical constraints in a standard MIP solver?
There are many of the formulations to linearize logical constraints by introducing new auxiliary binary or any appropriate variables and adding the corresponding constraints to the model. It can be ...
- 9,068
11
votes
0
answers
164
views
Characterizing the solution of a (non) linear maximization program
I have the following maximization program
\begin{align}
\max\limits_{\{q_i\}}&\quad\sum\limits_{i=1}^nq_i \\
\text{s.t.}&\quad\begin{cases} k_j \geq \sum\limits_{i=1}^n q_i^{1 \over \...
- 591
10
votes
0
answers
187
views
How to monitor/debug an optimization model in a production environment professionally?
I have seen this question How to avoid having your optimization models rusting?, which is kind of related, but I am more curious about the actual monitoring and the initial design of the software in ...
- 544
10
votes
0
answers
227
views
For the solution of complex gaming are we to leave behind approximation and fixed algorithms in favor of agents?
For an evolutionary extensive form game is the use of multi-agent systems a necessity or can more traditional approximate Nash equilibria and mean-field interactions suffice?
Few games can be ...
- 5,442
9
votes
0
answers
105
views
Adjusting duals heuristically
I am solving a scheduling problem-to find shifts and task schedules- using column generation. In essence, it is a set covering problem with additional constraints. The problem seems to be that the ...
9
votes
0
answers
230
views
Solving large-scale stochastic mixed integer program
What are some methods or algorithms for solving a large-scale stochastic mixed-integer optimization problem that runs on an hourly dataset for a year? Do we employ some kind of decomposition? (the ...
- 1,687
9
votes
0
answers
203
views
Ill-conditioned LP in Benders decomposition
I have implemented a Benders decomposition for a constrained network flow but the LP solver (Gurobi) warns me of the ill-conditioning of the subproblem dual LP. As you can see below, the coefficients ...
- 33.1k
9
votes
0
answers
182
views
Modelling resource dependency in the assignment problem
The assignment problem is well-studied and has a nice polynomial time algorithm. I'm interested in an extension of this problem where all edges are in a certain group and taking multiple edges from ...
CommunityBot
- 1
8
votes
1
answer
141
views
Is there any way to use Lazy constraints in Pyomo?
I would like to know if there is any way to implement a Lazy constraint in the Pyomo package. (As far as I know, the only way to implement such a constraint is by ...
CommunityBot
- 1
8
votes
0
answers
169
views
Traveling Salesman Problem: determine k-exchange feasibility
Given a current solution $S$ and a $k$-exchange move $(v_1, .., v_{2k+1})$ with $v_1 = v_{2k+1}$, $v_i \neq v_j$, $(v_i, v_{i+1}) \in E(S)$ iff $i$ odd, i.e. we remove all edges $(v_i, v_{i+1})$ for $...
- 2,623
8
votes
0
answers
117
views
Multiple shipments with FILO order
I am trying to solve a problem statement with the help of jsprit.
There is a depot.
Identical items need to be delivered or picked up. An item can have two states: Bad or good.
Bad items need to be ...
- 1,895
8
votes
0
answers
112
views
For subset selection regression as a mixed integer program, how tightly should the bounding box be set?
When solving best subset regression as a mixed integer program, how do you decide how tightly to bound the range of values of the $X$ values? When the box is tight, the solver finds a solution ...
- 5,442
8
votes
0
answers
102
views
Examples for a kind of "set family hitting" problem
Given a ground set, say $[n]=\{1,2,\dots,n\}$, and a collection of subset families $\mathcal F_i\subseteq 2^{[n]}$, $i=1,2,\dots,m$, I want to select $m$ sets $B_i\in\mathcal F_i$ such that the ...
8
votes
0
answers
156
views
Is a base-stock policy optimal for a serial inventory system with upstream stockout costs?
In a serial inventory system without fixed costs, an echelon base-stock policy is known to be optimal if there is no stockout cost at any stage except the last stage. (This was proved for finite-...
- 5,442
7
votes
0
answers
107
views
MIP formulation for graph planarity test
In this question, it was asked wether a MIP formulation exists to test for a graph's planarity. The inputs are the graph's nodes and edges, and the output would be a certificate which guarantees that ...
- 13.6k
7
votes
0
answers
118
views
What distuingishes a model-and-run framework solver from a programmatic solver?
I am looking for examples to understand what kind of benefits a model-and-run framework solver offers that a more programmatic solver doesn't do or doesn't do as well.
What distinguishes a model-and-...
- 4,937
7
votes
0
answers
118
views
List of Call for papers
Is there somewhere a list of ongoing Call for papers for special issues in OR journals?
I believe that such a list would not only create a good overview for publication opportunities but also inform ...
- 1,706
7
votes
0
answers
122
views
Estimate lagrangian multiplier based on instance characteristics
Assume we have a simple resource allocation problem, where all players have the same cost, but a different utility $a_s$. The resources assigned to a certain player must be between $L$ and $M$. ...
- 123
7
votes
0
answers
149
views
Is this a valid strong polynomial algorithm for deciding LP feasibility?
Let
$$A \cdot X + B \preceq 0$$ be a system of linear inequalities with $X \in \mathbb{R}^n$ $A\in \mathbb{R}^{m\times n}$ and $B \in \mathbb{R}^m$ where $m \geq n$. According to Farkas lemma, exactly ...
- 507
7
votes
0
answers
166
views
Modelers and modeling languages: how do you choose, and which features do you use?
There are many modeling languages and APIs around. One or more per solver, plus many that target multiple solvers: AMPL, GAMS, PuLP, JuMP, Pyomo...
Among all these possibilities, why did you pick a ...
- 5,442
7
votes
0
answers
151
views
Modeling traffic in a city
I am trying to model traffic in a city, $(i,j)$ represents a road in a city.
There are $H$ vehicles in a city they have some prescheduled set of destinations to visit, $A_{j,h}$ denotes arrival time ...
- 5,442
7
votes
0
answers
93
views
Building the Scheurman's Model II constraints for a multi period linear program
Scheurman's paper discusses Model I and model II Formulation to solve harvesting and scheduling problems. It is a specific implementation to solve multi period linear programs. Both models are also ...
- 153
7
votes
0
answers
80
views
Which Constraint solver is extensible to CSP algorithms?
I am novice to constraint programming and I need to implement the following algorithms.
Backtacking
Conflict-based backjumping
AC partial lookahead
MAC
Forward checking
Forward checking + dom
...
- 87
7
votes
0
answers
156
views
Why does PuLP call copy for addition and how can I avoid it?
Using a for loop to append terms to an expression seems to be much faster than summing a group of terms all at once. Constructing the expression using a for loop uses __iadd__, which does not include ...
- 261
7
votes
0
answers
81
views
Modelling a simple ordering problem to have balanced delivery days
Assuming that I should buy 50 items from 25 different vendors with pre-known delivery duration between 2-7 day for each, which day of a week should I place each order so that the delivery days be even ...
- 5,442
7
votes
0
answers
91
views
KKT conditions validation- one dual variable equating to two values
I have the following optimization problem:
\begin{alignat}2\min &\quad A(t)\cdot x(t)-B(t)\cdot y(t)+C(t)\cdot z(t)-D(t)\cdot k(t)\\\text{s.t.}&\quad z(t)+z_1(t)-y(t)-y_1(t)+x(t) = k(t);&...
- 5,442
7
votes
0
answers
176
views
Relationship between two minimization problems
Let $\mathbf{A}$ be a ${n\times J}$ matrix with $A_{ij}\geq0$ (and $A_{ij}>0$ for most $ij$, there cannot be any rows or columns that consist only of $0$s), $Q=\left\{\mathbf{q}\mid \mathbf{q}\in\...
- 591
7
votes
0
answers
885
views
Having trouble with objective function in Python: "GurobiError: Variable not in model". What else could I try?
I am trying to figure out how I can write this objective function into python using Gurobi. I have to minimize the sum of the product of three dictionary's values. The reason I am confused is that ...
- 5,442