Operations Research Stack Exchange
Operations Research Stack Exchange

Most Popular

more tags
1500 questions
7
votes
1 answer

Is Dantzig-Wolfe decomposition finite if variables are unbounded?

Most descriptions of the Dantzig-Wolfe decomposition, I have seen end up with subproblems like this: $$\min_{x_j \in \mathbb{R}^n} \{ (\pi A_j - c_j)x_j \mid x_j \in P_j \}$$ They argue that $P_j$ can be described with a finite number of extreme…
Florian Pommerening
  • 385
  • 1
  • 7
7
votes
1 answer

Expressing a chain of boolean if-then with logical ANDs using MIP

How to express a chain of boolean If-then as MIP such as: If $(x_{10} \ge b_1$ and $x_{11} \le b_1)$ AND $(x_{20} \ge b_2$ and $x_{21} \le b_2)$... AND... then $y_1 = 1$ else $y_1 = 0$. So basically, if constants are between values of different…
GregK
  • 71
  • 2
7
votes
1 answer

Custom Nurse Rostering Problem

I've asked this question also on Math Stack Exchange. It's a custom nurse rostering problem: $N$ is a set of nurses; $S$ is the set of shift-type (morning, afternoon, night, rest) $n_\mathrm{Morning}$ is the number of nurses required every day to…
Overflow 404
  • 73
  • 8
7
votes
1 answer

Why is there a constant in the objective function of the *best subset selection problem*?

This article presents the following formulation of the best subset selection problem $$\min_{\|\beta\|_0\leq k}\frac{1}{2}\|y-X\beta\|^2_2$$ I wonder where the $1/2$ comes from. Help appreciated.
k88074
  • 1,661
  • 8
  • 18
7
votes
0 answers

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 Forward checking + LCV' Is it easy to extensible with…
Cecelia
  • 87
  • 2
7
votes
1 answer

Variant of job shop scheduling problem

I'm looking to identify a problem in the literature that I'm currently solving. I have a set of jobs each having a set of operations. Each operation has a duration. An operation may be done by a machine, from a set of machines, that can process the…
Stephen Hill
  • 81
  • 3
7
votes
1 answer

Design choices on how to implement several algorithms for the same problem

When one is interested in solving a problem but considering different objective functions the choice is easy, a class for problem, a class for solution and a class by algorithm then in the main function (or file) we just need to call the appropriate…
Antarctica
  • 2,917
  • 15
  • 34
7
votes
0 answers

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 a call to copy. The other methods of building…
Charles Fox
  • 261
  • 1
  • 6
7
votes
2 answers

shadow prices associated with nonnegativity constraints

Why are shadow prices associated with nonnegativity constraints also called as reduced costs, even if they have the same interpretation as shadow prices associated with an optimal solution? Why the use of the term "reduced cost"?
naive
  • 173
  • 3
7
votes
0 answers

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 and balanced and even as much as possible? What…
Sean
  • 159
  • 2
7
votes
3 answers

Constraint programming using solver: how to state the time limit of search?

Could someone give additional explanations about the TimeLimit of CPLEX for CPO? I am using CPLEX to solve a problem of assignment and scheduling in which each task needs to be assigned to a worker, by respecting a correct sequence. There is a cost…
campioni
  • 1,133
  • 5
  • 13
7
votes
2 answers

Max flow problem without splitting the flow from the supply nodes - LP formulation help

Since max flow formulation can be easily solved using LP, I wanted to ask the following: I am trying to solve a simple max flow problem where the graph is bipartite but with one added constraint. The constraint is that the flow from any supply node…
prakash gawas
  • 173
  • 4
7
votes
3 answers

Finding a solution to a linear program with a small number of zeros

It is known that, in a linear program with $k$ constraints, there exists a basic feasible solution in which at most $k$ variables are non-zero. How can I find such a solution? Is there a polynomial-time algorithm for this? I know that the simplex…
Erel Segal-Halevi
  • 989
  • 5
  • 18
7
votes
0 answers

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);& \lambda(t)\\&\quad0 \le x(t) \le \bar{X};&…
S_Scouse
  • 803
  • 3
  • 11
7
votes
1 answer

Is this formulation linear or non-linear?

Can you help me figure out if this formulation constitutes a non-linear problem? I believe It is a linear problem but my solver (GAMS) is unable to produce a acceptable solution. $x,y$ and $\text{state}$ are variables and the rest are…
MiguelL
  • 81
  • 4
1 2 3
…
99 100