Operations Research Stack Exchange
Operations Research Stack Exchange

Most Popular

more tags
1500 questions
5
votes
2 answers

In a MIP, how to force a decision variable to be zero unless the sum of specific other decision variables is equal to a certain number?

In an MIP, how can I formulate a constraint such that a decision variable is only greater (or equal to) zero if (and only if) the sum of different decision variables is equal to something. I'm working with a path flow formulation model and I want to…
AnneBart
  • 51
  • 3
5
votes
1 answer

What are (some of) the best resources for shift scheduling/rostering?

Shift scheduling/rostering is obviously very widely researched, with tons of papers around it. I found the review papers by Van den Bergh et al. [1] and Ernst et al. [2], but am looking for something that actually shows the various types of math…
Richard
  • 3,459
  • 7
  • 19
5
votes
1 answer

Use of comparisons in objective function of an ILP

If the objective function of a problem contains a comparison between two linear statements, can the problem still be defined as an Integer Linear Program? For example: $$\text{max} \sum_{\forall i,j} x_{i,j} - (y_{i,j}\cdot A_{i,j} \ge…
yucelf
  • 53
  • 4
5
votes
3 answers

Infeasibility False Positive

Is it possible/likely for a mixed integer linear solver (CBC in my case) to incorrectly state that a problem is infeasible when in fact it is actually feasible? Are there properties of the model that could exacerbate this? For example, large…
fishstix44
  • 153
  • 1
  • 4
5
votes
0 answers

Reduction from Steiner Tree to TSP

The Steiner Tree version that I am considering is the following: given an undirected weighted graph $G=(V,E)$ and a subset of vertices $T \subseteq V$, find a minimum tree that connects all the vertices in $T$ which possibly contains vertices…
user12632521
  • 111
  • 4
5
votes
1 answer

Python PuLP - Unable to Model Non-Square Matrix

I am having issues with setting up constraints using both input arrays from excel and variable arrays within PuLP. It appears the model only works with square matrices and my final code has a matrix that is 365x24. The code below has a matrix of…
bathtub2007
  • 53
  • 4
5
votes
4 answers

Solving Capacitated VRP with multiple various sized vehicles

I am looking to form a Capacitated VRP problem like this: I have 40,000 dropping locations with Demands of each point available I have 5-6 types of vehicles available with different capacities and costs I know the cost of travelling from one point…
Shibaprasad
  • 529
  • 3
  • 10
5
votes
2 answers

Combinatorial optimization, implementation needed

I have k sets of items. I want to choose n items from each set, $n \cdot k$ items total. I would like to choose the $n \cdot k$ items under some optimization criterion, e.g. that the sum of the $\ell_1$ distance between every pair of items is…
Joseph Turian
  • 153
  • 2
5
votes
2 answers

How to linearize specific range constraints?

I would like to know about the linearization of the $(If, Then)$ constraints as follows: $$\begin{array}{l} \text { If: } \\ 15 \leqslant x \leqslant 25 \\ \text { then: } \quad y=\color{blue}{a} x+\color{green}{b} \\ \text { elself: } \\ 25…
A.Omidi
  • 8,832
  • 2
  • 13
  • 49
5
votes
2 answers

Optimization When True Costs Are Unknown

Here is a problem I thought of: Suppose there is a car repair shop and 5 mechanics work there. Everyday, new cars arrive at the shop and each mechanic has to choose 3 cars to work on. In short, the mechanics ideally want to choose cars that they…
stats_noob
  • 1,831
  • 7
  • 30
5
votes
1 answer

Breadth First Search vs. Best First Search

What is the main difference between Breadth First Search and Best First Search? What is meant by saying Breadth First Search requires previous knowledge?
mcek
  • 45
  • 1
5
votes
1 answer

Does exchanging integer variables by binary variables strengthen a MIP?

Suppose that I have an MIP with a whole lot of continuous variables and some integer variables. In my case, this takes a very long to solve (in fact I wasn't able at all to solve it to optimality). So I was wondering if it would be beneficial for…
Noah D.
  • 93
  • 2
5
votes
1 answer

if $x = 0$ then $y \ne b$

I'm trying to model the following: if $x=0$ then $y \ne b$ $y$ is a positive integer number( $y\le U$) and $x$ is binary and $b$ is a constant.
AComputer
  • 153
  • 3
5
votes
3 answers

How to represent an integer variable via binary variables?

Suppose we have a model with $N$ integer variables, i.e. $x \in \mathbb{Z}^{N}$ with $L \leq x \leq U$. How can we represent the integer variables via binary variables? Or in other words: how can we transform an integer programming problem into a…
Ronaldinho
  • 385
  • 2
  • 5
5
votes
4 answers

Numbering the vertices of an $n$-layer graph so that edges have similar numbered vertices on their ends

Consider a graph whose vertices can be partitioned into $n$ layers. Edges exist only between vertices in successive layers. So, there are edges between layers $1$ and $2$, between layers $2$ and $3$ and so on but never between layers $1$ and $3$…
Rohit Pandey
  • 343
  • 1
  • 10
1 2 3
…
99 100