The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Questions tagged [linear-programming]

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

277 questions
Filter by
Sorted by
Tagged with
247 views

273 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 ...
487 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 ...
143 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 ...
43 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 ...
1k views

### Express XOR with multiple inputs in zero-one integer linear programming (ILP)

In the below post, it is explained how to express xor of two variables as linear inequalities. Express boolean logic operations in zero-one integer linear programming (ILP) Naturally, the xor of ...
498 views

### Can you generate random linear programming problems?

I looked at Linear Programming, and it are problems like this: You know that Cabinet X costs 10 cents per unit, requires 6 square feet of floor space, and holds 8 cubic feet of files. Cabinet ...
72 views

### Does there exist a problem that is hard to do in parallel? [closed]

I am looking for a workload which is hard to paralellise/distribute between multiple machines. For example, integer factorization does not go 10 times faster if you have 10 machines to split the ...
29 views

### What is the most efficient algorithm for finding the bounding inequalities of a cone given the extremal rays?

Say that I am given a cone, as specified by the extremal rays whose facets form its convex hull, what is the most efficient algorithm that finds the linear-rank inequalities whose intersection defines ...
131 views

### Practical implications of strongly polynomial time algorithm for linear programming

Why do people care about whether a strongly polynomial time algorithm for linear programming exists or not? Does this have any practical improvement?
83 views

### Basic linear programming question

Trying to answer this question: A factory produces chocolate and candy. In order to produce 100 kilograms of chocolate, the factory has to use machine A for 1 hour, machine B for 4 hours, and machine ...
186 views

### Scheduling Problem Optimisation using LP solvers

I am currently working on a scheduling system which schedules individuals based on timeslots that have the following attributes: (1) Day of Week (2) Month (3) Session(AM/PM). The individuals ...
271 views

### How are basic feasible solutions in linear programming related to vertices in its corresponding polytope?

In Section 2.3.3 "Polytopes and LP" of the book "Combinatorial Optimization: Algorithms and Complexity" by Christos H. Papadimitriou, Theorem 2.4 establishes the relation between bfs's (basic feasible ...
863 views

### ILP and number of variables in constraints

This question is about the time impact of the length (i.e. number of variables) of the constraints in an Integer Linear Programming formulation. Most people try to reach the minimum number of ...
489 views

### Linear programming formulation of cheapest k-edge path between two nodes

Given a directed graph $G = (V,E)$ with positive edge weights, find the minimum cost path between $s$ and $t$ that traverses exactly $k$ edges. Here is my attempt using a flow network: \begin{align} \...
126 views

2k views

### Advantage of MTZ problem formulation of TSP

In class, we saw the Miller-Tucker-Zemlin formulation of the Travelling Salesmen Problem (TSP). MTZ is a way of formulating the TSP as an integer linear programming instance. I understand how MTZ ...
105 views

### What is linear relaxation in the context of bayesian networks? [closed]

To add onto the question, how are elliptical differential equations applicable in this context? I was listening to a talk about Bayesian networks and someone asked if they were using differential ...
594 views

### Boat riddle as a combinatorial optimization problem?

I remember a riddle about a bunch of people on a river bank, and a boat with limited capacity (lets say the boat can transport 2 people at a time). There are various relations between the people like: ...
523 views

### Applications for boolean logic operations in zero-one integer linear programming (ILP) [closed]

It is nice to know that every boolean formula can be expressed by zero-one integer programming by this answered question. But are there any applications? To be more precise: Are there papers which ...