Optimization with a linear objective function, subject to linear equality and linear inequality constraints.
0
votes
0answers
34 views
Algorithm to solve job assignment problem
Can someone suggest an algorithm to solve job assignment problem with condition?
With condition means that some jobs cannot be done by some workers. For example table as shown below:
In this table ...
3
votes
1answer
18 views
Express boolean logic operations in zero-one integer linear programming (ILP)
I have an integer linear program (ILP) with some variables $x_i$ that are intended to represent boolean values. The $x_i$'s are constrained to be integers and to hold either 0 or 1 ($0 \le x_i \le ...
3
votes
0answers
50 views
Issues with an optimization problem
I have an expression $$Ax+By+Cz.$$ where $A$, $B$ and $C$ are positive constants $\ge1$. The variables $x$, $y$ and $z$ are non-negative integers. I am also given a number $T$.
I want to find the ...
1
vote
2answers
63 views
Finding the required value of an algebric expression
I have an expression $$Ax+By+Cz.$$ where $A$, $B$ and $C$ are positive constants $\ge1$. The variables $x$, $y$ and $z$ are non-negative integers. I am also given a number $T$.
I want to find the ...
5
votes
1answer
96 views
NP complete problems that are solvable in polynomial time if the input (e.g. number of variables) is fixed?
I have seen some problems that are NP-hard but polynomially solvable in fixed dimension.
Examples, I think, are Knapsack that is polynomial time solvable if the number of items is fixed and Integer ...
2
votes
0answers
47 views
Job assignment problem
I want to solve job assignment problem using Hungarian algorithm of Kuhn and Munkres in case when matrix is not square. Namely we have more jobs than workers.
In this case adding additional row is ...
2
votes
2answers
220 views
Are all Integer Linear Programming problems NP-Hard?
As I understand, the assignment problem is in P as the Hungarian algorithm can solve it in polynomial time - O(n3). I also understand that the assignment problem is an integer linear programming ...
2
votes
3answers
33 views
Solving system of linear inequalities
I am trying to solve a system of inequalities in the following form:
$\ x_i - x_j \leq w $
I know these inequalities can be solved using Bellman-Ford algorithm. ...
5
votes
1answer
36 views
Finding a set of maximally different solutions using linear programming or other optimization technique
Traditionally, linear programming is used to find the one optimal solution to a set of constraints, variables and a goal (all described as linear relationships). Sometimes, when the objective is ...
8
votes
1answer
85 views
Maximizing a convex function with a linear constraint
The problem is
$$\max f(\mathbf{x}) \text{ subject to } \mathbf{Ax} = \mathbf{b}$$
where $f(\mathbf{x}) = \sum_{i=1}^N\sqrt{1+\frac{x_i^4}{(\sum_{i=1}^{N}x_i^2)^2}}$,
$\mathbf{x} = ...
3
votes
1answer
51 views
Why does absence of strongly polynomial time algorithm for LP imply restriction to rational instances?
From Bernhard Korte, Jens Vygen, Combinatorial Optimization,
Instances of LINEAR PROGRAMMING are vectors and matrices. Since no
strongly polynomial-time algorithm for LINEAR PROGRAMMING is known ...
4
votes
1answer
181 views
Find maximum distance between elements given constraints on some
I have a list of numbered elements 1 to N that fit into positions on a number line starting with 1. I also have constraints for these elements:
The element 1 is in position 1, and element N must be ...
5
votes
2answers
119 views
Randomized Rounding of Solutions to Linear Programs
Integer linear programming (ILP) is an incredibly powerful tool in combinatorial optimization. If we can formulate some problem as an instance of an ILP then solvers are guaranteed to find the global ...
2
votes
0answers
22 views
Maximum feasible subsystem problem (MaxFS) in 2 variables
Topic:
The maximum feasible subsystem problem, which is generally NP-hard [1].
Question:
Are there special algorithms in case of only 2 variables (2D linear constraints)? The problem seems to be a ...
6
votes
1answer
314 views
Formalization of the shortest path algorithm to a linear program
I'm trying to understand a formalization of the shortest path algorithm to a linear programming problem:
For a graph $G=(E,V)$, we defined $F(v)=\{e \in E \mid t(e)=v \}$ and $B(v)=\{ e \in E \mid ...
-1
votes
1answer
196 views
Integer LP formulation and the existence of a solution
A film producer is seeking actors and investors for his new movie. There are $n$ available actors; actor $i$ charges $s_i$ dollars. For funding, there are $m$ available investors. Investor $j$ will ...
6
votes
2answers
194 views
A variant of the Assignment Problem
In my variant of the assignment problem I have a set $A$ of agents and a set (of possibly different cardinality) $T$ of tasks. Each agent needs to be assigned exactly $n$ or $n+1$ tasks, and each task ...
3
votes
0answers
34 views
A variant of the assignment problem (?) [duplicate]
Possible Duplicate:
A variant of the Assignment Problem
(Not a comp.scientist, but have the basic research. Please excuse me if I've overlooked anything obvious.)
In my variant of the ...
3
votes
1answer
76 views
Formulating a linear program s.t. only extreme point solutions are found
If there are many solutions to a linear program s.t. the objective function is minimized/maximized (= optimal solutions are on an edge of the polytope), how can I force an LP solver to find only an ...
9
votes
1answer
261 views
Sorting as a linear program
A surprising number of problems have fairly natural reductions to linear programming problems. See Chapter 7 of [1] for examples of network flows, bipartite matching, zero-sum games, shortest paths, a ...
6
votes
2answers
315 views
Known facets of the Travelling Salesman Problem polytope
For the branch-and-cut method, it is essential to know many facets of the polytopes generated by the problem. However, it is currently one of the hardest problems to actually calculate all facets of ...
9
votes
2answers
209 views
Minimize the maximum component of a sum of vectors
I'd like to learn something about this optimization problem: For given non-negative whole numbers $a_{i,j,k}$,
find a function $f$ minimizing the expression
$$\max_k \sum_i a_{i,f(i),k}$$
An example ...
2
votes
2answers
329 views
Partition of a set of integer into 3 subsets of approximately equal sum
I'm having a very hard time trying to figure out how to solve this problem efficiently. Let me describe how it goes:
"A hard working mom bought several fruits with different nutritional values for ...
3
votes
1answer
107 views
Efficient bandwidth algorithm
Recently I sort of stumbled on a problem of finding an efficient topology given a weighted directed graph. Consider the following scenario:
Node 1 is connected to 2,3,4 at 50 Mbps. Node 1 has 100 ...
12
votes
1answer
213 views
Does every NP problem have a poly-sized ILP formulation?
Since Integer Linear Programming is NP-complete, there is a Karp reduction from any problem in NP to it. I thought this implied that there is always a polynomial-sized ILP formulation for any problem ...
10
votes
3answers
258 views
Finding exact corner solutions to linear programming using interior point methods
The simplex algorithm walks greedily on the corners of a polytope to find the optimal solution to the linear programming problem. As a result, the answer is always a corner of the polytope. Interior ...
