Most Popular
1500 questions
8
votes
1 answer
Formulating two non-negative variables without binary and/or big-M
There are two non-negative integer variables $q$ and $p$, where only one of them can take a positive value. To impose this relation, I write:
\begin{align}
q &\leq M(1 - y) \tag1 \\
p &\leq M(y) \tag2
\end{align}
where $y$ is binary and $M$ is a…
Mostafa
- 2,104
- 10
- 28
8
votes
1 answer
What does "Concurrent spin time" mean in the Gurobi log and what does choosing Method=3 do?
We are using Gurobi 9.0.2 to solve complex mixed integer linear programs for which we are attempting to maintain total unimodularity (TUM). In our log file we see things like this:
Concurrent spin time: 13403.45s (can be avoided by choosing…
vy32
- 183
- 4
8
votes
4 answers
Algorithm for simplifying a set of linear inequalities
I am looking for an algorithm that, given a set of linear inequalities in $m$ variables, returns a simplified set. "Simplified" may mean an equivalent set with a smallest number of inequalities. If finding an optimal solution is…
Erel Segal-Halevi
- 989
- 5
- 18
8
votes
4 answers
Understanding integer programming solvers
I would like to verify if I understand the nature or workings of integer programming solvers.
My understanding is that for integer programming problems like the knapsack problem or the traveling salesman problem several algorithms can be used to…
spdrnl
- 249
- 1
- 4
8
votes
2 answers
OR-TOOLS : delivery node with multiple possible pickup nodes
I am using ortools to model a VRP with pickup and delivery constraints, where pickups can be done at different nodes. For example, if node A has a demand, it must be picked at node B or C.
Here is how I do this:
# data["pickups_deliveries"] is a…
Kuifje
- 13,324
- 1
- 23
- 56
8
votes
3 answers
How to determine different gap rates?
I found in the literature different gaps:
a gap between a random solution and an exact solution
a gap between the exact solution and a lower bound
a gap between the exact solution and a lower bound
a gap between lower bound and upper bound
I am…
fathese
- 423
- 2
- 5
8
votes
1 answer
No, Gurobi, I really do want this variable to be binary
When I mark a variable in a Gurobi MIP model as binary, sometimes Gurobi gives me a solution where that variable has a fractional value other than 0 or 1. How do I constraint a variable to be honest-to-goodness truly binary?
The Gurobi…
D.W.
- 230
- 1
- 10
8
votes
0 answers
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-horizon problems by Clark and Scarf (1960)1 and for…
LarrySnyder610
- 13,141
- 3
- 41
- 105
8
votes
1 answer
Specific algorithms to compute the LP-relaxation of the Set-Cover problem
One of the most commonly known combinatorial problems is the set cover problem, which states that given a collection of sets $S = \{s_1, \dots, s_m\}$ and a universe of elements $U = \bigcup_{i=1}^m s_i$ we should select the minimum number of sets…
Paul Bouman
- 2,100
- 5
- 17
8
votes
2 answers
Simplex-Implementations in professional Solvers
Which non-textbook variants (primal/dual, revised) and techniques (e.g. steepest-edge) do professional solvers like Xpress, CPLEX, CLP use, to get the best out of the simplex algorithm?
This question is about the Simplex algorithm for LP only, not…
Gehhilfe
- 453
- 3
- 6
8
votes
1 answer
What is robust optimization?
What is the academic definition of robust optimization?
What are examples of robust optimization on:
shift rostering
vehicle routing problem
facility location problem
bin packing
...
Geoffrey De Smet
- 4,851
- 10
- 34
8
votes
2 answers
knapsack problem with non-linear constraint
I have a basic knapsack problem where I need to fit the most weight possible in a bin:
import pyomo.environ as pyo
w = {'hammer': 5, 'wrench': 7, 'screwdriver': 4, 'towel': 3}
limit = 14
M = pyo.ConcreteModel()
M.ITEMS =…
Cesar Canassa
- 215
- 1
- 5
8
votes
2 answers
(Iterative?) Solutions to a certain quadratic program with non-convex constraints
Let $y\in\mathbb{R}^m$, $\tau\in\mathbb{R}$ and $X\in\mathbb{R}^{m\times n}$, with $\tau>0$
I would like to efficiently solve the following problem:
Problem 1
Choose $\alpha,z\in\mathbb{R}^m,\beta\in\mathbb{R}^n$ to minimize:
$$(y-\alpha)^\top…
cfp
- 259
- 1
- 8
8
votes
2 answers
Alternatives for real-world data collection in simulation courses for Fall 2020
I teach a discrete-event system simulation course in Fall 2020. As with most DES simulation courses, students have term projects that involve gathering real-world data and building stochastic input models that they can use to do a simulation study…
Ted
- 81
- 2
8
votes
1 answer
Optimization software for ARM Architecture
Given that tomorrow Apple will likely announce the first ARM Macs (per bloomberg), I was wondering what the current status of ARM support in optimization software. For instance, does anyone know if Gurobi or CPLEX plan on supporting ARM? Is there…
Connor
- 431
- 2
- 9