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

learn more… | top users | synonyms

1
vote
0answers
39 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 ...
1
vote
0answers
30 views

How to construct a network flow problem?

I have the optimization problem given below max $\sum_{i=1}^{N}\sum_{j=1}^{M} x_{ij}R_{ij}$ s.t $\quad 1)\quad \sum_{j=1}^{M} x_{ij}=1 \quad \forall i$ $\quad 2)\quad x_{ij} \in {0,1}$ $\quad ...
3
votes
0answers
30 views

Maximum set packing and minimum set cover duality

I read that the maximum set packing and the minimum set cover problems are dual of each other when formulated as linear programming problems. By the strong duality theorem, the optimal solution to the ...
0
votes
0answers
12 views

Writing linear programming constraint in a canonical form

I have a particular research problem that I'm formulating as a linear program. It's more or less an instance of the transportation problem, except there is one additional constraint that is proving ...
4
votes
2answers
69 views

Dynamic Shortest Path with Linear Programming

Consider a grid with $x=5$ columns, $y=5$ rows, and $T$ timesteps. There are $N=2$ agents in this grid, which can move vertically or horizontally. The positions of each agent $x$ at timestep $t$ ...
4
votes
0answers
44 views

Intuitive self-contained proof of Farkas' Lemma

I've been studying the proof of Farkas' Lemma, and given my rather fuzzy memory of Linear Algebra, am having some trouble with it. One version of Farkas' lemma states: For any convex cone ...
3
votes
0answers
29 views

Showing a linear program is infeasible or finding a feasible solution

I'm aware that for any given maximize/minimize LP problem, if its dual is unbounded then the primary is infeasible and vice versa. But what if there is no maximize/minimize objective function? For ...
0
votes
0answers
31 views

How to prove a min-max and max-min strong duality for Linear Programming example?

I was practicing Linear Programming, and came across the following question: Let $G = (V, E)$ be an undirected graph with capacities $c_e$ on each edge $e \in E$. let $s$, $t$ be two of its vertices. ...
0
votes
0answers
51 views

Max Flow / Linear Programming Reduction Variant

While studying max flow / LP, I came across a couple of reduction problems that gave me a bit of pause: Here are two variants of the standard Maximum Flow problem. Show that both of them can be ...
2
votes
0answers
55 views

General Steiner Tree Variants

In the general Steiner tree problem (Steiner tree in graphs), we are given an edge-weighted graph G = (V, E, w) and a subset S ⊆ V of required vertices. A Steiner tree is a tree in G that spans all ...
3
votes
1answer
36 views

Express product in ILP

Suppose I have a mixed integer-linear program (MILP) with variables $x,y,z$, where $y$ is a 0-or-1 variable, and I want to impose the constraint $z=xy$. This is not expressible in a MILP directly. ...
2
votes
1answer
37 views

Solution to a Np-hard problem and its relevance to a dual LP

From The design of APX algorithms book by David P. Williamson and David B. Shmoys, at the bottom of page 21 I saw the following statement (it is about the set cover LP and its dual): Let $y^*$ be ...
1
vote
1answer
44 views

Use max operation in a constraint in Linear Programming

I have liner programme with set of $x_{3n}$ variables where $x_{ij}$ are {0,1}. I am solving this linear programme using LP-Solve. Using these variables, I want to form following constraint : ...
1
vote
1answer
82 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*} ...
5
votes
0answers
74 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 ...
6
votes
0answers
83 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 ...
0
votes
1answer
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 ...
2
votes
1answer
47 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 ...
6
votes
0answers
76 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 ...
2
votes
1answer
53 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 ...
1
vote
0answers
76 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 ...
3
votes
1answer
67 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 ...
2
votes
1answer
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? ...
0
votes
1answer
41 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 ...
5
votes
0answers
108 views

Can the solution to a POMDP be found using linear programming?

