  Over the last decade, combinatorial algorithms have been obtained for exactly
solving several nonlinear convex programs. We first provide a formal context to
this activity by introducing the notion of {\em rational convex programs} --
this also enables us to identify a number of questions for further study. So
far, such algorithms were obtained for total problems only. Our main
contribution is developing the methodology for handling non-total problems,
i.e., their associated convex programs may be infeasible for certain settings
of the parameters.
  The specific problem we study pertains to a Nash bargaining game, called
ADNB, which is derived from the linear case of the Arrow-Debreu market model.
We reduce this game to computing an equilibrium in a new market model called
{\em flexible budget market}, and we obtain primal-dual algorithms for
determining feasibility, as well as giving a proof of infeasibility and finding
an equilibrium. We give an application of our combinatorial algorithm for ADNB
to an important "fair" throughput allocation problem on a wireless channel.
