Paul Bouman
  • Member for 2 years, 5 months
  • Last seen more than a week ago
Find feasible point in polynomial time in linear programming
Accepted answer
19 votes

It is not true that the Two-Phase methods requires Simplex iterations, it is just the common way to do it. Let's assume we have a linear program with $n$ variables and $m$ constraints. Step 1) ...

View answer
Algorithms vs LP or MIP
Accepted answer
18 votes

As mentioned earlier, all algorithms are constructed using loops and conditional statements, including the algorithms employed by LP/MIP solvers. There are plenty of problems where it is more ...

View answer
To which area does constraint programming belong?
11 votes

In general, I think Constraint Programming or Constraint Satisfaction Problems have their roots in Computer Science/Artificial Intelligence communities that may or may not overlap to some extent with ...

View answer
What is a "hard problem" in the context of Mixed-integer programming?
10 votes

In the context of computational complexity theory, a hard problem typically refers to an infinite set of problem instances for which it is widely believed that the worst-case amount of work needed to ...

View answer
Intuition behind more-for-less transportation paradox?
Accepted answer
8 votes

While it may seem reasonable to think that costs increase when you increase production, the transportation problem only considers the costs of moving things around. As a consequence, increasing ...

View answer
How to choose an architecture for an OR web app and how to learn the tech stack associated?
7 votes

Earlier this year I needed a web application to let some Chinese students (with varying English language proficiencies) play around with models for Timetabling and Rolling Stock scheduling. I used an ...

View answer
How to formulate: each pair of elements in $A$ has one common unit in $B$
6 votes

For the at-least variant, it seems you can write down this problem as propositional logic and convert your constraints into Conjunctive Normal Form, which gives you the constraints you need only using ...

View answer
How does a solver generally know whether a solution is optimal?
5 votes

Optimality implies that a proof was constructed that proves there does not exist a better solution than the best feasible solution found. A brute force search does indeed give you a (rather long) ...

View answer
Can this be formulated as one inequality
5 votes

If you are willing to introduce an additional binary variable and your goal is to have only a single constraint on $y$, you could do the following: Introduce three binary variables $\zeta_{10}$, $\...

View answer
Polynomial algorithm for a special ILP problem
Accepted answer
5 votes

Let us get some additional insights by assuming $d_{ij} \in \{0,1\}$ and interpreting the data as a directed graph. For now we assume the number of $i$'s and $j$'s is the same, but I don't think it ...

View answer
Theoretical results on performance of branch-and-bound
5 votes

If the problem you are solving is in $P$, I guess you can construct a branch-and-bound algorithm that only produces a polynomial number of nodes, since you can use your polynomial time algorithm to ...

View answer
Formulation of Assignment problem as integer programming
Accepted answer
4 votes

Since you mention that you want to operate two out of three machines, it boils down to a problem where you first pick two machines and then perform a standard $R2||C_{\max}$ parallel machine ...

View answer
The difference between max-min and min-max
4 votes

While these equations have many interpretations in OR (e.g. robust optimization), in this case I like to understand what happens here using a Game Theory perspective. These two equations can be ...

View answer
Dynamic programming problem with machines
4 votes

For the following I did not check in depth the rules related to end-of-period/beginning of period, so this is something you should carefully check for your problem. However, the approach does not ...

View answer
Find all Combinations of a Matrix
Accepted answer
4 votes

It sounds like what you want is to reduce each vector in your matrix to the relevant entries, and take the Cartesian Product of the column vectors. That is definitely not a problem where linear ...

View answer
Is the "reverse search" algorithm of David Avis the state-of-the-art method for finding discrete solutions to a system of linear inequalities?
4 votes

As far as I can tell from the information I could on the "Reverse Search" algorithm, it is a technique that helps to enumerate combinatorial structures. In particular the paper you mention in a ...

View answer
Using R for coding Matheuristic for Research Publication
Accepted answer
2 votes

A couple of years ago we had a student who wanted to call CPLEX from R and I think after spending a lot of time with a colleague they couldn't get it to work. The situation may have been improved, but ...

View answer