Questions tagged [linear-programming]

For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.

49 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9
votes
0answers
73 views

What to do with cuts (constraints) when a fixation is contrary to a RHS in a ILP / LP relaxation?

I am trying to understand an algorithm in a paper by Crévits et al. (2012)1 (see algorithm 2, the cuts I'm referring to are from the reduced costs). It uses a series of successive cuts on a linear ...
9
votes
0answers
127 views

Ill-conditioned LP in Bender's decomposition

I have implemented a Bender's decomposition for a constrained network flow but the LP solver (Gurobi) warns me of the ill-conditioning of the slave dual LP. As you can see below, the coefficients seem ...
7
votes
0answers
77 views

Provide basic solution to CLP

I'm using Pyomo to formulate an LP with approx 500,000 constraints and 200,000 decision variables. The LP is solved using CLP. Some instances fail to return even a feasible solution after many ...
7
votes
0answers
137 views

Modeling traffic in a city

I am trying to model traffic in a city, $(i,j)$ represents a road in a city. There are $H$ vehicles in a city they have some prescheduled set of destinations to visit, $A_{j,h}$ denotes arrival time ...
7
votes
0answers
77 views

Building the Scheurman's Model II constraints for a multi period linear program

Scheurman's paper discusses Model I and model II Formulation to solve harvesting and scheduling problems. It is a specific implementation to solve multi period linear programs. Both models are also ...
7
votes
0answers
69 views

Modelling a simple ordering problem to have balanced delivery days

Assuming that I should buy 50 items from 25 different vendors with pre-known delivery duration between 2-7 day for each, which day of a week should I place each order so that the delivery days be even ...
6
votes
0answers
56 views

Estimating multistop routing costs

In many OR problems, it is sometimes a good idea (or necessary) to relax routing constraints. An example of this occurs in the classical facility location problem, where a warehouse can send out a ...
6
votes
0answers
123 views

Is this a valid strong polynomial algorithm for deciding LP feasibility?

Let $$A \cdot X + B \preceq 0$$ be a system of linear inequalities with $X \in \mathbb{R}^n$ $A\in \mathbb{R}^{m\times n}$ and $B \in \mathbb{R}^m$ where $m \geq n$. According to Farkas lemma, exactly ...
6
votes
0answers
61 views

Proof that the leaving variable cannot be selected as the entering one in the next round

Using the Dantzig's pivoting rule, can it be proven that the leaving variable of one round cannot be selected as the entering variable in the next round?
6
votes
0answers
76 views

Benefits of removing slack variables during presolve

I was reading Tobias Achterberg's thesis, and on page 138 he mentions the following presolving technique for linear equations (I'm slightly paraphrasing Example 10.2): Consider the equation $4x_1+...
5
votes
0answers
106 views

Obtaining the system of irredundant inequalities from a set of inequalities using CPLEX

Given a linear system of inequalities $Ax \geq b$, I would ideally like to compute the irredundant set for those set of inequalities. I know how to do so mathematically, but I was wondering if there ...
5
votes
0answers
59 views

Complexity of determining whether a LP or MIP is infeasible

What is the best complexity for the worst case scenario and the algorithm associated with it to determine if a linear programming (LP) is infeasible ? Further, what if we consider a mixed integer ...
5
votes
0answers
33 views

In a binary logistic regression context, how to introduce a constraint to model the dependency between consecutive samples

Imagine we are running a logistic regression to identify opportunities for car sale promotion, using previous promotion campaign's result. Each $y$ is the increase of car sale after the promotion. ...
5
votes
0answers
93 views

Construct a direction of recession of the dual that is from growth to dual function

Consider the primal problem $$\begin{array}{ll} \text{minimize} & c^\top x\\ \text{subject to} & Ax = b\\ & x \geq 0\end{array}$$ where $ A \in \mathbb {R}^{ m × n}$ has rank $m$. Suppose ...
4
votes
0answers
108 views

Does anyone have the criss cross algorithm programming code to solve linear programming problems?

I have a project that requires programming code for the simplex algorithm and criss-cross algorithm. The purpose of this project is to compare the two methods. I've tried to find it, but the ...
4
votes
0answers
63 views

Continue on “Is there a known MILP to schedule routes after routes are made”

I have made some progress on my previous question (Is there a known MILP to schedule routes after routes are made). I have derived the sets of the problem, which are: 1) Itineraries of vehicle: $i \in ...
4
votes
0answers
163 views

