Most Popular
1500 questions
5
votes
1 answer
Identifying the variant of such a knapsack-like problem
I am not too familiar with variants of knapsack problems (or variants of possibly other classical OR problems), but I would like to identify the following Integer Programming problem:
$$\min_{x_i,y_{i,j}} \sum_i c_i x_i$$
subject to $$\sum_i…
Vergil
- 51
- 3
5
votes
1 answer
Reduced cost in column generation
I am following this tutorial to learn column generation.
`
https://co-at-work.zib.de/slides/Donnerstag_24.9/cgbpdw-coatwork-annotated.pdf
I have a couple of questions I thought someone experienced in this topic could help me understand.
How are the…
mars
- 629
- 4
- 8
5
votes
1 answer
Linearize minimum and maximum constraint with variable and constant
Let's say I want to linearize the restrictions: $ \min(0, y) \leq x \leq \max(0, y) $
Then I can define $y_{\max}$ and $y_{\min}$ such that:
$$ y_{\max} \geq 0 \\ y_{\max} \geq y \\ y_{\min} \leq 0 \\ y_{\min} \leq y \\ y_{\max} + y_{\min} = y $$
If…
Jean-Paul
- 153
- 5
5
votes
0 answers
How to use interpolation for problem parameters in Pyomo
I'm working on my first Pyomo DAE project to teach myself how to use it for trajectory optimization. I have generated an atmosphere lookup table with density and speed of sound as a function of altitude. Pyomo will not accept the following code…
machalot
- 51
- 1
5
votes
2 answers
Formulation of a constraint in a MIP for an element in different Sets
I have an element e $\in E$ with $E$ the set containing all elements e and $e \in Y_i$ with $Y_i \subseteq E$. Each set $Y_i$ has different attributes.
$G_j$ is a set of sets and the following holds: $ Y_i\in\ G_j $ and $\cup_j G_j =…
Georgios
- 1,193
- 5
- 21
5
votes
1 answer
How to call HiGHS solver from python PuLP MIP?
I have a large MIP built with PuLP in python, and want to utilize the HiGHS Solver. However, PuLP does not have the option to use HiGHS as a solver. One option I am aware of would be to use PuLP to write an MPS file, and call HiGHS via command…
Mason
- 515
- 4
- 8
5
votes
1 answer
Add constraint on objective of MPS file in automated way
I got an MPS file and a best know solution value for that problem. I do not know whether the MPS file contains a minimization or an maximization problem.
How do i programmatically create a copy of that MPS file and add a constraint saying that only…
worldsmithhelper
- 4,007
- 6
- 21
5
votes
1 answer
Flow problem with side constraints: how to eliminate subtours?
I am working on a flow problem with side constraints. More specifically, I have a usual flow problem, with constraints that require some arcs to have exactly one unit of flow on them. This makes the problem "hard", as the classic formulation for…
Kuifje
- 13,324
- 1
- 23
- 56
5
votes
3 answers
Model infeasible
What should you do when you face an infeasible solution? I have implemented the model with the dataset from the paper but found infeasible solution.
overboxed
- 593
- 1
- 12
5
votes
1 answer
How can we efficiently solve a large MILP with dense constraint matrix?
Large MILPs with block structures can be efficiently solved with decomposition methods (e.g., the Benders' decomposition), which exploit special sparse structures of the constraint matrices.
However, when a large MILP has a dense constraint matrix,…
Piwaldo
- 51
- 3
5
votes
1 answer
How to enumerate all vertices of a polyhedron as a stream
I need to find the vertices of a polyhedron from the defining halfspaces. In a previous question libraries for enumerating all vertices were mentioned.
However i have a very large polyhedron (~100,000 halfspaces and more) where enumerating all…
Daniel
- 103
- 6
5
votes
1 answer
Should I replace equality constraints by inequality constraints if the variables in the constraint appear in the objective?
Suppose I am minimizing a MILP and my objective is simply $\sum_i{x_i}$, where $x_i$ is binary. I also have a constraint saying that $1-\sum_j y_j = x_i$, $\forall i \in \mathcal{S}$, $\forall j \in \mathcal{S}$ where $\mathcal{S}$ is the set…
cholo14
- 233
- 1
- 5
5
votes
2 answers
Can Local Search Operators be formulated as a Mixed Integer Program?
Consider the situation of Vehicle Routing. Once we have an initial solution, one can apply various local search moves to improve it.
For example:
Removing a single customer from a route and inserting it into another route. (Relocate)
Removing a…
watchdogs132
- 233
- 2
- 6
5
votes
1 answer
Gurobi solver with multiprocessing does not reduce total solving time
Problem
I use the syntax of gurobi with multiprocessing to solve multiple problems in parallel. Even though multiple problems are solved concurrently, the solving time for a single problem increases significantly, so there are no benefits to use…
Qiu Junyan
- 91
- 4
5
votes
0 answers
Construct a direction of recession of the dual that is from growth to dual function
Consider the primal problem $$\begin{array}{ll} \text{minimize} & c^\top x\\ \text{subject to} & Ax = b\\ & x \geq 0\end{array}$$ where $ A \in \mathbb {R}^{ m × n}$ has rank $m$. Suppose that, in a certain iteration of the dual-simplex method,…
justlearningmath
- 51
- 2