It is known that Markov decision processes (MDPs) can be solved using linear programming (see page 24 of Carlos Guestrin's PhD dissertation). The linear program is: $$min_{V(x)} \sum_x ...
8
votes
3answers
213 views

Cast to boolean, for integer linear programming

I want to express the following constraint, in an integer linear program: $$y = \begin{cases} 0 &\text{if } x=0\\ 1 &\text{if } x\ne 0. \end{cases}$$ I already have the integer variables ...
2
votes
1answer
98 views

Modeling $(x > 0 \wedge y > 0) \Leftrightarrow z > 0$ in a linear program: impossible?

In this question, we see how to model boolean logic in $0 - 1$ ILPs. Moving to a relaxation, modelling $(x > 0 \vee y > 0) \Leftrightarrow z > 0$ with $x,y,z \in [0,1]$ with linear ...
3
votes
1answer
41 views

Are some Integer programming formulations completely useless for relaxation?

I was tasked with constructing an integer programming formulation for an NP-hard problem, and then with specifying its LP relaxation and the resulting approximation factor. The problem is that, while ...
4
votes
3answers
147 views

Help wrapping my head around a combinatorial optimization problem

Here's the problem I'm trying to solve: I have a bunch of widgets, whose weights vary over a small range. I would like to find the optimal grouping of them such that each group meets a minimum weight ...
0
votes
0answers
24 views

Mutipath selection in communication network

We have this assignment to be formulated then coded using Integer Linear Programming that is giving me such a headache. The problem is that I'm not sure on how to formulate it because of the way ...
4
votes
1answer
52 views

Unfeasible linear program becomes feasible if a variable is removed

Apologies, not a computer scientist by trade but I'm playing with linear programming these days. Let $\{x_i\}$ be $N$ optimization variables with bounds $$l_i \leq x_i \leq u_i$$ I'm interested in ...
0
votes
1answer
33 views

Branch and bound stanford slides doubt

On the 6th slide at https://web.stanford.edu/class/ee364b/lectures/bb_slides.pdf, while defining L2 and U2, why are we taking min for both?
1
vote
1answer
49 views

Restrictions that set binary variable to 1 when integer variable equals x, 0 otherwise

I have this problem: I'm building an integer linear program, which I'm going to give to an ILP solver. I have a binary variable Y which can be either 1 or 0 and an integer variable MONTH which takes ...
1
vote
0answers
35 views

Facility location on a Sphere with great circle distance

I am looking for an algorithm to find the point that minimizes the sum of the great circle distances to a set of fixed points on a sphere. In more detail: Given $x_1,\ldots, x_k$ fixed points in the ...
0
votes
1answer
92 views

Please explain linear programming as seen for this load balancing problem

I have at hand a linear program related to load balancing. However I have no idea what this is and wikipedia gives me something too simplified/abstract to be useful. I wonder if someone can explain ...
1
vote
0answers
48 views

Multidimensional 0-1 knapsack as the solution to 0-1 goal programming problem

I am trying to find the algorithm for the 0-1 goal programming problem. Actually I don't have any recent references for explicit algorithms, all the recent articles are about the modelling and not ...
4
votes
2answers
377 views

Linear programming with absolute values

I know that sometimes we can use absolute values into the objective functions or constraints. Is it always possible to use them, anywhere ? Example of use of absolute values: ...
5
votes
0answers
58 views

Uniform Sampling on Intersection of Faces of Simplices

I'm trying to sample uniformly on the intersections of faces of several simplicies, with all coordinates being non-negative. That is, given constraints $$A\vec{w}=\vec{b} \ \ and \ \ \vec{w} \geq ...
2
votes
1answer
126 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 ...
2
votes
1answer
79 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 ...
2
votes
1answer
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 ...
5
votes
0answers
39 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 ...
0
votes
1answer
166 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 ...
0
votes
1answer
99 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 ...
2
votes
1answer
57 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 ...
3
votes
0answers
21 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 ...
0
votes
1answer
52 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 ...
1
vote
1answer
111 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 ...
3
votes
0answers
37 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 ...
1
vote
1answer
150 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 ...