Publishing paper that uses LP solver to solve equation

I was reading this paper by Cerna et al. (2018)1. In the paper there are only CPLEX-solvable equations given by the authors and the results. How valuable is this paper, and what is its quality? Can ...
4
votes
0answers
191 views

How can I formulate this multi-objective optimization problem?

Now, for each system $X$ $(X=A,B,C,E)$, my objective is $$\max\min\frac{s_{x_u}}{d_{x_u}}$$ here, $x=a$ for system A, $x=b$ for system B and follows... and for the whole system, my objective is $$\max\...
3
votes
0answers
30 views

PuLP Python: How to linearize an inequality involving an integer variable

I am working on a Copper payables problem where the objective function is to maximise the sum of copper payable over a time period, T. The total amount of payable tonnes i.e. what the customer will ...
3
votes
0answers
50 views

Where I can study some job shop scheduling by course (video )?

I am seeking the help to know where I can study the job shop scheduling Heuristics or using solver by some course/video as I see some of books and papers hard to understand . It is hoped that the ...
3
votes
0answers
58 views

Optimal Seat Allocation Problem

I have to do an operations research assignment based on optimal seat allocation. The problem goes something like this. There are 5 rooms in an office each with a separate seating capacity. We now have ...
3
votes
0answers
47 views

Simplex method on graphs: How do I find a basic solution using the Ford-Fulkerson algorithm?

I'm tasked with solving a minimal cost flow problem. I'm asked to first use the Ford-Fulkerson algorithm on my graph to find a basic solution that will then be used to do the simplex method on that ...
3
votes
0answers
32 views

Linear functions in Lenstra's algorithm

I had asked this question at MathOverflow and was pointed here. I'm working on implementing Lenstra's algorithm. At the bottom of p.5 (at "construct $n+1$ linear functions"), he says to ...
3
votes
0answers
39 views

Public available MPS files with semi-continuous variables

Is there some MPS files with semi-continuous variables public available anywhere? To me it seems MIPLIB does not contain any. Erling
3
votes
0answers
108 views

On solving the Restricted Master Problem in Column Generation technique

I am working on developing a column generation (CG) based optimization framework for a large-scale airline crew pairing problem (a set-covering problem). First, I generate an initial feasible solution ...
3
votes
0answers
33 views

Constraint equivalence in PuLP

I'm working on an optimization problem in PuLP and I have to enforce a daily minimum of shifts and a daily maximum of assigned shifts. I have the following constraints to ensure each day has a minimum ...
2
votes
0answers
45 views

Two binding constraints - Linear Programming

I'm having some troubles to continue solving my system, I'm used to solve such systems but with "one" binding constraint, if someone could give me some helpful hints so I can solve it I will ...
2
votes
0answers
67 views

Solving transportation problem by the Network Simplex

I am trying to solve the following problem using Network Simplex method. But I have questions. My attempt: Basis Matrix$(B)$ Rows: 1, 2, 3, 4, 5 Column: (1,3) (1,4) (1,5) (2,3) (2,4) (2,5) $$ \...
2
votes
0answers
69 views

How to linearize this multiplicative constraint?

I have a constraint in the form $\sqrt{|\sum_{c\in C}{h_cw_c}|^2}\ge\sqrt{x}\zeta$ Here, $h_c$ is s row vector (know), $w_c$ is a column vector (variable). $x$ and $\zeta$ are also optimization ...
2
votes
0answers
56 views

Determine set of “arbitrage-free” regional prices

I am seeking for a way how to determine set of "arbitrage-free" regional prices for a single commodity market. There are $N>1$ production units with costs $C^{prod}_i, i=1,\dots,N$ and ...
2
votes
0answers
55 views

Reading MPS file for linear programming and reconstructing the Optimization model

Are you aware of any tutorial that can help me learn on how to reconstruct the objective function and constraints from a MPS file once it's loaded in MATLAB. I can load the mps file given to me and ...
2
votes
0answers
93 views

Condition for an integer program and its linear relaxation to have the same value

Let $A$ be a $(0,1)$-matrix where no row or column is a zero vector, and consider the following optimization programs \begin{align}(1):\min&\quad y\cdot1\\\text{s.t.}&\quad yA\ge w\\&\quad ...
2
votes
0answers
41 views

High-mix manufacturing capacity

