# Tagged Questions

Optimization with a linear objective function, subject to linear equality and linear inequality constraints.

12 views

### Linear equation in n variables with non negative solution [migrated]

The problem is that given a positive integer y and n positive integers x1 , x2 , ... , xn does there exist non negative integers ...
47 views

### Finding a minimal width strip which encloses a set of points in the plane

Problem: Consider a set of $n$ points in the plane, how could we find a strip of minimal vertical distance that contains all points? Definitions: A strip is defined by two parallel lines and the ...
31 views

### Project to nearest point in convex polytope

Is there a reasonably efficient algorithm for the following task? Input: a point $x \in \mathbb{R}^d$; a convex polytope $\mathcal{C} \subseteq \mathbb{R}^d$ Find: a point $y \in \mathcal{C}$ that is ...
19 views

### Does there always exist equivalent (M)(I)LPs with and without objective functions?

For computing pure Nash equilibria (game theory), there exists a MILP method in literature (clicky). In the proposed MILP, there is no objective function. A solution is a pure Nash equilibrium if it ...
33 views

### Flaw in linear programming solution for multi-commodity flow problem?

The multi-commodity flow problem problem statement - wiki According to constraints of multi-commodity flow problem a given material must start at source s with demand d and end up at its target t. ...
47 views

### Reducibility of finding Eulerian Path to Linear Programming

Consider any arbitrary directed, acyclic graph; how can we formulate the problem of finding a particular Eulerian path as a linear programming problem? It seems like there should be a relatively ...
33 views

95 views

### Single-source shortest paths as a linear program

I saw that I can formulate single-source shortest path as the following linear program: Given $G=(V,E)$ and $w\colon E\to R$ and with negative cycles, find $\max\,d(s,t)$ such that \begin{align*} ...
76 views

### Algorithm to optimize polling frequency between producer and consumer

I am trying to optimize what we call AJAX request polling frequency in the domain of web design. Here's a general version of the problem in simple lingo: Problem Statement: Suppose there are 3 ...
94 views

### What's the complexity of solving a packing LP?

Linear Programming is in polynomial time weakly (when numbers are encoded in unary). AFAIK it remains open if it is possible to solve LP in polynomial time strongly (when numbers are encoded in ...
54 views

### What is wrong with my LP exercise (longest path cost for a graph)

I have to do a linear programming exercise but i have some problems regarding the result. I have a graph with N nodes and E edges, that is not acyclic, and each edge is associated to a cost. I have ...
52 views

### Efficient formulation for binary integer linear programming

Problem: There are two types of balls, big (B) and small (S), which need to packed into boxes. One box can contain either: nothing, or 1 S, or 1 B, or 2 S, or 2 B, or 1 B and 2 S We are given the ...
80 views

### Formulating shortest path as submodular minimization

I'm curious about the general question of whether any combinatorial optimization problem with polynomial time solution can necessarily be reformulated as minimizing a submodular function. The answer ...
77 views

### Why cant we round results of linear programming to get integer programming?

Say if linear programming suggests that we need 2.5 trucks to deliver goods why cant we round up and say 3 trucks are needed. Similarly, if linear programming suggests we can afford only 3.7 workers ...
79 views

### Assign $m$ tasks to $n$ workers, with $m \geq n$

There are $n$ students that share the same apartment. At each evening, one of them must prepare dinner for everyone. There are $m$ evenings to schedule, with $m \geq n$, and you have to assign any ...
83 views

### Complexity of solving LP with a non-linear growth in variables/constraints

It has been shown that any Linear Program (LP) can be solved in a polynomial number of steps. An example of such algorithm is the ellipsoid method. To solve a problem which has $k$ variables and ...
39 views

### Find value of b

The following system of restrictions is given: $$y_1+ 2 y_2 \leq 4 \\ 2y_1+y_2 \leq 2 \\ y_1+b y_2 \leq 3 \\ y_1, y_2 \geq 0$$ For which values of b is there a degenarate basic feasible solution? ...
42 views

### Binary Integer Programming question - what graph problem is represented

I'm dealing with a BIP question, that represents a graph problem. The goal is finding the graph problem. I've spend a lot of time trying to solving this question but I couldn't find the answer to ...
114 views

130 views

### Inventory Routing - Subtour Elimination [closed]

I'm trying to implement a Inventory Routing Problem with Branch-and-Cut. But I'm facing with an issue regarding subtour elimination. (http://www.danflash.com/files/irp.pdf) The paper describes the ...
82 views

### Time complexity of linear program? [closed]

I have built a heuristic algorithm for approximately solving an NP complete graph problem by recursive linear relaxations. In each recursion, the algorithm returns a reduced graph, with number of ...
53 views

### A little confusion with the Knapsack problem (a worked example)

I'm going through a worked example on the Knapsack problem: My problem is that I don't understand quite follow the last bulletpoint. Where does the $x_4 = 4/5$ comes from? I know $x_4$ has to be a ...
40 views

### Authors of Complementary Slackness

Who were the first researchers to prove the Complementary Slackness condition for linear programming? I believe that strong optimality was proved by Gale, Kuhn, and Tucker in 1951, but I couldn't ...