I'm not an expert in OR but I would like to determine what is the maximum manufacturing capacity of a plant (or how much a plant can produce of mix products). Each person in the plant has a known set ...
2
votes
0answers
67 views

Finding Optimal Route using different Paths

I have a list of paths e.g. path 1 takes you from point A to B. A person needs to complete 5 of such paths. $$Route1 = path1 + ...
2
votes
0answers
58 views

Linear programming: extending problems yields non linearity

I had a linear programming problem with the following objective function $$f(x) = \sum_{j}x_jq_jp_j - \sum_{i}\left(\sum_{j}x_jq_jC_{ij} \right) c_i$$ Where $q, p, C, c$ are known. Let the term ...
2
votes
0answers
57 views

Weapon Target Assignment Problem + Time Windows

So I am very familiar with the WTAP it the static case. What I am wondering, is there a formulation that has "time windows" as well? Let's say you have some weapons and some targets, you know the ...
2
votes
0answers
58 views

Dantzig decomposition and Column Generation for equality constraints

I was trying to apply Dantzig Decomposition followed by Column Generation. The following is how I was taught. \begin{array}{l} \text { Minimize }-10 x_1-2 x_{2}-4 x_{3} \\ \text { subject to: } x_{1}+...
1
vote
0answers
27 views

Unifying constraint matrices in sparse situations

$\DeclareMathOperator\Set{Set}$ Let $Set=\{x\in\mathbb Z^{n}:\exists y\in\mathbb Z^m\text{ satisfying } A[x,y]'\leq b\}$ where $A$ has $r=km$ rows and $k=O(1)$. I am trying to write $$ Set=\{x\in\...
1
vote
0answers
44 views

To estimate new sales from history

A fruit supplier sells 3 types of fruits. The company has 3 salespersons. Here are the sales quantity of each person for each fruit. The total sales figure is available. (this is all the available ...
1
vote
0answers
64 views

Decomposition of Polyhedra

There is no doubt that clear examples consolidate the understanding of concepts being learnt. I am new to finding the structure and decomposition of a polyhedra. Suppose that we have the system $$ \...
1
vote
0answers
61 views

How to start the Dantzig-Wolfe decomposition?

I have the following problem: \begin{align}\min&\quad3x_1+5x_2+3x_3-2x_4+3x_5\\\text{s.t.}&\quad x_1+x_2+x_3+x_4\geq3\\&\quad3x_1+x_2+5x_3+x_4-2x_5\geq6\\&\quad x_1+2x_3-x_4\geq2\\&...
1
vote
0answers
32 views

Vertices of Polytope using Gurobi

Is there any way I can obtain all the vertices of a polytope using Gurobi? If this isn't possible, can I log all the intermediate vertices that Simplex finds before it hits the optimal one?
1
vote
0answers
31 views

How can I see the engine log when solving a LP using pulp (python)?

I wonder which command should I use to see how the steps the pulp solver is doing when solving a linear program.
1
vote
0answers
81 views

Expansion heuristic using gurobi reduced cost / shadow price (LP)

Gurobi 9.0.0 // C++ // LP Let us assume the following problem with three nodes: (1)-----(2)-----(3) node (1) is producing ...
1
vote
0answers
297 views

Canonical form of a linear program

I have a linear programming problem that I want to write in the canonical form: \begin{align}\min&\quad c^\top X\\\text{s.t.}&\quad A\cdot X\le b\end{align} The problem is given by \begin{...
1
vote
0answers
40 views

Verifying the correctness of KKT conditions

I have a LP problem and derived the corresponding KKT conditions for the same. I simulated the LP and obtained the primal and dual values and manually checked if the KKT conditions hold. Is there any ...
1
vote
0answers
56 views

Linear programming with correction term based on decision vector

I had a linear programming problem where I am optimizing some function $$f(x) = \sum_{j}x_jq_jp_j - \sum_{i}\left(\sum_{j}x_jq_jC_{ij} \right) c_i$$ Where $q, p, C, c$ are known. I now want to ...
0
votes
0answers
113 views

Resource constrained LP problem

I am working on Diet Allocation problem. Where we need to provide food piece for protein deficiency. The data is as below: ...
0
votes
0answers
95 views

Need help in formulating linear program

Edit: updated my solution for linear programming Can anyone explain the following passage? Both semiconductors and power generation industries also want to buy as many of the remaining units as ...